Order Build Stages by Dependency

mediumPROContainer Images & BuildsSystems & InfrastructureML Systems & Infrastructure 1

Problem Statement

A multi-stage Dockerfile has named stages that COPY --from earlier stages. Produce a build order so each stage is built after the stages it copies from.

Background

This is a topological sort over stage dependencies. Each stage names the stages it depends on. Build order lists dependencies before dependents; among stages that are simultaneously ready, choose the alphabetically smallest name for determinism. A dependency cycle returns "CYCLE".

Your Task

def build_order(stages):

stages: dict mapping stage name -> list of stage names it depends on.
Return the ordered list of stage names, or "CYCLE".

Input Format

stages (dict of str -> list of str).

Output Format

A list of strings, or "CYCLE".

Sample

print(build_order({"app": ["builder"], "builder": []}))

Output:

['builder', 'app']

Example

Input

print(build_order({"app": ["builder"], "builder": []}))

Output

['builder', 'app']

Reasoning

Initialize Dependencies: Analyze the input stages to determine in-degrees (number of unmet dependencies) for each stage. "builder" has no dependencies, so its in-degree is $0$ . "app" depends on "builder", so its in-degree is $1$ .
Select Initial Stage: Identify all stages with an in-degree of $0$ as ready to build. Only "builder" qualifies, so it is selected first and added to the build order.
Update Dependencies: Remove "builder" from the ready set and decrement the in-degree of any stage that depended on it. "app" depended on "builder", so its in-degree decreases from $1$ to $0$ .
Select Next Stage: With "builder" built, "app" now has an in-degree of $0$ and becomes ready. It is selected next and appended to the build order.
Finalize Order: The heap of ready stages is now empty, and the build order contains both stages. Since the length of the order ( $2$ ) matches the total number of stages ( $2$ ), no cycle exists, and the process terminates successfully.
The final output is ['builder', 'app']

Constraints

Dependencies build before dependents.
Ties broken by alphabetically smallest ready stage.
Return "CYCLE" if no valid order exists.

Learn this in

CI/CD & PipelinesSystems & Networking Docker & ContainerizationSystems & Networking

More from ML Systems & Infrastructure 1

Spot vs On-Demand Expected-Cost Decisionmedium Minimum-Cost Job Scheduling Across Priced Windowshard Deduplicate Retried Pipeline Runs by Idempotency Keymedium Retry with Capped Exponential Backoff and Jitter Capmedium Critical Path Length of a Pipeline DAGmedium

Concept primerPREVIEW

1. Background Knowledge

This problem is a classic application of topological sorting on a Directed Acyclic Graph (DAG). In a multi-stage Docker build, each stage is a node, and a COPY --from instruction creates a directed edge from the source stage to the dependent stage. A valid build order is a linear ordering of all nodes such that for every edge $(u, v)$ , node $u$ appears before node $v$ . If the graph contains a directed cycle, no such ordering exists, and the build is impossible.

The requirement to choose the alphabetically smallest name among simultaneously ready stages transforms this from a standard topological sort into a Kahn's algorithm variant using a min-heap (priority queue). Standard Kahn's algorithm uses a queue, which does not guarantee lexicographic order. By replacing the queue with a min-heap, we ensure that at every step, the lexicographically smallest available node is selected, producing a deterministic and lexicographically minimal topological order.

Cycle detection is inherent to Kahn's algorithm: if the number of nodes processed is less than the total number of nodes, a cycle exists. This is because nodes in a cycle will never have their in-degree reduced to zero.

2. Algorithm Approach

Use Kahn's algorithm with a min-heap for deterministic ordering:

Compute the in-degree of each node (number of dependencies it has).
Initialize a min-heap with all nodes that have in-degree zero (no dependencies).
Repeatedly extract the smallest node from the heap, append it to the result, and decrement the in-degree of its neighbors.
If a neighbor's in-degree becomes zero, add it to the heap.
If the result length equals the total number of stages, return it; otherwise, return "CYCLE".

3. Step-by-Step Strategy

Build the adjacency list: For each stage s and each dependency d in stages[s], add an edge from d to s (i.e., d must be built before s).
Compute in-degrees: For each stage, count how many dependencies it has. This is the in-degree in the dependency graph.
Initialize the min-heap: Push all stage names with in-degree zero into a heapq-based min-heap.
Process nodes: While the heap is not empty:
Pop the smallest stage name.
Append it to the result list.
For each stage that depends on this popped stage, decrement its in-degree.
If the in-degree becomes zero, push that stage into the heap.
Check for cycles: If the length of the result list is less than the number of stages, return "CYCLE". Otherwise, return the result list.

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results