Deduplicate Retried Pipeline Runs by Idempotency Key

mediumPROPipelines, Reliability & CostSystems & InfrastructureML Systems & Infrastructure 1

Problem Statement

A pipeline trigger may fire multiple times for the same commit. Count the distinct runs actually executed when duplicate triggers (same idempotency key within a time window) are collapsed.

Background

Each trigger has (key, time). A trigger starts a new run only if no run with the same key started within the last window seconds; otherwise it is a duplicate and reuses the existing run. Process triggers in time order and count distinct runs started.

Your Task

def distinct_runs(triggers, window):

triggers: list of (key, time), time non-decreasing.
Return the count of runs actually started.

Input Format

triggers (list of (str, int)), window (int).

Output Format

A single int.

Sample

print(distinct_runs([("c1", 0), ("c1", 5), ("c1", 100)], 60))

Output:

Example

Input

print(distinct_runs([("c1", 0), ("c1", 5), ("c1", 100)], 60))

Output

Reasoning

Process the first trigger ("c1", 0): Since no previous run exists for key c1, a new run is started. The count increases to 1, and the last run time for c1 is recorded as 0.
Process the second trigger ("c1", 5): Check the time difference from the last run: $5 - 0 = 5$ . Since $5 < 60$ (the window), this trigger is a duplicate and does not start a new run. The count remains 1.
Process the third trigger ("c1", 100): Check the time difference from the last recorded run (which is still at time 0): $100 - 0 = 100$ . Since $100 \ge 60$ , the window has expired, so a new run is started. The count increases to 2, and the last run time for c1 is updated to 100.
The final output is 2

Constraints

A trigger starts a run unless a run with the same key started within window seconds before it.
Update the key's last-run time whenever a new run starts.
Return the number of runs started.

Learn this in

CI/CD & PipelinesSystems & Networking ML InfrastructureSystems & Networking

More from ML Systems & Infrastructure 1

Spot vs On-Demand Expected-Cost Decisionmedium Minimum-Cost Job Scheduling Across Priced Windowshard Retry with Capped Exponential Backoff and Jitter Capmedium Critical Path Length of a Pipeline DAGmedium Pipeline Stages Ready to Runeasy

Concept primerPREVIEW

1. Background Knowledge

This problem models idempotency in distributed systems, a critical concept for ensuring that repeated operations (like pipeline triggers) do not cause side effects. An idempotency key is a unique identifier attached to a request; if the same key is received again within a defined time window, the system treats it as a duplicate and reuses the previous result instead of executing a new operation. This pattern is widely used in payment processing, CI/CD pipelines, and event-driven architectures to prevent redundant work and control costs.

The core mechanism here is a sliding window check. For each incoming trigger, you must determine whether a "live" run with the same key exists. A run is considered live if its start time is within the last window seconds relative to the current trigger's time. If a live run exists, the current trigger is collapsed (deduplicated); otherwise, a new run is started. Because triggers arrive in non-decreasing time order, you can process them sequentially without sorting.

Understanding state tracking is essential. You need to maintain, for each idempotency key, the timestamp of the most recent run that was actually started. This allows you to answer the question "Is there a recent run for this key?" in constant time. The problem is fundamentally about managing this state efficiently as time progresses.

2. Algorithm Approach

Use a hash map (dictionary) to track the last start time for each idempotency key. Iterate through the triggers in chronological order. For each trigger (key, time):

Check if key exists in the hash map.
If it does, compare the current time with the stored last start time. If time - last_start_time <= window, the trigger is a duplicate; do not update the map and do not increment the run count.
If it does not exist, or if the time difference exceeds the window, a new run is started. Update the hash map with the current time for this key and increment the run count.

This approach leverages the fact that triggers are already sorted by time, eliminating the need for complex data structures like segment trees or balanced BSTs. The hash map provides $O(1)$ average-case lookups and updates.

3. Step-by-Step Strategy

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