# Topological Kahn Sort (Practice 5055): Review

Interviewers use this pattern to test whether you can state the invariant before coding. Here is a compact rehearsal note.

## Approach

Emit zero-indegree nodes and decrement neighbors until the graph is emptied or a cycle remains.

```python
from collections import deque
def topo(n,edges):
g=[[] for _ in range(n)];ind=[0]*n
for a,b in edges: g[a].append(b);ind[b]+=1
q=deque(i for i in range(n) if ind[i]==0);out=[]
while q:
u=q.popleft();out.append(u)
for v in g[u]:
ind[v]-=1
if ind[v]==0: q.append(v)
return out if len(out)==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.