Topological Sort Interview Pattern: When to Use It and 5 Problems to Practice (2026)

When interviewers ask you to arrange items that depend on each other, they are usually looking for a topological sort. The pattern works on directed acyclic graphs (DAGs) – think of a set of tasks where some must finish before others can start. The goal is to produce an ordering that respects every dependency.
\

Recognizing the Topological Sort Pattern\

You don’t need a formal graph theory background to see the signal. Typical wording includes:

• "Find an order to complete all courses given prerequisites."
• "Determine a build order for modules where some depend on others."
• "Schedule jobs so that each job runs after its prerequisites."
• "Arrange characters in a language where some letters must appear before others." If the problem mentions dependencies, prerequisites, or ordering constraints and the input is a list of pairs, you are likely dealing with a DAG and should consider topological sort. \

Two Common Implementations\

1. Kahn’s Algorithm (BFS)\

Kahn’s method repeatedly removes nodes with zero in‑degree. It is intuitive and makes cycle detection explicit.

from collections import defaultdict, deque

def topological_sort_kahn(num_nodes, edges):
    # Build adjacency list and indegree count
    adj = defaultdict(list)
    indeg = [0] * num_nodes
    for u, v in edges:  # edge u -> v (u must come before v)
        adj[u].append(v)
        indeg[v] += 1

    # Queue of nodes with no incoming edges
    q = deque([i for i in range(num_nodes) if indeg[i] == 0])
    order = []
    while q:
        node = q.popleft()
        order.append(node)
        for nxt in adj[node]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                q.append(nxt)
    # If not all nodes were visited, a cycle exists
    if len(order) != num_nodes:
        raise ValueError("Cycle detected – no topological order")
    return order

2. DFS Post‑order\

A depth‑first search records nodes after exploring all outgoing edges. Reversing that list yields a valid order.

def topological_sort_dfs(num_nodes, edges):
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
    visited = [0] * num_nodes  # 0=unvisited, 1=visiting, 2=visited
    order = []
    def dfs(u):
        if visited[u] == 1:
            raise ValueError("Cycle detected")
        if visited[u] == 2:
            return
        visited[u] = 1
        for v in adj[u]:
            dfs(v)
        visited[u] = 2
        order.append(u)
    for i in range(num_nodes):
        if visited[i] == 0:
            dfs(i)
    return order[::-1]

Both run in O(V + E) time and use O(V + E) space for the adjacency structures. \

Common Pitfalls and How to Avoid Them\

Worked Example: Course Schedule\

Problem: Given n courses numbered 0..n-1 and a list of prerequisite pairs [a, b] meaning a must be taken before b, output a possible order to finish all courses.

Solution Sketch:

1. Build the graph where each pair [a, b] creates an edge a → b.
2. Run Kahn’s algorithm.
3. If a cycle is detected, return an empty list (or raise).

Code:

def find_course_order(num_courses, prereqs):
    try:
        return topological_sort_kahn(num_courses, prereqs)
    except ValueError:
        return []  # No valid ordering exists

Walk‑through:

• Suppose num_courses = 4 and prereqs = [(0,1), (1,2), (0,3)].
• In‑degrees: [0,1,1,1] → queue starts with [0].
• Pop 0, reduce indegrees of 1 and 3 → queue becomes [1,3].
• Pop 1, reduce indegree of 2 → queue [3,2].
• Pop 3 (no outgoing edges), then 2. Result [0,1,3,2] respects all constraints. \

Five Representative Practice Problems

Below are five problems you can code up yourself. They are described in plain terms; the exact input format can be adapted to your favourite language.

1. Course Planner – Same as the worked example but with up to 10⁵ courses. Hint: Use an array for indegrees; avoid recursion depth limits.
2. Build System – Given modules and a list of "module A depends on module B", output a build order or detect impossibility. Hint: Map module names to integers first.
3. Task Scheduler with Parallelism – You have k workers that can run independent tasks simultaneously. Return the minimum number of time slots needed. Hint: After each Kahn iteration, you can process up to k zero‑indegree nodes.
4. Alien Dictionary – From a sorted list of words in an unknown language, infer a possible character ordering. Hint: Compare adjacent words to derive precedence edges; then topologically sort.
5. Project Milestones – Each milestone has a list of preceding milestones. Find the earliest week each milestone can be started, assuming each takes one week. Hint: While performing Kahn’s algorithm, keep a level array that records the longest path to each node. \

Complexity Recap

• Time: O(V + E) – each vertex and edge is visited a constant number of times.
• Space: O(V + E) for adjacency lists and auxiliary structures (queue, visited flags).
• When to prefer BFS vs DFS: BFS (Kahn) makes cycle detection explicit and is easier to explain; DFS is concise but requires careful handling of recursion depth and visitation states. \

How to Practice This

1. Implement both algorithms from scratch in your preferred language. Run them on random DAGs and verify they produce the same ordering.
2. Create edge‑case tests: empty graph, single node, graph with a cycle, and a graph where many nodes have zero indegree initially.
3. Use Call Assistant to rehearse your explanation. Record yourself describing the algorithm, then let the assistant surface follow‑up questions so you stay on topic and keep the answer concise.

---

FAQ

• Q: How can I tell if a problem really needs topological sort and not just sorting? A: Look for explicit dependency pairs. Simple numeric sorting has no constraints; topological sort is required when the order must respect directed relationships.
• Q: What if the graph contains a cycle? A: Both Kahn’s and DFS approaches can detect cycles. In an interview, you should explain that a cycle means no valid ordering exists and return an error or empty list.
• Q: Is it okay to use recursion for DFS in Python? A: For small graphs it’s fine, but for large inputs you may hit recursion limits. Switching to an explicit stack or using Kahn’s BFS avoids that risk.
• Q: Do I need to output the exact same order as the sample solution? A: No. Any order that satisfies all constraints is correct. Mention that multiple valid topological orders can exist.