Pipeline Stages Ready to Run

easyPROPipelines, Reliability & CostSystems & InfrastructureML Systems & Infrastructure 1

Problem Statement

Given a CI pipeline's stage dependencies and the set of completed stages, list which stages are ready to run next.

Background

A stage is ready if it has not completed yet and all of its dependencies are in the completed set. Return the ready stages sorted alphabetically.

Your Task

def ready_stages(deps, completed):

deps: dict mapping stage name -> list of prerequisite stage names.
completed: list/set of completed stage names.
Return the sorted list of ready stage names.

Input Format

deps (dict), completed (list of str).

Output Format

A sorted list of strings.

Sample

print(ready_stages({"build": [], "test": ["build"], "deploy": ["test"]}, ["build"]))

Output:

['test']

Example

Input

print(ready_stages({"build": [], "test": ["build"], "deploy": ["test"]}, ["build"]))

Output

['test']

Reasoning

Convert the completed stages list ["build"] into a set $\{ \text{"build"} \}$ to allow for efficient membership checks during dependency validation.
Evaluate the "build" stage: it is already in the completed set, so it is excluded from the ready list.
Evaluate the "test" stage: it is not completed, and its only dependency "build" is present in the completed set, satisfying the condition that all prerequisites are met.
Evaluate the "deploy" stage: it is not completed, but its dependency "test" is not in the completed set, so it is not ready to run.
The final output is ['test']

Constraints

Ready = not completed AND all deps completed.
Return names sorted ascending.

Learn this in

ML InfrastructureSystems & 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 models a Directed Acyclic Graph (DAG) where nodes represent pipeline stages and directed edges represent dependencies. In CI/CD systems, stages often cannot start until their prerequisites finish. The "ready" state is a fundamental concept in topological sorting and task scheduling: a node is ready to execute if all its incoming edges (dependencies) point to nodes that have already been processed.

The input deps defines the graph structure. A stage with an empty dependency list has no prerequisites and is immediately ready (unless already completed). A stage like deploy depending on test means deploy cannot run until test is in the completed set. This mirrors real-world systems like Airflow, Jenkins, or GitHub Actions, where orchestrators constantly evaluate which tasks can be dispatched to workers.

Understanding set operations is also key here. You are essentially checking membership: for each stage, verify that its dependency list is a subset of the completed stages. This is a classic pattern in constraint satisfaction and dependency resolution.

2. Algorithm Approach

The approach is a linear scan with subset checking. Since the problem asks for stages that are currently ready (not a full topological order), you do not need to simulate execution over time. Instead, you evaluate the static state:

Iterate over all stages defined in deps.
For each stage, check two conditions:

It is not in the completed set.
All its dependencies are in the completed set.

If both conditions hold, the stage is ready.
Collect all such stages and return them sorted alphabetically.

This is a filtering pattern, not a graph traversal algorithm like BFS or DFS, because we are not building an execution order—we are just identifying the current frontier of executable tasks.

3. Step-by-Step Strategy

Normalize completed: Convert the completed list into a set for $O(1)$ average-time membership checks. This is critical for performance.
Iterate through stages: Loop over the keys of the deps dictionary. Each key is a stage name.
Check completion status: If the stage is already in the completed set, skip it.
Check dependency satisfaction: Retrieve the list of prerequisites for the current stage. Verify that every prerequisite is in the completed set. You can use Python’s all() function with a generator expression for this.
Collect ready stages: If both checks pass, add the stage name to a result list.
Sort and return: Sort the result list alphabetically (lexicographically) and return it.

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