Detect and return a prerequisite cycle in a course catalog
A university’s course planner imports the catalog from several departments, and sometimes their prerequisite rules contradict each other: Statistics II requires Data Modeling, which requires Statistics II. Students can then never finish either course. Saying “the catalog is broken” is not enough; the registrar needs to see the exact loop to fix it.
Implement findPrerequisiteCycle(catalog). Return null when every course in the catalog can eventually be completed. Otherwise, return one prerequisite cycle.
findPrerequisiteCycle(catalog) // => string[] | null
// catalog: { [courseCode]: string[] } course code -> codes of its prerequisites
catalog (for example, transfer credit) counts as already completed.[c0, c1, ..., ck, c0]:
c1 is in catalog[c0], c2 is in catalog[c1], and so on, and c0 is in catalog[ck];[c0, c0].catalog.findPrerequisiteCycle({
MATH101: [],
MATH201: ['MATH101'],
STAT210: ['MATH201', 'AP-CALC'], // AP-CALC is transfer credit
});
// => null
findPrerequisiteCycle({
STAT101: [],
STAT201: ['STAT101', 'DATA220'],
DATA220: ['STAT201'],
ML300: ['DATA220'],
});
// => ['STAT201', 'DATA220', 'STAT201'] (or ['DATA220', 'STAT201', 'DATA220'])
// ML300 can never be completed either, but it is not part of the loop.
findPrerequisiteCycle({ THESIS: ['THESIS'] });
// => ['THESIS', 'THESIS']
findPrerequisiteCycle({});
// => null