karat

foo.js

/*
Our local radio station is running a show where the songs are ordered in a very specific way.  The last word of the title of one song must match the first word of the title of the next song - for example, "Silent Running" could be followed by "Running to Stand Still".  No song may be played more than once.

Given a list of songs and a starting song, find the longest chain of songs that begins with that song, and the last word of each song title matches the first word of the next one.  Write a function that returns the longest such chain. If multiple equivalent chains exist, return any of them.

Example:
songs1 = [
    "Down By the River",
    "River of Dreams",
    "Take me to the River",
    "Dreams",
    "Blues Hand Me Down",
    "Forever Young",
    "American Dreams",
    "All My Love",
    "Cantaloop",
    "Take it All",
    "Love is Forever",
    "Young American",
    "Dreamship",
    "Every Breath You Take",
]
song1_1 = "Every Breath You Take"
chaining(songs1, song1_1) => ['Every Breath You Take', 'Take it All', 'All My Love', 'Love is Forever', 'Forever Young', 'Young American', 'American Dreams', 'Dreams']

Additional Input:
song1_2 = "Dreams"
song1_3 = "Blues Hand Me Down"
song1_4 = "Cantaloop"

songs2 = [
    "Bye Bye Love",
    "Nothing at All",
    "Money for Nothing",
    "Love Me Do",
    "Do You Feel Like We Do",
    "Bye Bye Bye",zz
    "Do You Believe in Magic",
    "Bye Bye Baby",
    "Baby Ride Easy",
    "Easy Money",
    "All Right Now",
]
song2_1 = "Bye Bye Bye"
song2_2 = "Bye Bye Love"

songs3 = [
    "Love Me Do",
    "Do You Believe In Magic",
    "Magic You Do",
    "Magic Man",
    "Man In The Mirror"
]
song3_1 = "Love Me Do"

All Test Cases:
chaining(songs1, song1_1) => ['Every Breath You Take', 'Take it All', 'All My Love', 'Love is Forever', 'Forever Young', 'Young American', 'American Dreams', 'Dreams']
chaining(songs1, song1_2) => ['Dreams']
chaining(songs1, song1_3) => ['Blues Hand Me Down', 'Down By the River', 'River of Dreams', 'Dreams']
chaining(songs1, song1_4) => ['Cantaloop']
chaining(songs2, song2_1) => ['Bye Bye Bye', 'Bye Bye Baby', 'Baby Ride Easy', 'Easy Money', 'Money for Nothing', 'Nothing at All', 'All Right Now']
chaining(songs2, song2_2) => ['Bye Bye Love', 'Love Me Do', 'Do You Feel Like We Do', 'Do You Believe in Magic']
chaining(songs3, song3_1) => ['Love Me Do', 'Do You Believe in Magic', 'Magic Man', 'Man In The Mirror']

Complexity Variable:
n = number of songs in the input

*/

"use strict";

const songs1 = [
  'Down By the River',
  'River of Dreams',
  'Take me to the River',
  'Dreams',
  'Blues Hand Me Down',
  'Forever Young',
  'American Dreams',
  'All My Love',
  'Cantaloop',
  'Take it All',
  'Love is Forever',
  'Young American',
  'Dreamship',
  'Every Breath You Take'
];
const song1_1 = 'Every Breath You Take';
const song1_2 = 'Dreams';
const song1_3 = 'Blues Hand Me Down';
const song1_4 = 'Cantaloop';

const songs2 = [
  'Bye Bye Love',
  'Nothing at All',
  'Money for Nothing',
  'Love Me Do',
  'Do You Feel Like We Do',
  'Bye Bye Bye',
  'Do You Believe in Magic',
  'Bye Bye Baby',
  'Baby Ride Easy',
  'Easy Money',
  'All Right Now'
];
const song2_1 = 'Bye Bye Bye';
const song2_2 = 'Bye Bye Love';

const songs3 = [
  'Love Me Do',
  'Do You Believe In Magic',
  'Magic You Do',
  'Magic Man',
  'Man In The Mirror'
];
const song3_1 = 'Love Me Do';


// function chaining(songs = [], songName) {
//   const results = [songName];
//   let parts = songName.split(' ');  
//   let lastWord = parts.at(-1);
  
//   for (let i = 0; i < songs.length; i++) {
//     if (songs[i] === songName) continue;
//     const [firstWord, ...rest] = songs[i].split(' ');
    
//     if (firstWord === lastWord) {
//       lastWord = rest.at(-1);
//       results.push(songs[i]);
//     }
//   }
  
