Q6 - The Flapping Alert Filter

Scenario: Google runs a monitoring pipeline over thousands of production services. Probes fire short alert lines into a console that an on-call engineer is watching during an incident. Every alert carries two things: the second it fired, and the alert text.

They arrive one at a time, oldest first, and look like this:

time:1    disk-full
time:5    disk-full
time:12   api-5xx

Part 1: The console is drowning in repeats. Build a filter that shows an alert only if that same alert text has not already been shown in the last 10 seconds. Anything repeating inside that cooldown is dropped.

For Part 1 we take the usual reading: the cooldown runs from the last copy we actually showed, and the stream arrives in non-decreasing time order.

ALERTS (arrival order):
   time:1    disk-full
   time:5    disk-full
   time:12   disk-full
   time:23   disk-full

CONSOLE (Part 1 rule, 10s cooldown from the last one SHOWN):
   [1]  disk-full     first sighting, nothing to compare against
        (5 dropped)   only 4s after the copy shown at 1
   [12] disk-full     11s after the copy shown at 1, cooldown expired
   [23] disk-full     11s after the copy shown at 12, cooldown expired

Part 1: The Cooldown Filter

Strip the story away and almost nothing is left. For each alert text you need one fact: the last time you showed it. That is a map from text to timestamp.

When an alert arrives, look its text up. If you have never shown it, or the gap since you last showed it is at least 10 seconds, show it and record the new time. Otherwise drop it and change nothing. One lookup, one comparison, one write.

The detail worth saying out loud is the one the cooldown hangs on: you record the time you showed a copy, not the time you saw one. A burst of copies arriving every two seconds forever will keep failing the check against that same stored time, so the alert surfaces once every 10 seconds instead of never surfacing again.

class AlertConsole:
    """Part 1: show an alert unless the same text was shown in the last 10 seconds."""

    def __init__(self, window_seconds=10):
        self.window_seconds = window_seconds
        self.last_shown = {}                 # alert text -> when we last showed it

    def receive(self, timestamp, text):
        last = self.last_shown.get(text)
        if last is not None and timestamp - last < self.window_seconds:
            return False                     # still inside the cooldown, drop it
        self.last_shown[text] = timestamp
        return True                          # show it

Part 2: When a Repeat Poisons Both

Here is the wrinkle. The on-call engineer comes back unhappy. A flapping alert, one that fires, clears, and fires again seconds later, is almost always noise: a probe bouncing, a pod restarting, a threshold sitting right on the line. Showing the first copy still put a false alarm on their screen at 3am.

So the rule changes, and only one word really moves:

An alert is shown only if no other copy of the same text fired within 10 seconds of it. If two copies land within 10 seconds of each other, that alert is flapping, and both copies are hidden.

Read that twice, because it breaks something structural. Under Part 1 you could decide an alert's fate the moment it arrived. Under this rule you cannot. The alert at time 1 looks perfectly isolated when it lands. Four seconds later a second copy shows up, and now the first one is noise too, except you already printed it to a console you cannot un-print.

Run the exact same stream from Example 1 through the new rule and watch how much changes.

ALERTS (arrival order):
   time:1    disk-full
   time:5    disk-full
   time:12   disk-full
   time:23   disk-full

VERDICT per alert:
   [1]    hidden    a copy fires at 5, which is 4s away    (4 < 10)
   [5]    hidden    within 10s of BOTH the copy at 1 and the copy at 12
   [12]   hidden    a copy fired at 5, which is 7s away    (7 < 10)
   [23]   SHOWN     nearest copy is at 12, which is 11s away  (11 >= 10)

CONSOLE:
   [23] disk-full

Part 1 showed three of these four. Part 2 shows one.

Two copies can take each other down even when neither is near anything else, and a middle copy can be poisoned from both sides at once. Note also that 12 and 23 are 11 seconds apart, so that pair is fine; 12 dies because of 5, not because of 23.

ALERTS (arrival order):
   time:2    cpu-hot
   time:3    disk-full
   time:9    cpu-hot        <-- 7s after cpu-hot@2
   time:20   disk-full      <-- 17s after disk-full@3

VERDICT per alert:
   [2]    hidden    cpu-hot fires again at 9   (7 < 10)
   [9]    hidden    the other half of that same flapping pair
   [3]    SHOWN     nearest disk-full is at 20 (17 >= 10)
   [20]   SHOWN     nearest disk-full is at 3  (17 >= 10)

