Deduplicate Retried Pipeline Runs by Idempotency Key
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:
2
Example:
print(distinct_runs([("c1", 0), ("c1", 5), ("c1", 100)], 60))2
- Process the first trigger
("c1", 0): Since no previous run exists for keyc1, a new run is started. The count increases to 1, and the last run time forc1is 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≥60, the window has expired, so a new run is started. The count increases to 2, and the last run time forc1is updated to 100. - The final output is 2
Constraints:
- A trigger starts a run unless a run with the same key started within
windowseconds before it. - Update the key's last-run time whenever a new run starts.
- Return the number of runs started.
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
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
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.