Q6 - Stripe Merchant Error Alerting Problem (3 Parts)

Scenario: Stripe's API answers a constant stream of merchant requests, and every one of them comes back with a status code. A monitoring service consumes that feed and raises alerts when a merchant starts seeing a burst of failures, so someone can look before the merchant notices. You are writing that service.

You receive a list of log lines in time order and return a list of alert strings. Each log line looks like this:

timestamp,merchant_id,status_code,count

• timestamp: whole seconds, non-decreasing as the feed advances.
• merchant_id: which merchant these transactions belong to.
• status_code: what Stripe returned. 200 is a success, and every other code is a failure.
• count: how many transactions this one line represents. A single line can carry six failures at once, so you are summing counts, never counting lines.

Three rules hold for all three parts:

1. The window is the last 30 seconds, inclusive on both ends. For a log at time T, the window covers every log with a timestamp in [T - 29, T].
2. Alerts are tracked per {merchant_id, status_code} pair. A merchant can have a 500 alert and a 402 alert firing independently, and one merchant's noise never affects another's.
3. Alerts are evaluated as each log is processed. Nothing happens between logs, so a window only ever moves when a new line arrives.

Every alert you emit is a string in this exact shape:

timestamp,event_type,merchant_id,status_code

Part 1: Spotting an Error Spike (~15 minutes)

Raise an alert for a {merchant, status_code} pair as soon as the window holds 5 or more failures on that exact code for that merchant.

If an alert for that pair is already firing, do not emit it again. In Part 1 an alert never goes away once raised.

INPUT:
   10,merchant1,500,2
   10,merchant2,500,1
   15,merchant1,500,2
   20,merchant1,500,1
   20,merchant2,500,4

OUTPUT:
   20,TRIGGER,merchant1,500
   20,TRIGGER,merchant2,500

WHY:
   merchant1 / 500:  2 at t=10, +2 at t=15, +1 at t=20  ->  5 in the window at t=20
   merchant2 / 500:  1 at t=10, +4 at t=20              ->  5 in the window at t=20
   Neither reaches 5 before t=20, so nothing fires earlier.

Solution - Part 1

Keep every log you have seen. When a new one arrives, only one pair can possibly have crossed the line: the pair that just got bigger. A success cannot push a failure count up, and the window sliding forward only ever removes old failures, so no other pair can newly reach 5.

That means the whole of Part 1 is: ignore 200s, sum this pair's counts inside the window, and fire once if the total reaches 5.

class AlertMonitor:
    WINDOW_SECONDS = 30
    FAILURE_THRESHOLD = 5

    def __init__(self):
        self.logs = []
        self.active_alerts = set()       # {merchant, status_code} pairs already firing
        self.events = []

    def process(self, timestamp, merchant, status_code, count):
        self.logs.append((timestamp, merchant, status_code, count))
        if status_code == 200:
            return                       # a success can never push a failure count up

        oldest = timestamp - self.WINDOW_SECONDS + 1
        failures = sum(c for ts, m, code, c in self.logs
                       if m == merchant and code == status_code and ts >= oldest)

        key = (merchant, status_code)
        if failures >= self.FAILURE_THRESHOLD and key not in self.active_alerts:
            self.active_alerts.add(key)
            self.events.append((timestamp, "TRIGGER", merchant, status_code))

    def alerts(self):
        # timestamp, then merchant, then status code, then event type
        self.events.sort(key=lambda e: (e[0], e[2], e[3], e[1]))
        return [f"{ts},{kind},{m},{code}" for ts, kind, m, code in self.events]

Complexity Analysis

• Time: O(n) per log, O(n^2) over the whole feed, because each arrival rescans everything stored so far. For an assessment sized feed that is completely fine, and it is what most submissions look like. We tighten it to O(1) amortized in the complete solution at the end.
• Space: O(n) for the retained log lines.

Part 2: Only Alert When It Actually Matters (~20 minutes)

Five failures means nothing on its own. A merchant pushing a hundred thousand payments a minute will throw five 500s constantly and nobody should be woken up for it. A merchant doing forty payments a minute throwing five 500s is genuinely broken.

So an alert now needs both conditions to hold:

1. 5 or more failures on that exact status code for that merchant in the window, exactly as in Part 1, and
2. those failures are more than 1% of that merchant's successful volume in the same window, where successful volume is the total count of 200s for that merchant.

The 1% comparison is strict, and the example below is built to catch you on precisely that.

INPUT:
   10,merchant1,200,600
   12,merchant1,500,6
   15,merchant2,200,599
   16,merchant2,500,6

OUTPUT:
   16,TRIGGER,merchant2,500