CONSOLE (in time order):
   [3]  disk-full
   [20] disk-full

cpu-hot and disk-full are compared only against themselves, so a busy text never drags a quiet one down with it. Each alert text gets its own independent timeline.

Step 1: You cannot print on arrival, so buffer instead

The first move is to stop trying to answer immediately. When an alert lands you do not know enough yet, so hold it and write down a provisional verdict you are allowed to revise.

Give every buffered alert one mutable flag, suppressed, starting at false. A later arrival is allowed to reach back and flip that flag to true. Nothing is printed while an alert sits in the buffer.

buffer after time:1        (nothing printed yet)
   [ 1  disk-full  suppressed=false ]

buffer after time:5        5 - 1 = 4, under 10, so the pair is flapping
   [ 1  disk-full  suppressed=TRUE  ]   <-- reached back and flipped
   [ 5  disk-full  suppressed=TRUE  ]

Step 2: Only the previous copy of that text can ever matter

The obvious way to check a new alert is to compare it against every copy of that text you have ever seen. That is O(k) per alert and it keeps getting slower as the stream runs. You can do far better, and the reason is worth saying out loud in the room.

Because the stream arrives in time order, take any three copies of the same text at times a < b < c. If a and c are within 10 seconds of each other, then b sits between them, so b is within 10 seconds of a too.

   a ............ b ...... c
   |<------- under 10s ------>|
   |<-- under 10s -->|              b is closer to a than c is

So if any pair of copies is close enough to matter, then some adjacent pair is already close enough. The consequence: you never need to look further back than the single most recent copy of that exact text. One lookup, not a scan.

Step 3: An alert is final once the stream passes its window

Buffered alerts cannot sit there forever, so you need the moment it becomes safe to commit one.

An alert at time t can only be killed by a copy that fires within 10 seconds of it. Once the stream's clock reaches t + 10, every future arrival is stamped t + 10 or later, which is at least 10 seconds away from t. Nothing that can still arrive is able to touch it. Its verdict is final.

So on each arrival at time now, first settle the front of the buffer: while the oldest buffered alert has timestamp + 10 <= now, pop it and print it if its flag is still false. Because arrivals come in time order, the buffer is already sorted by timestamp, so a plain queue works and the front is always the next one to close.

That gives the whole receive method: settle what has closed, look up the one previous copy, flip both flags if they are too close, then buffer this one.

def receive(self, timestamp, text):
    self._settle_through(timestamp)              # commit everything whose window closed
    previous = self.open_alert.get(text)         # the one copy that could still clash
    alert = {"timestamp": timestamp, "text": text, "suppressed": False}
    if previous is not None and timestamp - previous["timestamp"] < self.window_seconds:
        previous["suppressed"] = True            # reach back and kill the earlier copy
        alert["suppressed"] = True               # and this one is noise too
    self.pending.append(alert)
    self.open_alert[text] = alert

One case is easy to miss: when the stream ends, alerts whose windows never closed are still sitting in the buffer. Nothing more can arrive to kill them, so a final flush prints every survivor. Forget it and your last few seconds of output silently vanish.

Watch Example 2 run frame by frame. Each bar is one alert's 10-second window, and the dashed line is where the stream has reached, so a clash is simply the line landing inside an open bar. The last two frames cover the two ideas underneath it:

1 / 9

Part 3: Keep It Bounded, the Stream Never Ends

If your interviewer likes what they see, the next question is usually about memory. This console runs for months. What in your design grows without limit?

The buffer is fine: alerts leave it as soon as their windows close. The lookup map is the problem. Key it by alert text and never remove anything, and you are holding one entry for every distinct alert text the system has ever emitted, forever, long after those alerts stopped mattering.

The fix falls out of Step 3. Once an alert's window has closed, that copy can never clash with anything that arrives later, which is exactly why you were able to settle it. So it has no business staying in the lookup map either. Prune it at the same moment, with one guard: only remove the entry if it still points at the copy you are settling. If a newer copy of that text has already replaced it, that newer copy still has an open window and must stay.

alert = self.pending.popleft()
if not alert["suppressed"]:
    ready.append(alert)
