Topological Sort for Dependency Problems: A Practical Interview Guide

Why topological sort shows up so often in interviews

A lot of real engineering work is about dependencies: build systems, package managers, task schedulers, course planning, and pipeline execution. Interview problems use smaller versions of the same idea. If one item must happen before another, you are working with a dependency graph.

Topological sort is the standard tool for ordering nodes in a directed graph so that every dependency appears before the thing that depends on it. Once you understand it, a whole family of interview problems becomes much easier:

• Can you finish all courses?
• In what order should tasks run?
• Is there a cycle in the dependency graph?
• Which jobs can run in parallel?

This pattern matters because it tests more than graph knowledge. It checks whether you can model a problem correctly, detect impossible states, and build a clean algorithm from first principles.

Problem statement

You are given items and prerequisite relationships. Each directed edge u -> v means u must come before v.

Your job is to produce a valid ordering of all items such that every dependency is respected. If no such ordering exists, return that the schedule is impossible.

This graph is usually a DAG: a directed acyclic graph. If the graph has a cycle, a valid topological order does not exist.

Common interview variations

• Course Schedule: Can you complete all courses given prerequisites?
• Course Schedule II: Return one valid course order.
• Task ordering: Find the sequence to run jobs with dependencies.
• Build order: Determine compilation order for modules.

Intuition and insight

The key insight is simple:

• If a node has no incoming edges, nothing blocks it.
• You can safely place it next in the output.
• Once you place it, you remove its outgoing edges.
• That may unlock new nodes with zero incoming edges.

This is exactly how topological sort works.

There are two standard approaches:

1. Kahn’s algorithm using indegrees and a queue
2. DFS postorder using recursion or an explicit stack

For interviews, Kahn’s algorithm is often easier to explain for dependency problems because it mirrors the real-world idea of “unlocking” tasks.

Approach 1: Kahn’s algorithm with indegrees

Core idea

1. Build an adjacency list for the graph.
2. Count indegrees for every node.
3. Put all nodes with indegree 0 into a queue.
4. Repeatedly pop a node, add it to the result, and reduce indegrees of its neighbors.
5. If a neighbor’s indegree becomes 0, add it to the queue.
6. If you process all nodes, you found a valid order. Otherwise, there is a cycle.

Why it works

A node with indegree 0 has no remaining prerequisites. That means it is safe to process now. When you remove it from the graph, you may create new nodes with indegree 0. The process continues until either:

• you schedule every node, or
• you get stuck because all remaining nodes are still waiting on each other, which implies a cycle.

Example 1: Course Schedule II

Let’s solve the version where you need to return one valid order.

from collections import deque
from typing import List


def find_order(num_courses: int, prerequisites: List[List[int]]) -> List[int]:
    graph = [[] for _ in range(num_courses)]
    indegree = [0] * num_courses

    for course, pre in prerequisites:
        graph[pre].append(course)
        indegree[course] += 1

    queue = deque([i for i in range(num_courses) if indegree[i] == 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_courses else []

Walkthrough

Suppose:

num_courses = 4
prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]

This means:

• 0 -> 1
• 0 -> 2
• 1 -> 3
• 2 -> 3

Initial state:

• indegree = [0, 1, 1, 2]
• queue = [0]
• order = []

Step by step:

1. Pop 0, append to order → [0]

   • reduce indegree of 1 to 0
   • reduce indegree of 2 to 0
   • queue becomes [1, 2]

2. Pop 1, append → [0, 1]

   • reduce indegree of 3 to 1
   • queue remains [2]

3. Pop 2, append → [0, 1, 2]

   • reduce indegree of 3 to 0
   • queue becomes [3]

4. Pop 3, append → [0, 1, 2, 3]

All courses are processed, so the answer is valid.

Example 2: Detecting impossibility with a cycle

Now consider:

num_courses = 2
prerequisites = [[0, 1], [1, 0]]

This is a cycle:

• 1 -> 0
• 0 -> 1

No node has indegree 0.

print(find_order(2, [[0, 1], [1, 0]]))
# []

The queue starts empty, nothing gets processed, and the returned order is empty. That correctly signals “impossible.”

Approach 2: DFS-based topological sort

Kahn’s algorithm is not the only way. DFS also works well, especially if the interview asks you to explicitly detect cycles.

Core idea

Use three states for each node:

• 0: unvisited
• 1: visiting
• 2: visited

During DFS:

• If you reach a node currently marked visiting, you found a cycle.
• After all descendants are processed, add the node to the result.

Because a node is added after its dependencies, the result list must be reversed at the end.

Python code

from typing import List


def find_order_dfs(num_courses: int, prerequisites: List[List[int]]) -> List[int]:
    graph = [[] for _ in range(num_courses)]
    for course, pre in prerequisites:
        graph[pre].append(course)

    state = [0] * num_courses  # 0 = unvisited, 1 = visiting, 2 = visited
    order = []
    has_cycle = False

    def dfs(node: int):
        nonlocal has_cycle
        if has_cycle:
            return
        if state[node] == 1:
            has_cycle = True
            return
        if state[node] == 2:
            return

        state[node] = 1
        for neighbor in graph[node]:
            dfs(neighbor)
        state[node] = 2
        order.append(node)

    for i in range(num_courses):
        if state[i] == 0:
            dfs(i)

    return order[::-1] if not has_cycle else []

Example 3: DFS walkthrough

Use the same graph as before:

num_courses = 4
prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]

