Streaming Consecutive Failure Detection
Problem statement
You observe an infinite stream of events arriving in nondecreasing timestamp order. Each event has the form $(t, \text{user}, \text{outcome})$ where $t \geq 0$ is a real-valued timestamp and $\text{outcome} \in \{\text{success}, \text{failure}\}$.
For each user, you want to fire an alert whenever they accumulate three consecutive failures -- no successes in between -- such that the time span from the first to the third failure is strictly less than 5 seconds: $t_3 - t_1 < 5$.
Implement the function detect_failures(events), where events is a list of [t, user, outcome] records in nondecreasing timestamp order. Return a list of booleans, one per event (in the same order), where the $i$-th entry is True iff that event is the third (or later, overlapping) consecutive failure for its user that completes a valid triple within the 5-second window.
Requirements:
- Processes each incoming event in $O(1)$ expected time.
- Uses $O(U)$ total memory, where $U$ is the number of users with recent activity.
- Correctly handles overlapping detections for the same user (a fourth consecutive failure can trigger a second alert if it forms a new valid triple with the second and third failures).
Example
detect_failures([[0.1,"u","failure"],[1.1,"u","failure"],[2.1,"u","failure"],[3.0,"u","failure"]]) -> [False, False, True, True]
The third failure completes the triple $(0.1, 1.1, 2.1)$ with span $2.0 < 5$, and the fourth completes the overlapping triple $(1.1, 2.1, 3.0)$ with span $1.9 < 5$ -- so both fire.
Show hint
How much of a user's history can actually influence whether the next failure completes a qualifying triple?
Relevant roles: ML Engineer, MLOps Engineer, Forward Deployed Engineer and AI Engineer.