# the window has closed, so this copy can never clash again: stop tracking it,
# unless a newer copy of the same text has already taken its place
if self.open_alert.get(alert["text"]) is alert:
    del self.open_alert[alert["text"]]

Now both structures hold only what is still inside an open window. Memory tracks how many alerts arrive in any 10 seconds, not how long the process has been up. Say that part out loud: interviewers ask the memory question specifically to find out whether you think past the happy path.

The Full Solution

Putting Parts 2 and 3 together. receive hands back the alerts that just became final, which is usually nothing, and endOfStream flushes the survivors when the feed stops.

from collections import deque


class FlappingAlertFilter:
    """Show an alert only if no other copy of the same text fired within the window."""

    def __init__(self, window_seconds=10):
        self.window_seconds = window_seconds
        self.pending = deque()       # alerts with open windows, oldest first
        self.open_alert = {}         # alert text -> its most recent open copy

    def receive(self, timestamp, text):
        """Take one alert from the stream, return any alerts that are now final."""
        ready = self._settle_through(timestamp)
        previous = self.open_alert.get(text)
        alert = {"timestamp": timestamp, "text": text, "suppressed": False}
        if previous is not None and timestamp - previous["timestamp"] < self.window_seconds:
            previous["suppressed"] = True    # reach back: the earlier copy is noise too
            alert["suppressed"] = True
        self.pending.append(alert)
        self.open_alert[text] = alert
        return ready

    def _settle_through(self, now):
        """Commit every alert whose 10-second window has closed by `now`."""
        ready = []
        while self.pending and self.pending[0]["timestamp"] + self.window_seconds <= now:
            alert = self.pending.popleft()
            if not alert["suppressed"]:
                ready.append(alert)
            if self.open_alert.get(alert["text"]) is alert:
                del self.open_alert[alert["text"]]   # closed window: stop tracking it
        return ready

    def end_of_stream(self):
        """Nothing else can arrive, so every survivor still buffered is final."""
        ready = [alert for alert in self.pending if not alert["suppressed"]]
        self.pending.clear()
        self.open_alert.clear()
        return ready

Complexity Analysis

• receive: amortized O(1). One map lookup, one flag write, one append. A single call can settle several buffered alerts at once, but every alert is buffered exactly once and settled exactly once, so a stream of n alerts costs O(n) in total.
• Memory: O(open alerts), meaning the alerts whose 10-second windows have not closed yet. That is set by the arrival rate in any 10-second span, not by how long the process has been running, and the pruning in Part 3 is what keeps it there.
• Output delay: up to the window. An alert is printed no earlier than 10 seconds after it fires, which is the unavoidable price of a rule that lets the future change the past. Name this trade-off in the room before the interviewer does.

The naive version is worth saying out loud so they know you can see it: store every arrival per text, and on each new alert scan that text's history for anything within 10 seconds. It gives the right answer, but it is O(k) per alert and degrades toward O(n^2), and the history grows forever. Both problems disappear once you notice you only ever need the previous copy and only until its window shuts.

Final Notes

1. The one-word change is the entire interview. Part 1 hides the repeat. Part 2 hides the repeat and the original. That difference is what removes your ability to answer on arrival, and candidates who skim the new rule write Part 1 twice and never notice.
2. Buffer, then settle. When the future can invalidate the past, hold each record with a revisable verdict and commit it only once nothing can still change it, which here is the moment the stream's clock passes t + 10. The queue is already in time order because the arrivals are, so the front is always the next one to close.
3. Only the previous copy of the same text can matter. Three copies at a < b < c with a and c within 10 seconds means b is within 10 seconds of a as well, so a close pair is always an adjacent pair. That single observation turns a growing scan into one lookup.
4. Do not lose the tail. Alerts whose windows never close are still buffered when the feed stops, and they are all survivors. A stream with no flush silently drops its last few seconds, which is the bug most likely to surface in the room.
5. Answer the memory question before it is asked. A correct solution can still hold one key for every alert text the system has ever emitted, which is an unbounded map. Drop each entry the moment its window closes, guarding against a newer copy that has already replaced it, and memory stays proportional to one window.

The reason Google keeps reaching for questions shaped like this is that production streams really do behave this way: the thing you need in order to judge a record often shows up after the record does. Get comfortable saying "I cannot decide this yet, so here is where I will hold it and here is exactly when I will commit," and you are most of the way through the round. 🚀