Task Scheduler
Run dependent tasks in order and fail on cycles, topological sort with a bug → feature → scale arc.
Problem
A build system schedules tasks with dependencies. Each Task { id, deps: Task[], duration }. The starter code has a bug.
Phase 1 — Fix the bug
The scheduler sometimes returns tasks before their dependencies. The run order must guarantee every task appears after all of its dependencies.
Phase 2 — Feature
Add cycle detection: if the dependency graph has a cycle, throw an error listing the tasks in the cycle. Then add criticalPath(): the sequence of tasks with the maximum total duration (all dependencies must complete first).
Phase 3 — Scale
The build graph grows to thousands of tasks. Ordering and longest-path must both stay efficient.
What interviewers watch
Kahn's algorithm with correct indegree bookkeeping, cycle detection that names the offenders, and the DAG-longest-path trick (topological order + relax).