Algorithm selectionIntermediate
Ordering tasks with dependencies
Scenario
A build system has tasks, each listing the tasks that must finish before it can start. Produce a valid execution order, or report that none exists. Later, the team asks for the *maximum parallelism*: which tasks can run at the same time. Choose the model and algorithm.
Your task
- Model the input as a graph: what are vertices and edges, and which direction do edges point?
- State the condition under which no valid order exists and how you detect it.
- Choose between Kahn's algorithm and DFS-based ordering; justify with respect to the parallelism follow-up and cycle reporting.
- Sketch the algorithm and give its complexity.
- Edge cases: tasks with no dependencies, dependencies on unknown tasks, self-dependency, duplicate edges.
Pattern RecognitionProblem ClarificationEdge Cases
Work it out
Write your analysis before revealing anything. The self-check below compares it against what a strong answer contains.
Reveal
Progressive — each section builds on the previous one.
Key observation
The fix
Edge cases
Complexity
What this tests
Self-check
Tick what your analysis covered. Be honest — this feeds your readiness profile.