Order DAG tasks so every dependency runs first

Python data engineering interview problem. Difficulty: intermediate. Pattern: Graphs. About 15 minutes. Part of the Pro drill bank.

Production ticket: A scheduler can't just run tasks in the order they were declared - it has to respect the dependency graph. Treat this as a production helper: match the contracted return shape, including empty and duplicate inputs.

An orchestration engineer files a ticket: the scheduler runs tasks in the order they are written in the config, so transform can start before extract is done and publish incomplete data. A task can only start after all tasks it depends on have finished. deps maps each task to the list of tasks it depends on. Return one valid run order where every task comes after its dependencies. When several tasks are ready at the same time, take the one that appears first in deps. If there is a cycle, raise a ValueError. Write topo_order(deps: dict[str, list[str]]) -> list[str]. For extract, transform (needs extract), load (needs transform) and notify (needs load) the order is ['extract', 'transform', 'load', 'notify']. For a and b with no dependencies and c needing both, the order is ['a', 'b', 'c']. The starter file already has the function and the print lines at the bottom. Keep them, because the grader reads what they print.

Requirements

• Run a task only after all its dependencies.
• Return every task once.
• Among ready tasks, choose the one listed first in deps.
• Raise ValueError when no task is ready but tasks remain (a cycle).

Constraints

• deps is a dictionary from task name to a list of task names.
• Every dependency is also a key.

Examples

Input: topo_order({"extract": [], "transform": ["extract"], "load": ["transform"], "notify": ["load"]}) Output: ['extract', 'transform', 'load', 'notify'] This is the expected return value for the given call.

Topics: orchestration, dag, topological-sort.

More Python interview questions · All interview problems · Learn data engineering