topological-sort.md
· 2.2 KiB · Markdown
Sin formato
# 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.*
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)
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
- Lexicographically smallest order? Swap the deque for a min-heap.
- Minimum number of semesters? Process the queue level by level and count levels (LeetCode 1136).
- 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, an AI interview assistant. These notes are free to use for practice.