Micro-questions over the topological sort module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. The idea
1. What is a topological order?
Answer
A linear list where every prerequisite node comes before every node that depends on it — equivalently, an arrangement in which every edge points forwards.
2. Give the getting-dressed illustration.
Answer
Underwear → Pants → Shoes, and Socks → Shoes. You cannot put shoes on before socks and pants, nor pants before underwear.
3. Give two valid orderings for that graph.
Answer
[Underwear, Socks, Pants, Shoes] and [Socks, Underwear, Pants, Shoes].
4. What does that show?
Answer
A graph can have multiple valid topological orderings. Where the constraints do not order two tasks, either may come first.
5. Name four production applications.
Answer
Build systems (Make, Bazel, Webpack), package managers (npm, pip, cargo), university course registration around prerequisites, and spreadsheet recalculation engines.
B. The vocabulary
6. What is a DAG?
Answer
A directed acyclic graph — directed edges with no circular loops. A prerequisites flowchart.
7. What is in-degree, in plain terms?
Answer
The number of incoming directed edges pointing into a node — the number of uncompleted prerequisites a course has.
8. Why does a cycle make topological ordering impossible?
Answer
Each vertex on the cycle would have to come before itself. Circular reasoning deadlocks.
9. What kind of graph does topological sort require?
Answer
Directed and acyclic. Both conditions — it is meaningless on an undirected graph and impossible with a cycle.
C. Kahn’s algorithm
10. Give Kahn’s algorithm in six steps.
Answer
- Compute the in-degree of every vertex.
- Push all vertices with
in_degree == 0into a FIFO queue. - Pop
u, append it to the order. - For every neighbour
vofu, decrementin_degree[v]. - If
in_degree[v]hits 0, pushv. - Repeat until the queue is empty.
11. What does in_degree == 0 mean semantically?
Answer
Every prerequisite of that task is already done, so it is safe to do now.
12. Why does decrementing on the way out model “completing” a task?
Answer
Emitting u means u is finished, so each dependent of u now has one fewer outstanding prerequisite.
13. State the cycle detection guarantee.
Answer
If len(topological_order) < V, a cycle exists. Circular dependencies prevent in-degrees from ever reaching 0, so those vertices never enter the queue.
14. Does Kahn’s algorithm need a separate cycle-detection pass?
Answer
No — the length check is the cycle test, and it costs nothing extra.
15. Kahn’s uses a queue. Does it have to?
Answer
No — any container works, and the choice only changes which valid order you get. A min-heap gives the lexicographically smallest topological order, which is what problems asking for a deterministic answer want.
D. The DFS alternative
16. How does the DFS variant produce a topological order?
Answer
Run DFS and push each vertex onto a list when it finishes; reverse the list at the end. Equivalently, sort by decreasing finish time.
17. Why does decreasing finish time work?
Answer
A vertex finishes only after everything reachable from it has finished, so anything it points to already has a smaller finish time and therefore lands later in the reversed list.
18. How does the DFS variant detect a cycle?
Answer
It looks for a back edge — an edge to a grey (still-open) vertex. A directed graph is a DAG iff DFS produces no back edges. See edge classification.
19. Which variant would you reach for, and why?
Answer
Kahn’s, usually — it is iterative (no recursion limit), the cycle check is a length comparison, and the queue can be swapped for a heap to control ties. The DFS variant is neater when you already need finish times for something else.
E. Costs
20. Time complexity, and why?
Answer
— every vertex is enqueued once and every directed edge is decremented once.
21. Space complexity, and what makes it up?
Answer
— the adjacency list is , plus the in-degree array and queue at .
F. Traps
22. What happens if you flip the edge direction?
Answer
You get the reverse topological order. Be precise about which way dependency points — u → v here means “u must happen before v”.
23. Why must you never assert a single fixed output array in a test?
Answer
Multiple valid orders usually exist. Assert the property instead: for every edge u → v, u appears before v.
24. What is the one check you must always perform?
Answer
len(order) == num_nodes. Without it, a cyclic graph silently returns a partial order that looks plausible.
25. Summarise topological sort in one sentence.
Answer
Repeatedly emit whatever has no remaining prerequisites — , with cycle detection falling out of the count for free.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Topological Sort — the module
- Edge Classification — Question Bank — why the DFS variant is correct
- Paths, Cycles and Connectivity — Question Bank — what a DAG is
Software engineering
Infrastructure & security
Computer science
Hardware & engineering