Problem Statement

Design a deduplication system for an event stream with a configurable time-to-live (TTL) window.

In distributed systems, the same event can arrive multiple times due to retries, network issues, or at-least-once delivery guarantees. A deduplicator detects and filters these duplicates within a time window, while allowing the same event ID to be processed again after the window expires.

Implement the Deduplicator class:

• Deduplicator(int ttl) initializes the deduplicator with a TTL window. An event is considered a duplicate if the same event ID was processed within the last ttl time units (inclusive). If ttl is 0, no deduplication is performed (every event is new).
• bool process(int timestamp, int eventId) processes an event. Returns true if this event is new (not seen within the TTL window), or false if it is a duplicate. Timestamps are guaranteed to be in non-decreasing order. The timestamp of the event is always updated on each call, whether it is new or a duplicate.

Additional information

• 0 <= ttl <= 10^6
• 1 <= timestamp <= 10^9
• 0 <= eventId <= 10^6
• Timestamps across calls are in non-decreasing order.
• At most 50,000 calls will be made to process.

Example 1:

Input:
["Deduplicator", "process", "process", "process", "process", "process"]
[[5], [1, 100], [2, 200], [3, 100], [7, 100], [8, 200]]

Output: [null, true, true, false, false, true]

Explanation:

• process(1, 100) -- event 100 is new. Returns true.
• process(2, 200) -- event 200 is new. Returns true.
• process(3, 100) -- event 100 was seen at t=1, and 3-1=2 <= 5 (within TTL). Duplicate. Returns false.
• process(7, 100) -- event 100 was last updated to t=3, and 7-3=4 <= 5. Still within TTL. Duplicate. Returns false.
• process(8, 200) -- event 200 was seen at t=2, and 8-2=6 > 5. TTL expired. New. Returns true.

Example 2:

Input:
["Deduplicator", "process", "process", "process", "process"]
[[0], [1, 10], [2, 10], [3, 10], [4, 10]]

Output: [null, true, true, true, true]

Explanation: TTL is 0, so no deduplication happens. Every event is treated as new.

Simple Dictionary (No Expiration)

Intuition

Store every event with its timestamp. On each process call, scan all stored events to check if the same event ID exists within the TTL window. This is straightforward but slow for large streams.

Algorithm

1. Maintain a dictionary mapping eventId to its last-seen timestamp.
2. On process(timestamp, eventId): check if the event exists in the dictionary and its stored timestamp is within the TTL window. Always update the timestamp for the event.

class Deduplicator:
    def __init__(self, ttl):
        self.ttl = ttl
        self.events = {}

    def process(self, timestamp, eventId):
        if eventId in self.events and timestamp - self.events[eventId] <= self.ttl:
            self.events[eventId] = timestamp
            return False
        self.events[eventId] = timestamp
        return True

Time & Space Complexity

• Time complexity: O(n) per process

• Reason: Scanning all stored events to find a matching ID.

• Space complexity: O(n)

• Reason: All events are stored, growing unboundedly.

Hash Map with Expiration (Optimal)

Intuition

A hash map from eventId to its last-seen timestamp gives O(1) duplicate lookups. On each call, we clean up expired entries (where currentTimestamp - storedTimestamp > ttl) to bound memory usage.

Since timestamps arrive in non-decreasing order, any entry that expires stays expired -- we never need to "un-expire" it. This means our cleanup pass is correct and the map only holds active entries.

Algorithm

1. Initialize a dictionary seen mapping eventId to its last timestamp.
2. On process(timestamp, eventId):

• Remove all entries from seen where timestamp - storedTimestamp > ttl.
• If eventId is in seen, update its timestamp and return False (duplicate).
• Otherwise, add it to seen and return True (new event).

class Deduplicator:
    def __init__(self, ttl):
        self.ttl = ttl
        self.seen = {}

    def process(self, timestamp, eventId):
        expired = [k for k, t in self.seen.items() if timestamp - t > self.ttl]
        for k in expired:
            del self.seen[k]

        if eventId in self.seen:
            self.seen[eventId] = timestamp
            return False
        self.seen[eventId] = timestamp
        return True

Time & Space Complexity

• Time complexity: O(n) worst case per process (cleanup pass), O(1) amortized

• Reason: The cleanup pass iterates expired entries, but each entry is cleaned at most once. The lookup and insert are O(1).

• Space complexity: O(k) where k is the number of active (non-expired) event IDs

• Reason: Expired entries are removed, so the map is bounded by the number of distinct events within the TTL window.