//   return results;
// }

function chaining(songs = [], songName) {
  let map = {};
  const results = [songName];
  
  for (let i = 0; i < songs.length; i++) {
    const song = songs[i];
    const tokens = song.split(' ');
    const firstWord = tokens[0];
    const lastWord = tokens.at(-1);
    
    if (!map[firstWord]) map[firstWord] = { first: [i], last: [] };
    else map[firstWord].push(i);
    
    if (!map[lastWord]) map[lastWord] = { first: [], last: [i] };
    else map[lastWord].push(i);
  }

  const tokens = songName.split(' ');
  let lastWord = tokens.at(-1);

  console.log({ map, lastWord });

  while (map[lastWord].length > 0) {
    const index = map[lastWord].pop();
    const song = songs[index];
    results.push(song);
    lastWord = song.split(' ').at(-1);
  }
  
  return results;
}

let res = chaining(songs3, song3_1);
console.log(res);

// O(n^2) O(n)
function findPair(songs = []) {
  const results = [];
    
  for (let i = 0; i < songs.length; i++) {
    const song = parseSong(songs[i]);
    
    for (let j = 0; j < songs.length; j++) {
      if (j === i) continue;
      const otherSong = parseSong(songs[j]);
      const combinedSeconds = song.seconds + otherSong.seconds;
      if (![0, 60].includes(combinedSeconds)) continue;
      
      if (
        (song.minutes + otherSong.minutes === 7) && (combinedSeconds === 0)
        || (song.minutes + otherSong.minutes === 6) && (combinedSeconds === 60)
      ) {
        results.push([song.name, otherSong.name]);
        break; 
      }
    }
    
    if (results.length) break;
  }
  
  return results;
}

function parseSong(song) {
  const [name, time] = song;
  let [minutes, seconds] = time.split(':');
  minutes = Number(minutes);
  seconds = Number(seconds);
  return { name, minutes, seconds };
}
/*
console.log(
  findPair(songTimes1)
);

console.log(
  findPair(songTimes2)
);
console.log(
  findPair(songTimes3)
);
console.log(
  findPair(songTimes4)
);
console.log(
  findPair(songTimes5)
);
console.log(
  findPair(songTimes6)
);*/

const songs3 = [
    "Love Me Do",
    "Do You Believe In Magic",
    "Magic You Do",
    "Magic Man",
    "Man In The Mirror"
];

const songs2 = [
    "Bye Bye Love",
    "Magic Potato",
    "Nothing at All",
    "Money for Nothing",
    "Potato Magic Man",
    "Love Me Do",
    "Do You Feel Like We Do",
    "Bye Bye Bye",
    "Do You Believe in Magic",
    "Bye Bye Baby",
    "Baby Ride Easy",
    "Easy Money",
    "All Right Now",
];

const song2_1 = "Bye Bye Love";
const song3_1 = "Love Me Do";

function getFirstAndLastWord(song) {
  const words = song.split(' ');
  return { first: words[0], last: words.at(-1) };
}

function chaining(songs = [], startSong) {
  const firstWords = {};
  // const lastWords = {};
  const chains = {}; // all possible chains

  for (let i = 0; i < songs.length; i++) {
    const song = songs[i];
    const { first, last } = getFirstAndLastWord(song);

    if (!firstWords[first]) firstWords[first] = [];
    // if (!lastWords[last]) lastWords[last] = [];

    firstWords[first].push(song);
    // lastWords[last].push(song);
    chains[songs[i]] = [songs[i]];
  } 
  debugger;
  let longestChain = [startSong];
  const queue = [startSong];
  
  while (queue.length > 0) {
    const currentSong = queue.shift();
    const currentChain = chains[currentSong];
    const { last } = getFirstAndLastWord(currentSong);

    if (firstWords[last]) {
      for (let nextSong of firstWords[last]) {
        if (currentChain.includes(nextSong)) continue; // already have this song in the chain
        
        const newChain = [...currentChain, nextSong];

        if (newChain.length > chains[nextSong].length) {
          chains[nextSong] = newChain;
          queue.push(nextSong);
          
          if (newChain.length > longestChain.length) {
            longestChain = newChain;
          }
        }
      }
    }
  }
  
  return longestChain;
}

let res = chaining(songs2, song2_1);
console.log(res);

foo2.js

