Topological Sort Interview Questions for Software Engineers: In-Degree, Cycles, and Build-Order Judgment

Topological sort questions look more abstract than they really are.

They show up as Course Schedule, build-order problems, task pipelines, recipe dependencies, and weird-looking string questions like Alien Dictionary. The surface changes. The invariant does not.

In the current StrongYes corpus, 38 company guides already mention Course Schedule, Course Schedule II, or Alien Dictionary. The local problem-editorial dataset still treats topological sort as a core interview pattern, and as of April 10, 2026, both interviewing.io Topics and NeetCode Core Skills still break Topological Sort out as its own lane instead of burying it inside generic graph prep.

That is the signal: if the prompt is really about dependency order, this is not just "some graph question." It is a topological-sort question.

The miss usually is not coding speed.

It is forgetting to say the contract early enough:

"A node is ready only when all incoming dependencies have been satisfied."

If you can say that out loud before you type, the round gets much calmer.

What interviewers are actually testing

A strong topological-sort answer usually proves five things:

1. You can tell the difference between a generic directed graph and a dependency graph.
2. You know whether the prompt wants a boolean, one valid order, or proof that no order exists.
3. You can say what in-degree, ready, and cycle mean in plain English.
4. You can build the graph correctly even when the constraints are implicit.
5. You can explain the invariant instead of narrating queue operations.

That last point matters more than people think.

Weak candidates say, "I use BFS and a queue."

Strong candidates say, "The queue stores exactly the work whose prerequisites are already satisfied."

That sounds like someone who understands the round, not someone pattern-matched their way into it.

Name the dependency-order variant before you code

The four families below map onto three diagnostic questions. Walk the tree out loud before the keyboard — the terminal tells you what the queue actually contains, what the answer type is, and where the real risk lives.

Diagram

Copy source

Rendering diagram...

Green terminals are mechanical once you say the invariant. Amber means the real work is before the queue even runs. Red means the topological sort is only half the answer — the other half is whatever the prompt layered on top.

The four topological-sort question families that keep repeating

1. Can all the work finish?

This is the family behind:

• Course Schedule
• package-manager dependencies
• build pipelines
• any "can I finish everything?" DAG question

This is the cleanest topological-sort prompt because the interviewer is really asking one thing:

"Does a cycle exist?"

Kahn's algorithm is usually the most interview-friendly answer because it makes the invariant visible. You track how many prerequisites each node still needs, start with the nodes that need zero, and keep unlocking more work.

PYTHON

Copy

from collections import deque def topo_order(num_nodes, edges): graph = {node: [] for node in range(num_nodes)} indegree = [0] * num_nodes for before, after in edges: graph[before].append(after) indegree[after] += 1 queue = deque([node for node in range(num_nodes) if indegree[node] == 0]) order = [] while queue: node = queue.popleft() order.append(node) for neighbor in graph[node]: indegree[neighbor] -= 1 if indegree[neighbor] == 0: queue.append(neighbor) return order if len(order) == num_nodes else []

The sentence to say out loud is:

"The queue stores exactly the nodes whose prerequisites are already satisfied."

If the final order is shorter than num_nodes, you found a cycle. Do not bury that in implementation details. Say it plainly.

2. Give me the order, not just the boolean

This is the family behind:

• Course Schedule II
• build-order questions
• startup task sequencing
• release dependency planning

The trap here is thinking the question changed a lot from family one.

It did not.

You are still running the same dependency-unlock loop. The only difference is that now the order itself is the output.

What interviewers are really checking:

• Did you include isolated nodes with zero prerequisites?
• Did you keep edge direction straight?
• Do you know that any valid order is fine unless the prompt asks for a stable or lexicographically smallest one?

Candidates throw away easy points by building edges backward.

If the prompt says "A must happen before B," your edge is A -> B, and indegree[B] goes up.

Say that sentence before you code. It prevents half the bugs.

3. Derive the graph from partial evidence

This is the family behind:

• Alien Dictionary
• inferred ordering from logs
• sorted-record constraints
• implicit dependency questions where the graph is not handed to you

This is where topological sort starts feeling hard.

The hard part is usually not the topological sort. The hard part is building the graph correctly from the evidence.

For Alien Dictionary, the repeated mistakes are:

• comparing more than the first differing character
• forgetting to initialize letters that never appear in an edge
• missing the invalid prefix case like ["abc", "ab"]

That last one matters. If the earlier word is longer and fully prefixes the later word, the ordering is impossible before you even start the queue.

PYTHON

Copy

def add_constraint(a, b, graph, indegree): for left, right in zip(a, b): if left != right: if right not in graph[left]: graph[left].add(right) indegree[right] += 1 return True return len(a) <= len(b)

The talk-track to use is:

"The tricky part is graph construction, not the topological sort itself."

That tells the interviewer you know where the real risk is.

4. Add one more business rule on top

This is the family behind:

• Parallel Courses
• job scheduling with durations
• readiness questions with tie-breaking rules
• "find one valid order, but also optimize X"

This is where people over-focus on the topological-sort skeleton and forget the extra state the prompt actually cares about.

Sometimes the extra state is:

• semester count
• total completion time
• a lexicographically smallest valid order
• the longest path through a DAG after the order is known

The right move is to say that topological sort is the backbone, not the whole answer.

You still need the dependency order first. Then you layer the timing or selection rule on top.

Common mistakes that cost easy points

Reversing the edge direction

If A must happen before B, then the edge is A -> B.

This sounds obvious. Under pressure, it is not.

Forgetting isolated nodes

If a course, task, or letter never appears in an edge, it still exists. It still belongs in the graph. It still may belong in the answer.

Treating in-degree like a vague counter

in-degree is not "some graph number." It is how many unmet prerequisites remain right now.

Say that, and your bookkeeping usually gets cleaner.

Missing the invalid-prefix case

Topological sort does not rescue bad graph construction. If the input evidence is invalid before the graph is built, reject it early.

Narrating methods instead of the invariant

Better: "This node becomes ready once its last prerequisite is removed."

Worse: "Then I pop from the queue, then decrement, then append."

A better 90-minute topological-sort prep block

If this category still feels slippery, do one focused block like this:

1. 20 minutes: solve Course Schedule and say in-degree, ready, and cycle out loud until the words feel normal.
2. 20 minutes: solve Course Schedule II and make sure isolated nodes still appear in your output.
3. 20 minutes: do Alien Dictionary and focus on graph construction plus the invalid-prefix case.
4. 20 minutes: do one follow-up problem like Parallel Courses where topological sort is the skeleton but not the whole solution.
5. 10 minutes: explain edge direction, queue meaning, and cycle detection without touching the keyboard.

That block covers the failure modes that actually repeat:

• wrong edge direction
• missing isolated nodes
• weak in-degree explanation
• bad graph construction
• vague cycle reasoning

Then pick one dependency-order problem and solve it out loud.

If your explanation sounds like build-order reasoning instead of graph trivia, you are on the right track.

If you want the adjacent mental models after this, read Graph Interview Questions for Software Engineers: BFS, Topological Sort, and Union-Find and Queue Interview Questions for Software Engineers: FIFO State, Deques, and BFS Judgment.