Última actividad 5 days ago

Interview prep notes

Revisión 4d947ff82d9bcb2b65df62a206cba7d1755f542d

topological-sort.md 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)

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, an AI interview assistant. These notes are free to use for practice.