Streaming Consecutive Failure Detection

Reported in interviews at Tower Research Capital

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:

  1. Processes each incoming event in $O(1)$ expected time.
  2. Uses $O(U)$ total memory, where $U$ is the number of users with recent activity.
  3. 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.

Related free problems