Topological Sort Practice Questions
Ten interview classics, both algorithms represented. Each problem is a direct application of Kahn’s or DFS topological sort, or one of the standard variations from the applications page — once you spot the shape, the code writes itself.
Before reading any solution, force yourself through the four-question checklist:
- What’s the graph? (Nodes? Edges? Edge direction?)
- Which algorithm? (Kahn’s for “any/lex-smallest/rounds”; DFS for “report cycle / longest path”.)
- What’s the return value? (Boolean? List? Number?)
- What’s the cycle case? (Return false / empty / -1?)
The code is a 20-line transcription of those four answers. If you can answer them, you’ve solved the problem.
Easy
| Problem | Pattern | Status |
|---|---|---|
| Course Schedule | Kahn’s count-check / cycle detection | Available |
| Find Eventual Safe States | Reverse-graph Kahn’s, or three-color DFS | Available |
Medium
| Problem | Pattern | Status |
|---|---|---|
| Course Schedule II | Kahn’s, return the order | Available |
| Minimum Height Trees | Iterated leaf-stripping (Kahn’s on undirected graph) | Available |
| Parallel Courses | Kahn’s-with-rounds | Available |
| Loud and Rich | DFS with memoization on a DAG | Available |
| Sequence Reconstruction | Kahn’s with uniqueness check | Available |
| Longest Increasing Path in a Matrix | DFS + memoization (a DAG induced on grid cells) | Available |
Hard
| Problem | Pattern | Status |
|---|---|---|
| Alien Dictionary | Build the precedence DAG from word pairs, then topo | Available |
| Build a Matrix with Conditions | Two independent topo sorts (rows, cols) | Available |
More Practice (Coming Soon)
| Problem | Pattern | Status |
|---|---|---|
| All Ancestors of a Node | BFS/DFS from each node on reversed graph | Coming Soon |
| Reconstruct Itinerary | Eulerian path (Hierholzer’s), not pure topo | Coming Soon |
| Course Schedule IV | Transitive closure via topo + DP | Coming Soon |
| Minimum Number of Days to Eat N Oranges | DP, not topo, but interesting cousin | Coming Soon |
| Find All Possible Recipes from Given Supplies | Kahn’s on recipe graph | Coming Soon |
| Sort Items by Groups Respecting Dependencies | Two-layer topo sort (groups + items) | Coming Soon |
| Number of Different Subsequences GCDs | Math, not topo, but listed for completeness | Coming Soon |
| Strongly Connected Components (Tarjan / Kosaraju) | DFS, generalization of cycle detection | Coming Soon |
| Minimum Reorder to Make All Paths Lead to Zero | BFS on a tree, related “edge direction” topic | Coming Soon |
| Cracking the Safe | Eulerian path on de Bruijn graph | Coming Soon |