WHY:
   merchant1 at t=12:  6 failures, 600 successes.  1% of 600 is exactly 6.
                       6 > 6 is FALSE, so nothing fires.
   merchant2 at t=16:  6 failures, 599 successes.  1% of 599 is 5.99.
                       6 > 5.99 is TRUE, so the alert fires.

   One success apart, opposite answers. That is the whole point of this example.

Solution - Part 2

The condition itself is one extra line. The part that actually catches people is not the condition at all. It is a change in which pairs you check.

In Part 1 you only had to look at the pair that just arrived, because failure counts only ever grow for the pair receiving a log. That reasoning breaks the moment the rule depends on successes, because successes age out of the window too. A merchant's success volume falling away can make the ratio newly true for a status code that has not received a log in twenty seconds.

   0,m,200,1000     1000 successes
   5,m,500,6        6 failures.  window [-24,5]: 600 > 1000? NO, nothing fires
  31,m,200,1        window [2,31]: the 1000 successes have AGED OUT,
                    the 6 failures are still inside
                    600 > 1? YES, so {m,500} must fire at t=31

   The log that arrives at t=31 is a 200. The alert that fires is a 500.

So from Part 2 onward, every log makes you re-check every status code that merchant currently has in the window, not just the one that arrived. Miss this and your code passes the given example and fails the hidden tests.

def process(self, timestamp, merchant, status_code, count):
    self.logs.append((timestamp, merchant, status_code, count))
    oldest = timestamp - self.WINDOW_SECONDS + 1
    in_window = [r for r in self.logs if r[1] == merchant and r[0] >= oldest]

    successes = sum(c for _, _, code, c in in_window if code == 200)
    codes = {code for _, _, code, _ in in_window if code != 200}

    for code in sorted(codes):                   # every code, not just the one that arrived
        failures = sum(c for _, _, k, c in in_window if k == code)
        meets = failures >= self.FAILURE_THRESHOLD and failures * 100 > successes
        key = (merchant, code)
        if meets and key not in self.active_alerts:
            self.active_alerts.add(key)
            self.events.append((timestamp, "TRIGGER", merchant, code))

Part 3: Resolving, and Firing Again (~25 minutes)

An alert that never clears is useless. Part 3 gives alerts a lifecycle.

• An active alert is resolved at time T if a log arrives for that merchant at T and the window ending at T no longer meets the trigger conditions from Part 2.
• An alert can only ever resolve when a log is processed for that merchant. Time passing on its own resolves nothing, because nothing is evaluated between logs.
• Once resolved, that pair is free to fire again later if the conditions come back.
• Emit resolutions as RESOLVE rows, in the same format and the same sort order.

INPUT:
   10,merchant1,500,6
   16,merchant2,500,6
   45,merchant1,200,1
   45,merchant2,200,1

OUTPUT:
   10,TRIGGER,merchant1,500
   16,TRIGGER,merchant2,500
   45,RESOLVE,merchant1,500

WHY:
   t=10  merchant1: 6 failures, 0 successes -> 600 > 0 is true -> TRIGGER
   t=16  merchant2: 6 failures, 0 successes -> TRIGGER
   t=45  merchant1: window is [16,45], so the failure at t=10 has fallen out.
                    0 failures -> conditions fail -> RESOLVE
   t=45  merchant2: window is [16,45], and the failure at t=16 is STILL inside it,
                    since the window includes both ends. 6 failures, 1 success,
                    600 > 1 -> still firing -> emit NOTHING

   Two merchants, the same timestamp, the same kind of log, opposite outcomes,
   decided by a single second at the edge of the window.

Watch that run, and keep an eye on the window's left edge as it drags forward:

1 / 6

Solution - Part 3

Two changes, and one of them is easy to miss.

First, when the conditions fail and the pair is currently active, emit a RESOLVE and drop it from the active set. Since a resolved pair is no longer active, the existing trigger check will happily fire it again later, which is exactly the re-arming behaviour the spec asks for.

Second, the set of codes you loop over has to grow again. A pair resolves precisely because its failures have left the window, which means that code may have nothing in the window at all any more, so it will not appear in the codes you gathered from the window. You have to add the merchant's currently active alerts to that set or the resolution never fires.

codes = {code for _, _, code, _ in in_window if code != 200}
codes |= {code for (m, code) in self.active_alerts if m == merchant}   # may have aged out

for code in sorted(codes):
    failures = sum(c for _, _, k, c in in_window if k == code)
    meets = failures >= self.FAILURE_THRESHOLD and failures * 100 > successes
    key = (merchant, code)
    if meets and key not in self.active_alerts:
        self.active_alerts.add(key)
        self.events.append((timestamp, "TRIGGER", merchant, code))
    elif not meets and key in self.active_alerts:
        self.active_alerts.discard(key)
        self.events.append((timestamp, "RESOLVE", merchant, code))

