If you can recognize when a problem is secretly a dependency graph, topological sort becomes one of the highest-leverage patterns to drill before an interview. The core skill is spotting the signal ("finish X before Y", "build order", "prerequisites") and then reaching for Kahn's algorithm (BFS with in-degree counting) or DFS post-order. Both run in O(V + E) time, both detect cycles for free, and together they cover the vast majority of topological sort interview questions. This guide breaks down when the pattern applies, the two implementations you must have memorized, and the specific problems worth practicing.
When a problem is actually topological sort
Topological sort produces a linear ordering of the nodes in a directed acyclic graph such that for every edge u to v, u comes before v. The moment a problem mentions ordering under constraints, you should test whether it maps to a DAG.
The trigger phrases we hear engineers talk through in mock interviews:
- "You must take course A before course B" (prerequisites)
- "Task X depends on tasks Y and Z finishing first" (build systems, job scheduling)
- "Given a partial order, produce a valid full order" (alien dictionary, custom sort)
- "Detect whether the dependencies contain a cycle" (deadlock detection)
The catch: topological sort only exists if the graph is a DAG. If there is a cycle, no valid ordering exists, and half the interview problems in this space are really asking you to detect that cycle. This is why cycle detection and topological sort are the same muscle. Kahn's algorithm, for example, reports a cycle when it cannot output all V nodes.
A quick decision test we recommend: draw the dependencies as arrows. If the answer is "an order" or "is an order even possible," you are almost certainly looking at topological sort.
The two implementations to memorize
You need both because interviewers probe for both, and each shines in different follow-ups.
Kahn's algorithm (BFS, in-degree)
Compute the in-degree of every node, seed a queue with all zero in-degree nodes, and repeatedly pop a node, append it to the order, and decrement its neighbors. When a neighbor's in-degree hits zero, enqueue it.
from collections import deque
def topo_sort(n, edges):
graph = [[] for _ in range(n)]
indegree = [0] * n
for u, v in edges: # edge u -> v
graph[u].append(v)
indegree[v] += 1
queue = deque(i for i in range(n) if indegree[i] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for nxt in graph[node]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
return order if len(order) == n else [] # empty => cycle
Kahn's algorithm is the one we recommend leading with. The time complexity of Kahn's topological sort algorithm is O(V + E), where V and E are the total number of vertices and edges in the graph. It is easy to explain, the cycle check is a single length comparison, and it generalizes cleanly to "process nodes in levels," which matters for parallel scheduling problems.
DFS post-order
Run DFS, and after visiting all descendants of a node, push it onto a stack. Reverse the stack at the end. Use a three-color marking (unvisited, in-progress, done) so that hitting an in-progress node signals a back edge, which means a cycle.
DFS is often shorter to write, but the cycle detection logic is easier to get wrong under pressure. If you only have time to be bulletproof on one, make it Kahn's.
Both approaches share the same asymptotic cost. The time complexity of topological sort is O(V + E), where V is the number of vertices and E is the number of edges; in a DFS-based approach, each vertex is visited once and each directed edge is explored once.
Problems worth practicing, from easy to hard
Here is how we would sequence practice using problems from our own question bank. The progression matters more than volume: most candidates over-index on obscure variants and under-practice explaining the base pattern out loud.
| Problem | Level | What it drills |
|---|---|---|
| Loud and Rich | mid-senior | Building a DAG from comparisons, propagating a min over predecessors |
| Minimum Height Trees | mid-senior | Peeling leaves layer by layer (topological sort on an undirected tree) |
| Parallel Courses III | staff | Longest path in a DAG via Kahn's plus DP on completion times |
| Largest Color Value in a Directed Graph | staff | Cycle detection combined with per-color counts during the sort |
| Number of Increasing Paths in a Grid | staff | Implicit DAG where edges are defined by cell values |
| Count Visited Nodes in a Directed Graph | staff | Functional graph where each node has one out-edge, finding cycles |
Start with Loud and Rich. It is the cleanest example of the "translate constraints into a graph, then relax values in topological order" idea, and the graph is handed to you directly.
Then do Minimum Height Trees, which teaches the most non-obvious variant: topological sort on an undirected graph. You do not literally sort here; you repeatedly strip degree-one leaves until one or two nodes remain. Recognizing that leaf-peeling is the same in-degree machinery is exactly the kind of insight interviewers reward.
Parallel Courses III is where the pattern earns its keep at the staff level. It layers dynamic programming on top of the sort: as you process each course in topological order, you compute the earliest finish time as the course's own time plus the max over its prerequisites. This "longest path in a DAG" formulation shows up constantly in scheduling questions, and it is a natural bridge if you have already worked through our dynamic programming framework.
Largest Color Value in a Directed Graph is the best single problem for practicing cycle-detection-as-part-of-the-answer. If Kahn's algorithm cannot emit all nodes, you return -1. Otherwise you carry a color-frequency table forward through the traversal. It forces you to combine two ideas in one pass.
Finish with Count Visited Nodes in a Directed Graph, which looks like topological sort but is really a functional graph (every node has exactly one outgoing edge). It teaches you the limits of the pattern: when every node has an out-edge, cycles are guaranteed somewhere, so pure topological sort will not consume the whole graph, and you need to reason about the cycle each node eventually falls into.
Where it shows up by company
Dependency ordering, build systems, and package managers are real infrastructure, so this pattern is common at companies with large internal tooling. Course-schedule-style questions and their variants come up frequently in graph rounds at Google, Amazon, and Meta. In our mock interviews, the failure mode is rarely the algorithm itself. It is candidates who jump into code before confirming the graph is directed, before deciding what a cycle means for the answer, and before stating which node maps to a vertex. Spend the first two minutes on that framing and the implementation writes itself.
How to talk through it in the room
State the reduction explicitly: "This is a dependency ordering, so I will model it as a directed graph and run a topological sort." Name your cycle policy up front. Then narrate in-degree setup, the queue, and the terminal check. When you finish, volunteer the complexity (O(V + E) time and O(V + E) space for the adjacency structure) without being asked. Interviewers read that as fluency, not showing off.
The most common follow-ups: "What if there are multiple valid orderings?" (any is fine unless lexicographic order is required, in which case swap the queue for a heap), "How do you detect a cycle?" (Kahn's length check or DFS gray-node), and "Can you do it in parallel?" (yes, each Kahn's layer can run concurrently). Have a one-line answer ready for each.
FAQ
Should I use Kahn's algorithm or DFS in an interview?
Default to Kahn's algorithm. The in-degree queue is easier to explain, the cycle check is a trivial length comparison, and it maps naturally to level-by-level and lexicographic variants. Learn DFS post-order as a backup, especially if the interviewer explicitly asks for a recursive solution.
How does topological sort detect a cycle?
With Kahn's algorithm, if the output ordering contains fewer than V nodes, the remaining nodes are stuck in a cycle because their in-degree never reached zero. With DFS, you mark nodes in-progress and detect a back edge when you reach an in-progress node again. Both are O(V + E).
Does topological sort work on undirected graphs?
Not directly, because "before and after" needs edge direction. But a related leaf-peeling technique works on trees, as in Minimum Height Trees, where you repeatedly remove degree-one nodes. Recognizing that variant is a common interview curveball.
What is the time complexity of topological sort?
Both Kahn's algorithm and DFS run in O(V + E) time, where V is the number of vertices and E is the number of edges. Space is O(V + E) for the adjacency list plus O(V) for the in-degree array or recursion stack.
Is topological sort the same as a regular sort?
No. There is no comparison of values. You are ordering nodes to respect directed edges (partial order), and there can be many valid results. A comparison sort produces a single total order based on element values.