Home / Blog / Topological Sort Interview Pattern

Topological Sort Interview Pattern

Published 2026-10-12 · Luna Interview

When a problem says “prerequisites,” “build order,” or “tasks with dependencies,” you are usually looking at a directed acyclic graph—and the topological sort interview pattern. The skill is recognizing the pattern quickly, detecting cycles, and implementing either Kahn’s algorithm (BFS/ indegrees) or a DFS-based order without confusing the edge direction.

The 10-second recognition

Cues:

• You must order items so every dependency comes before dependents
• Edges mean “A must happen before B” or “A is a prerequisite of B”
• The answer is an order, a boolean “possible?”, or counts of valid sequences
• There might be multiple valid orders; any one may be fine unless asked otherwise

Talk track:

“I’ll model this as a directed graph. If it’s a DAG, a topological order exists. I’ll use Kahn’s algorithm with indegrees so cycle detection is natural: if we can’t process all nodes, there’s a cycle.”

Clarify edge direction first

This is the #1 interview bug. Ask:

“Does an edge u → v mean u is a prerequisite of v (u before v)?”

Draw one tiny example on the board. Wrong direction produces a confidently wrong order.

Kahn’s algorithm (default for interviews)

1. Build adjacency list and indegree array/map
2. Push all zero-indegree nodes into a queue
3. Pop, append to order, decrement neighbors’ indegrees
4. Push neighbors that hit zero
5. If order size < n → cycle → impossible

from collections import deque, defaultdict

def topo_kahn(n, edges):
    graph = defaultdict(list)
    indeg = [0] * n
    for u, v in edges:  # u before v
        graph[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 graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else []  # empty => cycle

Complexity: O(V + E). Say it once.

DFS-based topological sort

• Recurse on dependents first; append node on the way out (post-order)
• Reverse the post-order list—or push onto a stack and pop
• Use colors (white/gray/black) to detect cycles: hitting gray means back edge

Talk track:

“DFS post-order gives a reverse topo if I finish children before I record the node. Gray nodes detect cycles.”

Prefer Kahn in interviews when the prompt emphasizes “is it possible?”—the leftover nodes story is easy to explain.

Pattern variants candidates commonly see

For “minimum number of terms,” process Kahn in layers: each wave is one parallel step.

Failure modes

• Reversed edges
• Forgetting nodes with no edges (still in the order)
• Using undirected thinking on a directed problem
• Claiming uniqueness when multiple topos exist
• Skipping cycle detection when the prompt allows contradictions

Complexity and follow-ups

Be ready for:

• “What if new edges arrive online?” → incremental indegrees / dynamic structures (verbal is enough)
• “Count the number of topological orders?” → usually harder; often DP on subsets for small n—say when it becomes exponential
• “Any order vs lexicographically smallest?” → use a min-heap instead of a queue in Kahn

Practice plan

Worked mini-example (say it aloud)

Nodes 0..3, edges 0→1, 0→2, 1→3, 2→3:

• Indegrees: [0,1,1,2]
• Queue starts with [0]
• Process 0 → push 1,2
• Process 1 and 2 → 3’s indegree hits 0 → push 3
• Order example: 0,1,2,3 (1 and 2 may swap)

If an edge 3→0 existed, you would stall with nodes left—report impossible.

Alien dictionary sketch

Characters are nodes; a wrong lexicographic contradiction means a cycle. Build edges from adjacent word pairs, then Kahn. If words violate prefix rules (longer word before shorter prefix), reject before topo.

Talk track:

“I’ll derive letter edges from sorted word pairs, then topo-sort. Cycle or invalid prefix → no ordering.”

Soft practice note

Topo problems punish silent edge-direction mistakes. If you want timed rehearsal of the “model → indegree → Kahn → cycle” talk track, Luna Interview is built for calm structured practice—not for anything that breaks interview rules.

Day-of checklist

• [ ] Edge meaning confirmed with an example
• [ ] Indegrees initialized for all nodes
• [ ] Zero-indegree seeds queued
• [ ] Cycle rule: processed count vs n
• [ ] Complexity stated
• [ ] Dry-run on a 3–4 node graph

When the prompt is dependencies, reach for topological sort on purpose—then prove the graph is a DAG while you build the order.

Rehearse with an AI interview copilot, then browse commonly reported interview questions.