0
\$\begingroup\$

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));
\$\endgroup\$
  • \$\begingroup\$ Should the values be sorted by (alpha-) numeric order? e.g. if the input was {'CSC400': ['CSC200'], 'CSC300': ['CSC100', 'CSC200'], 'CSC200': ['CSC100'], 'CSC100': []}; then should the output be [ "CSC100", "CSC200", "CSC300", "CSC400"]? \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Feb 13 at 1:01
  • \$\begingroup\$ @SᴀᴍOnᴇᴌᴀ following the pattern of the post, i assume CSC400 would have an array of courses required to get to it, 'CSC400': ['CSC100', 'CSC200', 'CSC300'], \$\endgroup\$ – Taki Feb 13 at 1:05
  • \$\begingroup\$ @Taki you can’t assume CS300 would be a pre-requisite of CS400. Some institutions might not have such a pattern- e.g. if both are elective courses like graphics and networking \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Feb 13 at 2:32
  • \$\begingroup\$ @SᴀᴍOnᴇᴌᴀ oh didn't know that, fair enough, but again, it's just an assumption following the pattern in the post. \$\endgroup\$ – Taki Feb 13 at 3:24
2
\$\begingroup\$

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);

\$\endgroup\$
  • \$\begingroup\$ Thanks for the input. There are something I definitely will take into account. But I'm not sure, whether the solution you presented is correct. The sorting can't be done by the length of the array alone but has to be in relation to the required courses. E.g. const coursesObj = { 'c1': ['c2', 'c3', 'c4'], 'c5': ['c1'], 'c4': [], 'c2': [], 'c3': ['c4'], }; should return this order {c4, c2, c3, c1, c5} \$\endgroup\$ – thadeuszlay Feb 13 at 5:48
  • \$\begingroup\$ @thadeuszlay i updated the answer for the input you provided, \$\endgroup\$ – Taki Feb 13 at 17:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.