How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Stripe.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Stripe during technical interviews.

Detect Trigger and Resolve Events | Stripe Coding Question

Detect Trigger and Resolve Events

Company: Stripe

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given transaction logs sorted by non-decreasing timestamp. Each log record has four fields: - `timestamp`: integer time in seconds - `merchant_id`: merchant identifier - `status_code`: error code - `count`: how many times that error occurred at that timestamp Given two integers, `window_size` and `threshold`, monitor each `(merchant_id, status_code)` pair independently. For a log at time `t`, define the rolling error count for its `(merchant_id, status_code)` pair as the sum of `count` values from all records for that same pair whose timestamps are in the inclusive range `[t - window_size + 1, t]`. While processing the logs in chronological order: - Emit a `TRIGGER` event when the rolling count for a pair changes from **strictly less than** `threshold` to **greater than or equal to** `threshold`. - Emit a `RESOLVE` event when the rolling count for a pair changes from **greater than or equal to** `threshold` to **strictly less than** `threshold`. - Do not emit duplicate consecutive events of the same type for the same pair. Return all emitted events in chronological order. Each output event should contain: - `timestamp` - `merchant_id` - `status_code` - `event_type` (`TRIGGER` or `RESOLVE`) Assume timestamps are processed in input order when equal, and each log contributes only to its own `(merchant_id, status_code)` pair.

Quick Answer: This question evaluates handling of time-ordered log streams, rolling-window aggregation, and state transition detection for keyed pairs, testing competence in algorithms, stateful stream processing, and temporal data handling.

You are given transaction logs sorted by non-decreasing timestamp. Each log is a 4-tuple: (timestamp, merchant_id, status_code, count). Monitor each (merchant_id, status_code) pair independently. For a log processed at time t, its rolling error count is the sum of count values from records with the same (merchant_id, status_code) whose timestamps fall in the inclusive range [t - window_size + 1, t]. While processing the logs in chronological order: - Emit a TRIGGER event when a pair's rolling count changes from strictly less than threshold to greater than or equal to threshold. - Emit a RESOLVE event when a pair's rolling count changes from greater than or equal to threshold to strictly less than threshold. - Do not emit duplicate consecutive events of the same type for the same pair. Important: events are evaluated only when processing an input log. Do not create synthetic events at times when no log exists for that pair. If multiple logs share the same timestamp, process them in input order. Return all emitted events in chronological order as 4-tuples: (timestamp, merchant_id, status_code, event_type).

Constraints

0 <= len(logs) <= 200000
0 <= timestamp <= 10^9, and logs are sorted by non-decreasing timestamp
1 <= window_size <= 10^9
1 <= threshold <= 10^12
1 <= count <= 10^9
merchant_id and status_code can be used as dictionary keys

Examples

Input: ([(1, 'm1', 500, 2), (2, 'm1', 500, 2), (5, 'm1', 500, 1), (6, 'm1', 500, 1)], 3, 4)

Expected Output: [(2, 'm1', 500, 'TRIGGER'), (5, 'm1', 500, 'RESOLVE')]

Explanation: At time 2, the rolling count for ('m1', 500) becomes 4, crossing the threshold and triggering an alert. At time 5, the earlier counts have expired from the 3-second window, so the rolling count drops to 1 and emits RESOLVE.

Input: ([(1, 'A', 404, 2), (1, 'A', 404, 1), (2, 'B', 500, 3), (3, 'A', 404, 1), (4, 'B', 500, 1)], 3, 3)

Expected Output: [(1, 'A', 404, 'TRIGGER'), (2, 'B', 500, 'TRIGGER')]

Explanation: The second log at timestamp 1 brings ('A', 404) to a rolling count of 3, so it triggers. Pair ('B', 500) reaches 3 at time 2 and also triggers. Later logs keep both pairs above threshold, so no duplicate TRIGGER events are emitted.

Input: ([(1, 'x', 1, 3), (2, 'x', 1, 2), (6, 'x', 1, 1)], 4, 5)

Expected Output: [(2, 'x', 1, 'TRIGGER'), (6, 'x', 1, 'RESOLVE')]

Explanation: At time 2, the rolling count becomes 5 and triggers. By time 6, the counts from times 1 and 2 are outside the 4-second window, so only the current count of 1 remains and the alert resolves.

Input: ([(1, 'm', 7, 2), (2, 'm', 7, 2), (5, 'm', 7, 2), (6, 'm', 7, 2)], 2, 4)

Expected Output: [(2, 'm', 7, 'TRIGGER'), (5, 'm', 7, 'RESOLVE'), (6, 'm', 7, 'TRIGGER')]

Explanation: Times 1 and 2 together reach 4, so a TRIGGER is emitted at 2. At time 5, the old records have expired and the rolling count is only 2, so a RESOLVE is emitted. At time 6, the window contains times 5 and 6 for a total of 4 again, so another TRIGGER is emitted.

Input: ([], 5, 10)

Expected Output: []

Explanation: With no logs, no events are emitted.

Hints

Treat each (merchant_id, status_code) pair as its own independent stream of records.
For each stream, use a deque to remove expired records from the left and keep a running sum of counts in the current window.

Quick Overview

This question evaluates handling of time-ordered log streams, rolling-window aggregation, and state transition detection for keyed pairs, testing competence in algorithms, stateful stream processing, and temporal data handling.