Note what the elif gives you for free: a pair whose failures are still above 5 but whose ratio has dropped, because the merchant's successful volume climbed, also resolves. The rule is written as "no longer meets the trigger conditions", not "the failures went away", and those are different things.

The Complete Solution

This is all three parts together, and it also fixes the rescan. Instead of keeping every log forever and filtering it on each arrival, hold one queue per merchant plus running totals, then drag the left edge of the window forward and adjust the totals as entries fall off. Every log is pushed once and popped once, so the whole feed costs O(n).

from collections import Counter, defaultdict, deque


class AlertMonitor:
    WINDOW_SECONDS = 30
    FAILURE_THRESHOLD = 5

    def __init__(self):
        self.window = defaultdict(deque)       # merchant -> (timestamp, code, count)
        self.successes = defaultdict(int)      # merchant -> 200s inside the window
        self.failures = defaultdict(Counter)   # merchant -> code -> failures in window
        self.active_alerts = set()
        self.events = []

    def process(self, timestamp, merchant, status_code, count):
        pending = self.window[merchant]
        pending.append((timestamp, status_code, count))
        if status_code == 200:
            self.successes[merchant] += count
        else:
            self.failures[merchant][status_code] += count

        oldest = timestamp - self.WINDOW_SECONDS + 1
        while pending and pending[0][0] < oldest:      # drag the left edge forward
            _, old_code, old_count = pending.popleft()
            if old_code == 200:
                self.successes[merchant] -= old_count
            else:
                self.failures[merchant][old_code] -= old_count
                if self.failures[merchant][old_code] <= 0:
                    del self.failures[merchant][old_code]

        # every code still in the window, plus any that is firing but has aged out
        codes = set(self.failures[merchant])
        codes |= {code for m, code in self.active_alerts if m == merchant}

        for code in sorted(codes):
            failures = self.failures[merchant].get(code, 0)
            meets = (failures >= self.FAILURE_THRESHOLD
                     and failures * 100 > self.successes[merchant])
            key = (merchant, code)
            if meets and key not in self.active_alerts:
                self.active_alerts.add(key)
                self.events.append((timestamp, "TRIGGER", merchant, code))
            elif not meets and key in self.active_alerts:
                self.active_alerts.discard(key)
                self.events.append((timestamp, "RESOLVE", merchant, code))

    def alerts(self):
        self.events.sort(key=lambda e: (e[0], e[2], e[3], e[1]))
        return [f"{ts},{kind},{m},{code}" for ts, kind, m, code in self.events]

Complexity Analysis

• Time: O(1) amortized per log, plus a pass over that merchant's live status codes. Every entry is pushed once and popped once across the whole feed, so the window maintenance is O(n) in total rather than O(n) per arrival. The per-log code loop is bounded by how many distinct status codes that merchant currently has in play, which is a handful in practice.
• Space: O(w), where w is the number of log lines currently inside somebody's 30-second window. Entries are dropped as the window moves, so memory tracks the live traffic rate rather than the length of the feed.
• Sorting the output: O(a log a) for a alerts, done once at the end.

Final Notes

1. Read the spec once, slowly, before typing a line. Candidates report the real prompt is several screens long with all three parts visible at once and roughly an hour on the clock. The people who run out of time are usually the ones who started coding on screen one and had to unwind a misread rule at minute forty.
2. count is a quantity, not an id. One line can carry six failures. Everything is a sum of counts, never a count of lines, and reading that field wrong breaks every threshold in the problem.
3. The window includes both ends. For a log at T the window is [T - 29, T], so a failure at exactly T - 29 is still inside it. Example 3 is built on this: two merchants get the identical log at the identical second and only one of them resolves, entirely because of that boundary.
4. From Part 2 on, check every one of that merchant's codes, not just the one that arrived. Successes age out of the window too, so a merchant's volume dropping can make the ratio newly true for a code that has been quiet for twenty seconds. This is the single likeliest reason a solution passes the given examples and fails the hidden tests.
5. A resolving pair may have nothing left in the window. Its failures aged out, which is exactly why it resolves, so it will not appear among the codes you gathered from the window. Union the merchant's active alerts into that set or resolutions simply never fire.
6. Treat the output contract as part of the problem. Four sort keys, in order, with RESOLVE sorting before TRIGGER on the same timestamp. It is the cheapest thing on this page to get right and an expensive one to get wrong.

The thing to take away is that a spec this fiddly is the point, not an accident. Payments monitoring is full of rules that sound simple in a sentence and have three edge cases apiece, and Stripe would rather find out now whether you are the kind of engineer who pins those down before writing code. Get the rules onto paper first, and the implementation is a pleasant half hour. 🚀