Deduplicate a Stream of Retried Events

Keep a hash map from event ID to the time its accepted copy arrived, plus a queue of IDs in arrival order. On each event, pop everything older than the window from the queue's front and delete it from the map; the event is a duplicate if its ID is still in the map. O(1) amortized per event.

mediumPattern: Sliding window·From Devana's Netflix question set

Problem

Playback clients retry uploads when they do not hear back, so the same event can arrive several times. Downstream counts must not double count, but the stream runs at a million events a second, so you cannot remember every ID forever.

Write a class EventDeduplicator(window_seconds) with is_duplicate(event_id, now). It returns True when the same ID was accepted within the last window_seconds, and otherwise accepts the event and returns False. State the guarantee the window gives.

class EventDeduplicator:
    def __init__(self, window_seconds: int = 900): ...
    def is_duplicate(self, event_id: str, now: float) -> bool: ...

This is one of Devana's own questions, written in the style of Netflix's interviews. It is not a question leaked from Netflix, and Devana is not affiliated with Netflix.

Constraints

• now never decreases from one call to the next.
• A copy arriving at most window_seconds after the accepted one is a duplicate; the boundary is inclusive.
• A duplicate does not extend the window, which runs from the accepted copy.
• After the window, the next copy is accepted again and starts a new window.
• Memory is bounded by the events inside the window, and dropping a genuine event is worse than letting an occasional duplicate through.

Examples

Input:  window_seconds = 900
        is_duplicate("e1", 0), is_duplicate("e1", 10)
Output: False, True

Input:  window_seconds = 900
        is_duplicate("e1", 0), is_duplicate("e1", 7200)
Output: False, False

Hints

Open one at a time, and try the problem again after each.

Approach: from brute force to optimal

How to say it in the interview

Lead with the guarantee, because the question asks for it: "copies within 15 minutes of the first are dropped; later ones are let through." Then the structure, a map for membership and a queue for expiry, both O(1) amortized. Then do the memory arithmetic out loud, since it is what pushes the design toward sharding.

Solution

Python

from collections import deque

class EventDeduplicator:
    def __init__(self, window_seconds=900):
        self.window = window_seconds
        self.accepted = {}       # event id -> time its accepted copy arrived
        self.order = deque()     # (time, event id), oldest first

    def is_duplicate(self, event_id, now):
        # Forget accepted events that have left the window.
        while self.order and self.order[0][0] < now - self.window:
            _, old_id = self.order.popleft()
            del self.accepted[old_id]
        if event_id in self.accepted:
            return True
        self.accepted[event_id] = now
        self.order.append((now, event_id))
        return False

JavaScript

class EventDeduplicator {
  constructor(windowSeconds = 900) {
    this.window = windowSeconds;
    this.accepted = new Map(); // event id -> time its accepted copy arrived
    this.order = [];           // [time, event id], oldest first, from this.head
    this.head = 0;
  }

  isDuplicate(eventId, now) {
    // Forget accepted events that have left the window.
    while (this.head < this.order.length && this.order[this.head][0] < now - this.window) {
      this.accepted.delete(this.order[this.head][1]);
      this.head++;
    }
    // Drop the consumed prefix now and then, so the array stays bounded.
    if (this.head > 1024 && this.head * 2 > this.order.length) {
      this.order = this.order.slice(this.head);
      this.head = 0;
    }
    if (this.accepted.has(eventId)) return true;
    this.accepted.set(eventId, now);
    this.order.push([now, eventId]);
    return false;
  }
}

Both versions are tested against the same cases, including every example on this page.

• The eviction test uses <, so an entry exactly window_seconds old is kept and the boundary is inclusive, as specified.
• JavaScript has no built-in deque, and shift() on an array is O(n), so the code keeps a head index and compacts occasionally.
• A duplicate never enters the queue, so it cannot extend the window.

Follow-up questions

Common mistakes

• A set of every ID ever seen, which grows until the process runs out of memory.
• Using list.pop(0) or Array.shift() for the queue, which makes every eviction O(n).
• Refreshing the timestamp on every duplicate, so a client that keeps retrying holds the window open indefinitely.
• Never stating the window. "Deduplicates the stream" without a time bound is a promise the design cannot keep.

Practice it in a mock interview

Reading a solution and explaining one under questioning are different skills. The button below starts this problem as a voice mock interview with Josh, Devana's AI interviewer, with an editor that runs your code.

Practice this problem in a mock interview

Related problems

• Time-Weighted Moving Average over Irregular Ticks: A time-based window with a running area, evicting from the front as ticks age out.
• Deduplicate a Member's Skills: Normalize each entry to a lookup key, map it through a taxonomy, keep first appearances.
• Sliding window: the pattern guide, with more practice questions.