Every engineer has felt topological sort without naming it: build systems compiling modules in dependency order, package managers resolving installs, course prerequisites deciding what you can take next semester. Interviewers love the Topological Sort pattern for exactly that reason — it is a real-world algorithm disguised as a puzzle, and it appears reliably in Google, Amazon, and Meta rounds. Yet most candidates prepare BFS and DFS in isolation and freeze when a problem hides its graph behind the word “prerequisites.”
This guide shows you how to spot the pattern, the Kahn’s algorithm template worth memorizing, how cycle detection falls out for free, and the classic problems to drill before your next onsite.
What Is Topological Sort?
A topological order is a linear arrangement of the nodes of a directed acyclic graph (DAG) such that every edge points forward: if task A must happen before task B, A appears earlier in the order. Two facts drive every interview question. First, a topological order exists if and only if the graph has no cycle. Second, when multiple valid orders exist, the problem may ask for any one, a specific one (lexicographically smallest), or simply whether one exists — read the question carefully, because those are three different amounts of work.
How to Spot It in a Problem Statement
The graph is almost never handed to you. Instead you get pairs with a before/after relationship: course prerequisites, job dependencies, characters ordered by an alien dictionary, recipes requiring ingredients. The signal phrases are “must be taken before,” “depends on,” “build order,” and “is it possible to finish.” When you see them, say it out loud: “These pairwise constraints form a directed graph, and the question is whether a topological order exists — I’ll use Kahn’s algorithm.” Naming the model in one sentence is the strongest opening move available in a graph interview.
The Java Template: Kahn’s Algorithm (BFS)
public int[] findOrder(int numCourses, int[][] prerequisites) {
List<List<Integer>> adj = new ArrayList<>();
int[] indegree = new int[numCourses];
for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
for (int[] p : prerequisites) { // p[1] -> p[0]
adj.get(p[1]).add(p[0]);
indegree[p[0]]++;
}
Deque<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < numCourses; i++)
if (indegree[i] == 0) queue.offer(i);
int[] order = new int[numCourses];
int idx = 0;
while (!queue.isEmpty()) {
int cur = queue.poll();
order[idx++] = cur;
for (int next : adj.get(cur))
if (--indegree[next] == 0) queue.offer(next);
}
return idx == numCourses ? order : new int[0]; // cycle check
}The logic reads like the real world: repeatedly pick any task with no outstanding prerequisites (indegree zero), do it, and cross it off everyone else’s list. Complexity is O(V + E) time and space — state that before you code.
Cycle Detection Comes Free
The final line is the part interviewers probe. If a cycle exists, the nodes inside it never reach indegree zero, so they never enter the queue and idx falls short of numCourses. One comparison answers “can all courses be finished?” — no separate cycle-detection pass needed. If you are asked for the DFS alternative, sketch it honestly: three-state coloring (unvisited, in-progress, done), where meeting an in-progress node means a cycle, and the reverse of the finish order is the topological order. Know both, lead with Kahn’s — the iterative version avoids stack-overflow questions and is easier to reason about under pressure.
Four Classic Problems to Practice
1. Course Schedule (LeetCode 207)
The canonical yes/no form: can all courses be completed? It is the template minus the order array. If this takes you more than ten minutes, drill the template again before moving on.
2. Course Schedule II (LeetCode 210)
Return an actual valid order — exactly the template above. The pair 207/210 is the single most common topological sort ask at Amazon phone screens.
3. Alien Dictionary (LeetCode 269)
The senior-level staple. Given words sorted in an unknown alphabet, recover the letter order. The topological sort is the easy half; the real test is building the graph — comparing adjacent words, finding the first differing character, and catching the invalid case where a word is a prefix’s longer form ordered first. It measures whether you can construct a graph from raw data, which is the actual senior signal.
4. Minimum Height Trees (LeetCode 310)
Not a DAG problem at all — but the solution repeatedly strips leaves (degree-one nodes) layer by layer, the undirected cousin of Kahn’s peeling. Solving it teaches you to see indegree-peeling as a general technique rather than a memorized ritual.
How to Present It in the Interview
Structure the walkthrough deliberately. First, translate the story into a graph and state the direction convention — mixing up edge direction is the most common unforced error in this pattern, so write the comment // prerequisite -> dependent before anything else. Second, state O(V + E) up front. Third, code the template cleanly, then walk one small example including a cycle, showing the count falling short. Expect the standard follow-ups: “What if you need the lexicographically smallest order?” (swap the queue for a min-heap, O(V log V + E)) and “How would you parallelize the schedule?” (each BFS layer is a batch of tasks that can run concurrently — a beautiful answer that takes one sentence).
Your One-Week Practice Plan
Days 1–2: write Kahn’s template from memory daily and solve Course Schedule 207 and 210. Days 3–4: Find Eventual Safe States (LeetCode 802) with the DFS coloring method, so both approaches are live. Days 5–6: Alien Dictionary, focusing on graph construction and the edge cases. Day 7: Minimum Height Trees under a 35-minute timer, narrating your reasoning out loud the entire time — verbal fluency under pressure is a separate skill from solving, and it is the one that decides offers.
Topological sort rewards preparation more than almost any graph topic: one template, one cycle-check trick, and a small set of variants that all rhyme. Rehearsing your out-loud delivery matters as much as the code — tools like Niraswa AI can help you practice under realistic conditions. Start now: write Kahn’s algorithm from memory before you close this tab.
