Return a sorted ordering of courses such that we can finish all courses

Question

The task:

We're given a hashmap associating each courseId key with a list of courseIds values, which represents that the prerequisites of courseId are courseIds. Return a sorted ordering of courses such that we can finish all courses.

Return null if there is no such ordering.

For example, given {'CSC300': ['CSC100', 'CSC200'], 'CSC200': ['CSC100'], 'CSC100': []}, should return ['CSC100', 'CSC200', 'CSCS300'].

My solution:

const isEveryCourseCovered = courses => courses.every(c => !Boolean(c));
const getCourseOrder = courses => {
  const courseSubjects = Object.keys(courses);
  const courseRequirements = Object.values(courses);
  const courseOrder = [];

  do {
    courseSubjects.map((subject, i) => {
      if (subject) {
        courseRequirements[i].map((requirement, idx) => {
          if (courseOrder.includes(requirement)) {
            courseRequirements[i].splice(idx, 1);
          }
        });
        if (!courseRequirements[i].length) {
          courseOrder.push(subject);
          delete courseSubjects[i];
        }
      }
    });
  } while(!isEveryCourseCovered(courseSubjects));

  return courseOrder;
};

const coursesObj = {'CSC300': ['CSC100', 'CSC200'], 'CSC200': ['CSC100'], 'CSC100': []};
console.log("result ", getCourseOrder(coursesObj));

Answer 1

Objects are passed by "copy of a reference".

Notice that the coursesObj after the function call has empty values ( see snippet below )

const isEveryCourseCovered = courses => courses.every(c => !Boolean(c));
const getCourseOrder = courses => {
  const courseSubjects = Object.keys(courses);
  const courseRequirements = Object.values(courses);
  const courseOrder = [];

  do {
    courseSubjects.map((subject, i) => {
      if (subject) {
        courseRequirements[i].map((requirement, idx) => {
          if (courseOrder.includes(requirement)) {
            courseRequirements[i].splice(idx, 1);
          }
        });
        if (!courseRequirements[i].length) {
          courseOrder.push(subject);
          delete courseSubjects[i];
        }
      }
    });
  } while (!isEveryCourseCovered(courseSubjects));

  return courseOrder;
};

const coursesObj = {
  'CSC300': ['CSC100', 'CSC200'],
  'CSC200': ['CSC100'],
  'CSC100': []
};
console.log("result ", getCourseOrder(coursesObj));

console.log("Courses Object : ", coursesObj);

You should create a copy of the passed object, a quick way ( one of many ways ) of doing that is JSON.parse(JSON.stringify(c)); ( see snippet below ):

const getCourseOrder = c => {
  // make a copy of the input object
  const courses = JSON.parse(JSON.stringify(c));

const isEveryCourseCovered = courses => courses.every(c => !Boolean(c));
const getCourseOrder = c => {
  // make a copy of the input object
  const courses = JSON.parse(JSON.stringify(c));

  const courseSubjects = Object.keys(courses);
  const courseRequirements = Object.values(courses);
  const courseOrder = [];

  do {
    courseSubjects.map((subject, i) => {
      if (subject) {
        courseRequirements[i].map((requirement, idx) => {
          if (courseOrder.includes(requirement)) {
            courseRequirements[i].splice(idx, 1);
          }
        });
        if (!courseRequirements[i].length) {
          courseOrder.push(subject);
          delete courseSubjects[i];
        }
      }
    });
  } while (!isEveryCourseCovered(courseSubjects));

  return courseOrder;
};

const coursesObj = {
  'CSC300': ['CSC100', 'CSC200'],
  'CSC200': ['CSC100'],
  'CSC100': []
};
console.log("result ", getCourseOrder(coursesObj));

console.log("Courses Object : ", coursesObj);

I didn't test the performance but i would guess it wouldn't be that efficient since it has 5 nested loops (do while, .map, .map, .includes) and .every that's called on every iteration of the while loop and 3 ifs

Reading the requirement :

Return a sorted ordering of courses

Array.sort() was the first thing to come to my mind, my suggested approach would be simply sorting the Object.keys of the coursesObj based on the length of the value ( array of required courses) corresponding to that key, like so :

const coursesObj = {
  'CSC300': ['CSC100', 'CSC200'],
  'CSC400': ['CSC100', 'CSC200', 'CSC300'],
  'CSC200': ['CSC100'],
  'CSC100': []
};

const result = Object.keys(coursesObj).sort((a, b) =>
  coursesObj[a].length - coursesObj[b].length
);

console.log(result)

PS : i added the CSC400 key in the middle just for the demo.

EDIT :

If you have an Object like :

const coursesObj = 
    {  
      c1: ['c2', 'c3', 'c4'], 
      c5: ['c1'], 
      c4: [], 
      c2: [], 
      c3: ['c4']
    }

you can transform it to add the prerequisites of the courses in its prerequisites array so it becomes :

const detailed = 
   { 
     c1: [ 'c2', 'c3', 'c4' ],​​​​​
     c5: [ 'c1', 'c2', 'c3', 'c4' ],​​​​​ // c5 now has c1 and the prerequisites of c1
   ​​​​​  c4: [],​​​​​
​​​​​     c2: [],​​​​​
   ​​​​​  c3: [ 'c4' ] 
   }​​​​​

then apply the same sort function above :

const coursesObj = { c1: ["c2", "c3", "c4"], c5: ["c1"], c4: [], c2: [], c3: ["c4"] };

const detailedObj = Object.entries(coursesObj).reduce((accumulator, [courseId, requirements]) => {
  accumulator[courseId] = requirements.slice(0); // original courses required.

  requirements.forEach(course => {
    accumulator[courseId].push(...coursesObj[course]); // add the required courses for each required course .
  });

  // remove the duplicates
  accumulator[courseId] = [...new Set(accumulator[courseId])];

  return accumulator;
}, {});

// sort by the number of prerequisites 
const result = Object.keys(detailedObj).sort((a, b) =>
  detailedObj[a].length - detailedObj[b].length
);

console.log(result);