Quant Memo
Coding/●●●●●

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 O(V+E)O(V + E).

Your answer

This one is open-ended. Work it through, then check your reasoning against the full solution.

More Coding questions