The Dependency Resolver

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
L5
Asked in
Amazon

Problem

An on-call engineer restarting a pipeline holds a tasks map in which each task name lists the tasks that must finish before it can start, and every prerequisite is itself a task in the map. The scheduler launches in waves, each wave starting every task whose prerequisites are already done. Return the full launch order with each wave's tasks in the order the map lists them, or raise an exception when a cycle means some tasks can never start.

Everything depends on everything.

Example 1

Input:

tasks = {"load":["transform"],"notify":["load"],"extract":[],"transform":["extract"]}

Output:

["extract","transform","load","notify"]

Example 2

Input:

tasks = {"A":[],"B":["A"],"C":["A"],"D":["B","C"]}

Output:

["A","B","C","D"]

Worked solution and explanation

What this really is

Strip the scheduling costume and this is a topological sort: order a directed acyclic graph so every node lands after the nodes it depends on. The real skill isn't knowing the word, it's the release rule. A task is runnable the instant all of its prerequisites are already placed, and readiness keeps shifting as the placed set grows, so one pass or a sort by prerequisite count can't do it. Two things separate people here. First, edge direction: if A needs B, then B goes first, and a surprising number of candidates wire it backwards. Second, the cycle: when tasks remain but nothing is runnable, there is no valid order, and returning a truncated list instead of failing ships a scheduler that silently drops work.

Walking it

Step 1: Precompute each task's prerequisite set

For each task, collect its prerequisites into a set once. You test readiness on every sweep, and a subset check against the resolved set is far cheaper than rebuilding a list each pass.

Step 2: Sweep for ready tasks in map order

Walk the tasks in the order the map lists them. A task is ready when its prerequisite set is a subset of everything already resolved. Collect the wave in map order, not alphabetically and not by prerequisite count, because that is the order the launch promises. In the third example dedupe is listed first but launches last, and ingest goes out ahead of snapshot because the map lists it first.

Step 3: Release the wave as a unit

Append the whole wave to the order and only then add it to the resolved set. Growing that set is what unblocks the next wave on the following sweep. Releasing the wave as a unit is also why dedupe launches after snapshot even though it only needs ingest: it becomes ready on the second sweep, after the whole first wave is out.

Step 4: Fail on a stalled sweep

If a sweep finds no ready task while tasks still remain, every survivor is waiting on something inside its own loop. There is no valid order, so raise instead of returning a partial list.

The solution

Wave-by-wave release with cycle detection
from collections import defaultdict


def resolve_order(tasks: dict) -> list:
    # Build each task's prerequisite set once so every readiness
    # check below is a cheap subset test instead of a rescan.
    prerequisites = defaultdict(set)
    for task in tasks:
        for prereq in tasks[task]:
            prerequisites[task].add(prereq)

    resolved = set()
    order = []
    while len(resolved) < len(tasks):
        newly_ready = []
        for task in tasks:
            if task not in resolved and prerequisites[task] <= resolved:
                newly_ready.append(task)
        if not newly_ready:
            raise ValueError("Cycle detected in dependency graph")
        for task in newly_ready:
            resolved.add(task)
            order.append(task)
    return order
Repeated sweeps
Rescan every unplaced task each pass and release those whose prerequisites are all resolved. Simple, obviously correct, O(V^2). The cycle check is 'a full pass released nothing.'
In-degree tracking (Kahn's)
Count each task's unmet prerequisites, seed a wave with the zero-count tasks, and decrement counts as tasks release. O(V+E), but each new wave must be put back in map order. The cycle check is 'fewer tasks came out than went in.'

Common follow-up questions