Topological Sort in Coding Interviews: Course Schedule and Beyond

Topological sort orders the nodes of a directed graph so that every edge points forward: if task A must happen before task B, A appears earlier in the result. It sounds academic, but it is the engine behind build systems, package managers, spreadsheet recalculation, and a well-known group of interview questions. If a problem mentions prerequisites, dependencies, or "order of tasks", topological sort should be one of your first ideas. When does a topological order exist? Only when the graph has no cycles, i.e. it is a DAG (directed acyclic graph). If course A requires B and B requires A, no valid order exists. Most interview problems really ask two things at once: is there a cycle, and if not, what is one valid order? Approach 1: Kahn's algorithm (BFS with in-degrees) from collections import deque def topo_sort(n, edges): graph = [[] for _ in range(n)] indeg = [0] * n for a, b in edges: # a must come before b graph[a].append(b) indeg[b] += 1 q = deque(i for i in range(n) if indeg[i] == 0) order = [] while q: node = q.popleft() order.append(node) for nxt in graph[node]: indeg[nxt] -= 1 if indeg[nxt] == 0: q.append(nxt) return order if len(order) == n else [] # [] means a cycle Kahn's algorithm is easy to explain: repeatedly take any task with no remaining prerequisites. If you finish with fewer than n nodes, the leftover nodes are stuck in a cycle. Approach 2: DFS with three colors Mark nodes as unvisited, visiting, or done. Run DFS; when a node finishes, push it onto a list. Reverse the list at the end. If you ever reach a node that is still "visiting", you have found a back edge, which means a cycle. This version is handy when you also need to report the cycle itself. Classic problems 1. Course Schedule: can you finish all courses? Run Kahn's algorithm and check whether the order includes every course. 2. Course Schedule II: return one valid order, the same code returning the list. 3. Alien Dictionary: compare adjacent words to derive letter-ordering edges, then topologically sort the letters. Watch for the invalid case where a longer word appears before its own prefix. 4. Parallel Courses / minimum semesters: process Kahn's algorithm level by level; the number of BFS layers is the answer. 5. Build order / task scheduling with dependencies: identical structure with different names. Complexity Both approaches run in O(V + E) time and O(V + E) space for the adjacency list. Say this out loud, and mention that each edge is examined exactly once. Common mistakes - Reversing the edge direction. Decide explicitly whether [a, b] means "a before b" or "b before a" and write it as a comment. - Forgetting isolated nodes that have no edges; they still belong in the output. - Returning a partial order without detecting the cycle. How to talk through it Start by modeling: "Each course is a node and each prerequisite is a directed edge." Then name the algorithm and the cycle check before coding. Interviewers reward candidates who connect the story (dependencies) to the structure (DAG) quickly. Staying calm enough to narrate that modeling step is half the battle. Linkjob AI (https://linkjob.ai) offers real-time help during job interviews and technical interviews, helping you keep your explanation organized while you code. It works best on top of the practice you have already done. Takeaway: prerequisites plus ordering means topological sort, and Kahn's algorithm gives you both the order and the cycle check in one pass.