Neural Mastery
← Practice
Pipeline DAG Topological Sorthard

Pipeline DAG Topological Sort

hard ML Systems & MLOps 15 min

NumPy allowed · plain Python earns 10 bonus points

Implement topological sort for a data/ML pipeline DAG, determining a valid stage execution order from declared dependencies.

Task

Implement topological_sort(dependencies). dependencies maps each stage name to a list of stages it depends on (must run first). Return a valid execution order (a list of ALL stage names, including those with no dependents) such that every stage appears after all of its dependencies. Use Kahn's algorithm; among stages with no remaining dependencies at a given point, process them in sorted (alphabetical) order for a deterministic result. Assume the graph is acyclic.

Function Signature

topological_sort(dependencies: dict[str, list[str]]) -> list[str]

Examples

Example 1: linear chain
Input: dependencies = {'train': ['features'], 'features': ['ingest'], 'ingest': []}
Output: ['ingest', 'features', 'train']
Example 2: diamond dependency
Input: dependencies = {'deploy': ['test'], 'test': ['build_a', 'build_b'], 'build_a': [], 'build_b': []}
Output: ['build_a', 'build_b', 'test', 'deploy']
Example 3: independent stages alphabetical
Input: dependencies = {'c': [], 'a': [], 'b': []}
Output: ['a', 'b', 'c']

Constraints

  • no cycles
  • a stage may depend on a stage not itself listed as a key (treat it as having no further dependencies)
Python3Saved ✓
def topological_sort(dependencies):
# Your implementation here
pass

Case 1: linear chain
Input: dependencies = {'train': ['features'], 'features': ['ingest'], 'ingest': []}
Expected: ['ingest', 'features', 'train']
Case 2: diamond dependency
Input: dependencies = {'deploy': ['test'], 'test': ['build_a', 'build_b'], 'build_a': [], 'build_b': []}
Expected: ['build_a', 'build_b', 'test', 'deploy']
Case 3: independent stages alphabetical
Input: dependencies = {'c': [], 'a': [], 'b': []}
Expected: ['a', 'b', 'c']