Quant Memo
Coding/●●●●

Is the schedule order unique?

Asked at DE Shaw

Given jobs and their dependencies (("curves", "swaps") means curves before swaps), decide whether there is exactly one valid execution order. If two or more valid orders exist, or if the dependencies are cyclic (no order at all), return False.

jobs = ["a", "b", "c"]
deps = [("a", "b"), ("b", "c")]      ->   True    (only a, b, c works)

jobs = ["a", "b", "c"]
deps = [("a", "b"), ("a", "c")]      ->   False   (a, b, c and a, c, b both work)

Return whether the topological order is unique. 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