/*
You're developing a system for scheduling advising meetings with students in a Computer Science program. Each meeting should be scheduled when a student has completed 50% of their academic program.

Each course at our university has at most one prerequisite that must be taken first. No two courses share a prerequisite. There is only one path through the program.

Write a function that takes a list of (prerequisite, course) pairs, and returns the name of the course that the student will be taking when they are halfway through their program. (If a track has an even number of courses, and therefore has two "middle" courses, you should return the first one.)

Sample input 1: (arbitrarily ordered)
pairs1 = [
	["Foundations of Computer Science", "Operating Systems"],
	["Data Structures", "Algorithms"],
	["Computer Networks", "Computer Architecture"],
	["Algorithms", "Foundations of Computer Science"],
	["Computer Architecture", "Data Structures"],
	["Software Design", "Computer Networks"]
]

In this case, the order of the courses in the program is:
	Software Design
	Computer Networks
	Computer Architecture
	Data Structures < 
	Algorithms
	Foundations of Computer Science
	Operating Systems

Sample output 1:
	"Data Structures"

Sample input 2:
pairs2 = [
    ["Algorithms", "Foundations of Computer Science"],
    ["Data Structures", "Algorithms"],
    ["Foundations of Computer Science", "Logic"],
    ["Logic", "Compilers"],
    ["Compilers", "Distributed Systems"],
]

Sample output 2:
	"Foundations of Computer Science"

Sample input 3:
pairs3 = [
	["Data Structures", "Algorithms"],
]

Sample output 3:
	"Data Structures"

All Test Cases:
halfway_course(pairs1) => "Data Structures"
halfway_course(pairs2) => "Foundations of Computer Science"
halfway_course(pairs3) => "Data Structures"

Complexity analysis variables:

n: number of pairs in the input
*/

"use strict";


const pairs1 = [
  ["Foundations of Computer Science", "Operating Systems"],
  ["Data Structures", "Algorithms"],
  ["Computer Networks", "Computer Architecture"],
  ["Algorithms", "Foundations of Computer Science"],
  ["Computer Architecture", "Data Structures"],
  ["Software Design", "Computer Networks"]
];

const pairs2 = [
  ["Algorithms", "Foundations of Computer Science"],
  ["Data Structures", "Algorithms"],
  ["Foundations of Computer Science", "Logic"],
  ["Logic", "Compilers"],
  ["Compilers", "Distributed Systems"],
];

const pairs3 = [
  ["Data Structures", "Algorithms"]
];


// time: O(4n)
// space: O(3n)
function halfway_course(pairs = []) {
  const map = {};
  const firstCourse = {};
  let chain = [];
  
  for (let pair of pairs) {
    const [course1, course2] = pair;
    firstCourse[course2] = false;
    if (firstCourse[course1] !== false) firstCourse[course1] = true;
  }
  
  for (let k in firstCourse) {
    if (firstCourse[k]) {
      chain.push(k);
      break;
    }
  }
  
  for (let pair of pairs) {
    const [course1, course2] = pair;
    map[course1] = course2;
  }

  // build the chain
  let ptr = map[chain[0]];
  while (ptr) {
    chain.push(ptr);
    ptr = map[ptr];
  }
  
  // get middle
  let idx = Math.floor(chain.length / 2);
  if (chain.length % 2 === 0) idx -= 1;
  const middle = chain[idx];
  
  return middle;
}

console.log(
  halfway_course(pairs1), '\n',// "Data Structures"
  halfway_course(pairs2), '\n', // "Foundations of Computer Science"
  halfway_course(pairs3) // "Data Structures"
)


function find_pairs(enrollments = []) {
  const results = {};  

  for (let i = 0; i < enrollments.length; i++) {
    const student = parseEnrollment(enrollments[i]);
    const coursesTaking = { [student.course]: true };
    
    for (let j = 0; j < enrollments.length; j++) {
      if (j === i) continue;
      const otherStudent = parseEnrollment(enrollments[j]);
      if (student.id === otherStudent.id) continue;
      
      
      const key = [student.id, otherStudent.id].sort().join(',');
      if (!results[key]) results[key] = [];
      
      if (coursesTaking[otherStudent.course] && !results[key].includes(otherStudent.course)) {
        results[key].push(otherStudent.course);
      }
    }
  }
  
  return results;
}

// console.log(
//   "enrollments1",
//   find_pairs(enrollments1)
// );

// console.log(
//   "enrollments2",
//   find_pairs(enrollments2)
// );

// console.log(
//   "enrollments3",
//   find_pairs(enrollments3)
// );

function parseEnrollment(enrollment) {
  const [id, course] = enrollment;
  return {id, course};
}