# Topological Sort in Coding Interviews: Kahn's Algorithm Explained Problems like **Course Schedule (LeetCode 207/210)**, **Alien Dictionary** and build-order questions are all the same idea: you have tasks with "must happen before" rules, and you need a valid order (or proof that none exists). ## The idea in one sentence Repeatedly take a node with **no remaining prerequisites** (in-degree 0), output it, and remove its outgoing edges. ## Python template (Kahn's algorithm) ```python from collections import deque, defaultdict def topo_order(n, edges): # edges: (before, after) graph = defaultdict(list) indeg = [0] * n for a, b in edges: 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 ``` Time O(V + E), space O(V + E). ## What to say out loud - "I'll model this as a directed graph where an edge means *must come before*." - "If I can't output every node, some nodes are stuck waiting on each other, so there is a cycle." - Mention the alternative: DFS with three colours (unvisited / visiting / done) detects cycles too, and the reverse post-order is a valid topological order. ## Common follow-ups 1. **Lexicographically smallest order?** Swap the deque for a min-heap. 2. **Minimum number of semesters?** Process the queue level by level and count levels (LeetCode 1136). 3. **Alien Dictionary**: build edges by comparing the first differing character of adjacent words, and watch for the invalid case where a longer word comes before its own prefix. ## Mistakes interviewers notice - Building the edge in the wrong direction (prerequisite → course, not the reverse). - Forgetting isolated nodes that have no edges at all. - Returning a partial order instead of reporting the cycle. --- *Disclosure: I'm part of the team behind [Linkjob AI](https://www.linkjob.ai/), an AI interview assistant. These notes are free to use for practice.*