DFS from 0 explores 1, then 3, then backtracks and adds 3, then 1. Then it explores 2, sees 3 already visited, and adds 2. Finally it adds 0.

The postorder list might be:

[3, 1, 2, 0]

Reverse it:

[0, 2, 1, 3]

That is a valid topological order.

Note that topological order is not unique. [0, 1, 2, 3] would also be valid for this graph.

Which approach should you use in interviews?

Both are correct. In practice:

• Use Kahn’s algorithm if you want an iterative approach, a clean cycle check, and a queue-based dependency unlocking flow.
• Use DFS if the problem naturally asks for recursion, postorder reasoning, or explicit cycle detection through node states.

Complexity comparison

Where:

• V = number of vertices/nodes
• E = number of edges/dependencies

Step-by-step problem-solving template

When you see a dependency problem, ask yourself:

1. What are the nodes?
2. What does a directed edge mean?
3. Is the graph possibly cyclic?
4. Do I need any valid order, or all possible orders?
5. Do I need to detect impossible scheduling?

Then map the problem to topological sort:

• Build a graph
• Choose Kahn or DFS
• Return the order if all nodes are processed
• Otherwise, return failure

A second worked example: simple task ordering

Suppose you have tasks:

• A depends on nothing
• B depends on A
• C depends on A
• D depends on B and C

Represent as edges:

• A -> B
• A -> C
• B -> D
• C -> D

Let’s use integers for code and map them to letters:

tasks = ["A", "B", "C", "D"]
prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
print(find_order(4, prerequisites))

One valid output is:

[0, 1, 2, 3]

Another valid output is:

[0, 2, 1, 3]

Both are correct because B and C can happen in either order after A.

Common mistakes

1. Reversing the edge direction

In course schedule problems, the pair [course, prerequisite] often means prerequisite -> course. If you flip this, the entire algorithm breaks.

2. Forgetting cycle detection

A topological order exists only for DAGs. If you process fewer than V nodes, you likely hit a cycle.

3. Adding a node too early in DFS

In DFS topological sort, append after exploring neighbors, not before.

4. Assuming the order is unique

Many graphs have multiple valid topological orders. Don’t hardcode one answer.

5. Not handling disconnected graphs

You must start from every unvisited node, not just one source, because the graph may have several components.

Related problems

Topological sort appears in many interview problems, sometimes directly and sometimes hidden inside another story.

• Course Schedule: can you finish all courses?
• Course Schedule II: return a valid course order
• Alien Dictionary: infer character ordering from sorted words
• Minimum Height Trees: not topological sort directly, but similar leaf-removal thinking
• Parallel task scheduling: compute levels or batches of work
• Build system dependency resolution: determine compilation order

If a problem asks for “before/after,” “must come first,” “prerequisite,” or “dependency,” consider whether a DAG and topological sort fit.

Key takeaways

• Topological sort orders nodes so every dependency comes first.
• It only works on DAGs; cycles make ordering impossible.
• Kahn’s algorithm uses indegrees and a queue.
• DFS topological sort uses postorder and cycle detection states.
• Many interview problems are just topological sort in disguise.

Final practical advice

When you practice topological sort, do not just memorize the code. Practice reading a problem and translating words into graph edges. That modeling step is usually the real interview test.

If you can explain why zero-indegree nodes are safe, why cycles break scheduling, and how the queue or DFS stack evolves, you are in good shape.

If you'd like to see the variables update live as you step through, check out codebrew.ai.

Practice these next

1. Course Schedule
2. Course Schedule II
3. Alien Dictionary
4. Find Eventual Safe States
5. Parallel Courses