Can every job finish? (cycle detection)
Asked at DE Shaw
You have n jobs labeled 0 .. n-1 and a list of prerequisite pairs. [a, b] means job b must finish before job a starts. Decide whether all jobs can be completed, that is, whether the dependencies are free of cycles.
n = 4, prereqs = [[1, 0], [2, 0], [3, 1], [3, 2]] -> True
n = 2, prereqs = [[1, 0], [0, 1]] -> False (0 and 1 wait on each other)
Return True if a valid schedule exists, else False. Aim for .
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.