Topological Kahn (Practice 4371): Cheat

📅 2026-11-07T22:27:27.513Z
👁️ 70 katselukertaa
🔓 Julkinen


# Topological Kahn (Practice 4371): Cheat Sheet

Interviewers love topological kahn because it checks whether you can state the invariant before coding. Here is a compact rehearsal note.

## Approach

Indegree queue; pop zeros and decrement neighbors.

```python
from collections import deque
def topo(n, edges):
    g = [[] for _ in range(n)]; indeg = [0]*n
    for u, v in edges: g[u].append(v); indeg[v] += 1
    q = deque([i for i in range(n) if indeg[i] == 0]); order = []
    while q:
        u = q.popleft(); order.append(u)
        for v in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0: q.append(v)
    return order if len(order) == n else []
```

## Complexity

Linear in the dominant input size for the scan; heap/tree variants add a log factor.

## Interview pitfalls

State the invariant out loud, name the complexity, then code. Skipping the invariant is the usual fail mode.

## Practicing out loud

Narrate the approach, complexity and one edge case in under a minute. Disclosure: I work on Linkjob AI, a real-time interview assistant. If you want live practice help, see [Linkjob AI interview assistant](https://www.linkjob.ai/).