Topological sort — every question, written out
Order a DAG so every edge points forward. Kahn's algorithm peels off nodes with no remaining prerequisites. A leftover node proves there is a cycle.
Read the topological sort explanation and watch it run
Why is Kahn’s algorithm O(V + E)? Account for both terms.
Complexity derivation
Each node is enqueued and dequeued once, and each edge decrements exactly one counter once
Setup costs one pass over the edges to build the counters and one pass over the nodes to seed the queue. In the main loop a node enters the queue exactly once — at the moment its count first touches zero — and each edge is walked exactly once, when its source is placed. Adding the two gives O(V + E), the same shape as BFS, because this *is* BFS’s discipline applied to clearing constraints.
See it run — The badges are the indegree table, built in one pass over the edges before the loop begins.
The problem asks for the lexicographically smallest valid order. What changes, and what does it cost?
Complexity derivation
Replace the FIFO queue with a min-heap; the bound becomes O(V log V + E)
Every node in the ready set is legal to place, so choosing the smallest one at each step is greedy and safe — no later choice can be blocked by taking a smaller node now. Swapping the queue for a min-heap makes each placement O(log V) instead of O(1), giving O(V log V + E). It is the standard variant, and recognising that the tie-break is a free choice is what makes it an easy change rather than a rewrite.
Sorting n items needs Ω(n log n) comparisons. Why does topological sort escape that lower bound?
Complexity derivation
It never compares two nodes — the edges supply the order directly, so the bound does not apply
The Ω(n log n) bound applies to algorithms whose only access to the ordering is a pairwise comparison, because each comparison yields one bit and n! orders need log(n!) bits. Kahn’s is handed the ordering as data — every edge is a constraint stated outright — so it only has to propagate what it was told. That is the same reason counting sort beats the bound, and it is the cleanest way to answer “why is this linear when it is called a sort?”.
The DFS formulation emits nodes as their frames finish, reversed. When is it preferable?
Comparison
When you are already inside a DFS — it needs no indegree table and detects cycles via back edges
Both run in O(V + E) and both detect cycles, so the choice is about context rather than cost. The DFS version is a few lines bolted onto a traversal you may already be writing, and its cycle evidence is a back edge — a node still on the stack. Kahn’s advantage is operational: it emits nodes in executable order as it goes, which is what a scheduler feeding a thread pool actually needs, whereas DFS only knows the answer once the whole traversal is done and reversed.
A node’s badge reads 2. What exactly does that number count?
Invariant identification
Prerequisites not yet placed — incoming edges whose source is still unordered
The badge starts as the raw indegree and then counts down, one decrement each time a source of an incoming edge is placed. Zero means every prerequisite is already in the output, which is exactly the condition for being legal to place next. Counting *unplaced* prerequisites rather than total incoming edges is what makes "badge is zero" and "ready" the same statement.
See it run — Placing A drops L’s badge from 2 to 1 — one prerequisite cleared, one still blocking.
Why does "the queue is empty but nodes remain" prove a cycle, rather than merely suggesting one?
Invariant identification
The queue holds every legal move, so an empty queue means every leftover node has an unplaced prerequisite
The queue invariant is an equality, not an inclusion: it holds *exactly* the unplaced nodes with no unplaced prerequisites. So when it drains, no legal placement remains anywhere, and every leftover node is waiting on another leftover. Follow those waiting-on edges backwards through a finite set and you must revisit a node — which is a cycle, proven rather than guessed.
Given that, what does Kahn’s return on a cyclic graph if you forget the count check?
Edge case reasoning
A valid order of the acyclic part, which looks correct and silently omits the cyclic nodes
The nodes on and downstream of a cycle never reach indegree zero, so they are simply never emitted, while everything else is ordered perfectly legally. Without the `placed === V` test you get a plausible partial order and no error — which turns the standard cycle detector into a cycle concealer. Prism runs the check and marks the stragglers rejected, so completeness is visible rather than assumed.
See it run — All 12 nodes placed, so the count check passes — the DAG preset is acyclic by construction, and never strands anything.
An implementation seeds the queue with the first zero-indegree node it finds instead of all of them. What happens?
Code diagnosis
Other sources are never placed, so the count falls short and a cycle is reported on an acyclic graph
Zero-indegree means no incoming edge exists, so nothing will ever decrement that node into readiness — the only chance is the initial seeding pass. Miss a source and its entire downstream subgraph stays blocked, the placement count comes up short, and the completeness test reports a cycle that is not there. It passes every connected single-source test and fails on forest-shaped dependency graphs, which is what most real ones are.
Placing a node decrements the indegree of its *predecessors* instead of its successors. What is the symptom?
Code diagnosis
It terminates and returns an order that violates dependencies, because the wrong counters cleared
Placing `A` means every edge *out of* `A` is now satisfied, so the counters that shrink belong to the nodes `A` points at. Decrementing the other way clears constraints that were never met, admitting nodes to the queue before their real prerequisites are placed. The run finishes, the count often matches V, and the order is quietly wrong — the worst failure mode available, and the reason the invariant is worth stating in words before writing the loop.
The ready queue holds [B, C]. Which node must be placed next?
Trace prediction
Either is legal; this implementation takes B because the queue is first-in, first-out
Every node in the ready set has all its prerequisites placed, so any of them is a legal next step — that is what indegree zero means. Prism serves them FIFO, so B goes first, but a min-heap would give the lexicographically smallest order and a random pick would give a different valid one. "The topological sort" is almost always "a topological sort", and the count of valid orders multiplies every time the queue holds more than one node.
See it run — Two nodes are ready at once — the first branch point where the output order stops being forced.
When does a DAG have exactly one valid topological order?
Edge case reasoning
When the ready queue never holds two nodes at once — equivalently, when a Hamiltonian path exists
Two nodes in the ready set at the same moment means two different orders, so uniqueness requires the queue to hold exactly one node at every step. That forces a total order on the nodes, which is precisely a path visiting every node once — a Hamiltonian path. It is the cleanest answer to "why might two runs give different orders", and it turns a vague ties argument into a structural condition.
The dependency graph is two unrelated clusters. Does Kahn’s need a separate outer loop?
Edge case reasoning
No — every source of every cluster is seeded up front, so all components are ordered in one run
This is the payoff for seeding *every* zero-indegree node rather than one: disconnected components are handled without noticing they are disconnected. The two clusters interleave in the output in whatever order the queue produces, which is legal because no edge relates them. It is the one place where Kahn’s is structurally simpler than a traversal-based approach, which does need the outer loop.
A variant checks `indegree <= 0` after decrementing instead of `indegree === 0`. What can go wrong?
Code diagnosis
A node with several incoming edges is enqueued once per remaining edge and placed multiple times
A node must enter the ready set exactly once, at the moment its counter first touches zero. Testing `<= 0` after each decrement re-admits it every time a further edge is cleared, so it appears repeatedly in the output and its own successors are decremented too many times. The equality test is not stylistic — it is what makes "enqueued once" true.
See it run — B joins the ready queue in the same breath its badge first reads zero — once, and never again.
Kahn’s uses a queue like BFS. What is the substantive difference?
Comparison
BFS enqueues on first discovery; Kahn’s enqueues only when every incoming edge has been cleared
The container is the same and the admission rule is not, which is the whole difference. BFS admits a node the first time any edge reaches it, giving shortest distances; Kahn’s admits a node only when the *last* edge into it is cleared, giving a legal execution order. Seen that way, topological sort is BFS with a counter guarding the door.
A build system runs tasks in parallel. What does the ready queue mean there, and what does the order cost you?
Trade-off & selection
Everything in the ready set can run at once, so serialising it into one order throws away the parallelism
A linear topological order is one valid schedule for one worker; the ready set is the strictly richer object, because every node in it is runnable right now. Feeding that set to a thread pool and decrementing as each task reports done is exactly how `make -j` and cargo schedule work. Python’s `graphlib.TopologicalSorter` exposes this directly with `get_ready()` and `done()`, and naming it is a strong signal that you have used the algorithm rather than only recited it.
You only need to know whether a directed graph has a cycle. Is Kahn’s the right tool?
Trade-off & selection
It works and costs O(V + E), but a DFS with an on-stack check answers it without an indegree table
Both approaches are O(V + E) and both are correct, so the choice comes down to what you already have and what you want out. Kahn’s needs an indegree table and a queue, and it hands you an execution order as a bonus; DFS needs only a colour array and reports which nodes form the cycle, which is what an error message wants. If the answer is a yes-or-no and you are already traversing, DFS is the lighter tool.
One node has an edge to itself. What does Kahn’s do?
Trade-off & selection
It reports a cycle — the node’s indegree includes its own edge and can never reach zero
A self-loop is a cycle of length one, and the counting machinery handles it without a special case: the node needs itself placed before it can be placed. It never joins the ready set, the count falls short, and the completeness test reports the cycle. That is the right answer for a build system too — a target that depends on itself genuinely cannot be built.
Explain topological sort to someone who has never programmed. Say it out loud before revealing.
Explain it plainly
Think about getting dressed. Socks before shoes, shirt before jacket — but socks versus shirt, there is no rule at all, either way round is fine. Here is the method: for each item, count how many things must go on before it. Anything at zero can go on right now, so pile those up as your ready list. Put on any item from the ready list, and for everything that was waiting on it, knock its count down by one; anything that hits zero joins the ready list. Keep going until the ready list is empty. If you are dressed, that sequence was a legal order. If the list ran dry while you were still half-dressed, the leftovers are waiting on each other in a loop — your belt needs your trousers which need your belt — and no order exists at all, which is exactly what a build tool means by "circular dependency". Two places the picture misleads: mornings feel like there is one right order, but there are usually many, and any item on the ready list is as legal as any other. And nothing here is clever about *choosing* — it never picks the item that unblocks the most work, it just takes whatever is ready.
The test is whether the listener grasps both outputs — an order, or a proof that no order exists. A strong answer conveys the counting mechanism without jargon and volunteers that the order is usually not unique, which is the follow-up interviewers reach for.