Common Patterns
Topological Sort
Ordering tasks with dependencies using Kahn's algorithm and DFS — a pattern that appears whenever problems involve build systems, scheduling, or prerequisites.
The whole workflow in about ten minutes: how to recognize this pattern, drive the AI through Kahn's, handle the cycle traps, and verify the result. Chapters let you skip to whatever you need. The written deep dive is below.
Run pip install pandas and you'll watch it pull down NumPy first, then a dozen smaller things, and only install pandas itself at the end. If pip went in random order, half the imports inside pandas would blow up because their dependencies hadn't loaded yet. So pip figures out an order where nothing gets installed before the things it depends on.
That ordering move has a name: topological sort. The structure underneath is a directed acyclic graph (DAG), a graph where edges have a direction (A points to B, not back) and following the arrows never loops you back to where you started. Topological sort lays the nodes out in a line such that every arrow points forward.
It shows up wherever one thing has to happen "after" another: build systems, course schedulers, task pipelines, spreadsheet recalc. If the name is new to you, that part doesn't matter. What matters is recognizing the dependency-ordering shape when a problem describes it, and being able to steer the AI through the implementation once you do.
Recognizing the pattern
Topological sort problems almost never announce themselves. They arrive dressed up as build systems, task schedulers, dependency installers, course planners, or compilation pipelines, and your job is to see the DAG underneath. The interviewer is watching whether you can name the structure before you start coding.
If you see any of these signals, your pattern-matching instinct should immediately flag topological sort:
- Vocabulary from the problem statement. "Prerequisites," "dependencies," "ordering," "before/after," "must complete first," "blocks." These are giveaways.
- A list of pairs that describe a "must come before" relationship. Course A requires course B. Package X depends on Y. Step 1 must finish before Step 2. Any time the input is a list of these ordered pairs, you're being handed a graph and asked to linearize it.
- A question about feasibility. "Is there an order in which all of these can run?" If the answer might be "no because there's a cycle," topological sort is the right tool — it both produces the order and detects the impossibility.
- A scheduling problem with prerequisites. Parallel task execution, semester planning, build pipelines. The topological order is the scaffolding; the actual answer often involves a second pass on top of it.
Say the pattern out loud when you spot it: "This looks like a dependency graph — I'd model it as a DAG and use topological sort to find a valid ordering." That one sentence tells the interviewer you've identified the pattern, and it gives them confidence you're heading in the right direction.
What is a topological ordering?
Algorithms
Kahn's algorithm (BFS approach)
DFS-based topological sort
Kahn's vs. DFS: when to reach for which
Cycle detection
Common variations you'll encounter
Prompting the AI
Verifying the AI's code
When to use vs. alternatives
What interviewers expect
Putting it together
Purchase Premium to Keep Reading
Unlock this article and so much more with Hello Interview Premium
Reading Progress
On This Page
Recognizing the pattern
What is a topological ordering?
Algorithms
Kahn's algorithm (BFS approach)
DFS-based topological sort
Kahn's vs. DFS: when to reach for which
Cycle detection
Common variations you'll encounter
Prompting the AI
Verifying the AI's code
When to use vs. alternatives
What interviewers expect
Putting it together