The Build Order

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L4
Asked in
Citadel

Problem

A build system has n modules numbered 0 to n-1 and a list of edges, where each [a, b] pair means module a can only be built once module b has been built. Return an order in which every module can be built, and when more than one module is ready at the same moment, take the lowest-numbered one first. If the dependencies loop so that no valid order exists, return an empty list.

Some tasks must wait for others to finish first.

Example 1

Input:

n = 4, edges = [[1,0],[2,0],[3,1],[3,2]]

Output:

[0,1,2,3]

Example 2

Input:

n = 2, edges = [[1,0],[0,1]]

Output:

[]

Worked solution and explanation

What this really is

This is a cycle-detection problem wearing a build-scheduler costume. The skill being probed: can you produce an order where every module follows the ones it depends on, and recognize when no such order exists because the dependencies loop? Anyone can build the graph. Two things separate candidates. First, edge direction: an edge must point from a prerequisite to the module that waits on it, not the reverse. Invert the arrows and you schedule dependents before their prerequisites. Second, proving acyclicity: you know the graph is buildable only if you emitted every module. Skip that count and you hand back a half-finished order for a graph that can never be built at all.

Building it step by step

Step 1: Build an adjacency list and in-degree counts

For each [dependent, prereq] pair, append the dependent to adj[prereq] and add one to in_degree[dependent]. Pre-seed both maps for every module 0 to n-1 so isolated modules still exist in the graph and still get emitted.

Step 2: Seed a min-heap with the zero-in-degree modules

Every module with in-degree 0 has no unbuilt prerequisites, so it can go first. Push these into a min-heap rather than a plain queue: when several are ready at once, the heap hands back the lowest-numbered one, which makes the output deterministic and matches the expected [0, 1, 2, 3].

Step 3: Drain the heap, releasing dependents as prerequisites clear

Pop the smallest ready module, append it to the order, and walk its dependents, decrementing each one's in-degree. The moment a dependent hits 0, all of its prerequisites have been emitted, so push it onto the heap.

Step 4: Detect the cycle by counting

If the order has fewer than n modules, some of them never reached in-degree 0, which can only happen inside a cycle. Return an empty list. A self-loop [a, a] is the smallest such cycle, and the same check handles it.

The solution

Kahn's algorithm with a lowest-first tie-break
import heapq


def topological_sort(n: int, edges: list) -> list:
    adj = {i: [] for i in range(n)}
    in_degree = {i: 0 for i in range(n)}
    for dependent, prereq in edges:
        adj[prereq].append(dependent)
        in_degree[dependent] += 1

    ready = [node for node in range(n) if in_degree[node] == 0]
    heapq.heapify(ready)

    order = []
    while ready:
        node = heapq.heappop(ready)
        order.append(node)
        for dependent in adj[node]:
            in_degree[dependent] -= 1
            if in_degree[dependent] == 0:
                heapq.heappush(ready, dependent)

    return order if len(order) == n else []
DFS without state tracking
A recursive post-order emits a valid order on a DAG, but on a cyclic graph it either recurses forever or silently returns a partial order. To make it correct you must track three colors (unvisited, in-progress, done) and treat an edge into an in-progress node as a cycle. That is easy to get subtly wrong under interview pressure, and the lowest-first tie rule does not fall out of it naturally.
Kahn's algorithm
Cycle detection falls out for free: if the emitted count is short of n, a cycle exists. There are no recursion depth limits and no color bookkeeping, and the deterministic tie-break is a one-line swap from queue to heap.

Common follow-up questions