Order tasks with dependencies

Medium30 minFree, no account

A topological sort wearing a build system, and the cycle you have to report usefully.

The question

Given tasks and their dependencies, return an order in which they can all run, or report that it is impossible.

If there is a cycle, say which tasks are in it, not just that one exists.

order({ a: [], b: ["a"], c: ["b"], d: ["a"] })
// ["a", "b", "d", "c"]: any valid order

order({ a: ["b"], b: ["a"] })
// { error: "cycle", cycle: ["a", "b"] }

30:00Commit to an answer before you open the solution. Reading it first teaches you to recognise good answers, which is not the skill being tested.

Stuck?

0 of 3 hints taken

The worked solution

written by a person · not a grade

Score yourself

0 of 5 marked

A correct topological order in O(V + E)30
Detected cycles rather than looping or returning a partial order25
Reported the actual cycle members25
Handled self-dependencies, unknown deps and empty input10
Stated complexity and mentioned determinism or parallelism10

We run no AI here and nothing on this page grades you. The score is yours, and the useful number is the one you get on the same problem a month from now, cold.

kept in this browser only