Quant Memo
Coding/●●●●

Fewest rounds to finish all jobs

Asked at Two Sigma, DE Shaw

Jobs 1 .. n have dependencies: [a, b] means a must finish before b starts. In each round you may run every job whose prerequisites are all already done, in parallel. Find the minimum number of rounds to finish all jobs, or -1 if the dependencies are cyclic.

n = 3, deps = [[1, 3], [2, 3]]   ->   2      # round 1: {1, 2};  round 2: {3}

Return the minimum number of rounds. 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