Topological Sort

Topological sort appears in every problem with dependencies: build systems, course prerequisites, task scheduling. If things need to happen in a specific order, you're probably looking at a DAG — a directed acyclic graph where tasks are nodes and dependencies are one-way edges with no cycles.

What it solves

Ordering items so every item comes after the things it depends on. A build system uses it to compile modules in dependency order. A scheduler uses it to run tasks after their prerequisites. Course planners use it to sequence classes.

Recognition signals

• "Dependencies", "prerequisites", "must happen before", "build order"
• "Tasks/jobs/steps that depend on each other"
• "If X depends on Y, Y runs first"
• "Detect/throw on circular dependencies"
• A graph of ordering constraints (vs. shortest-path or reachability)

The approach

Two implementations, same result:

Kahn's is the safer default for interviews: you see the ordering building up, and cycle detection falls out naturally — if you process fewer nodes than exist, there's a cycle.

What to tell the AI

Implement Kahn's algorithm for the build graph: an adjacency list of dependencies. Compute an indegree for each node, seed a queue with indegree-0 nodes, process them in order, and if the output has fewer nodes than the input, throw a cycle error with the leftover nodes. Return the ordered list.

What to verify

• Cycle handling — does it detect cycles, or silently return a partial order? Build systems must fail loudly.
• Indegree updates — decrementing only when a prerequisite is processed; off-by-ones produce wrong orders.
• Stability — does the AI add arbitrary tie-breaking? Decide whether a stable (input-order) or deterministic (sorted) tie-break matters.
• DAG assumption — the AI might skip cycle checks because the problem "looks like a DAG."
• Duplicate edges / self-loops — the AI may not deduplicate, inflating indegrees.

Worked micro-example

Tasks A, B, C, D with A→C, B→C, C→D. Indegrees: A=0, B=0, C=2, D=1. Kahn's seeds {A, B}, emits them (order depends on your queue), decrements C to 0, emits C, decrements D to 0, emits D. Valid orders: A B C D or B A C D. If someone added C→A, you'd have a cycle and Kahn's would finish with fewer than 4 nodes — that's your failure signal.

Practice problems

Try these: Task Scheduler (topo sort with cycle detection, critical path), Schedulr (dependencies + availability windows), Kitchen Orders (station ordering under priority constraints).