Design a Ten-Minute In-Memory Notification Deduplication Engine

# Design a Ten-Minute In-Memory Notification Deduplication Engine Design the in-memory component of a high-throughput notification service that detects repeated notification IDs. The preserved requirements say that an identical UUID string seen during the past ten minutes is a duplicate, traffic is about 10,000 notifications per second, one application instance has a strict memory limit, expired IDs must be cleaned up, and check-and-insert should ideally take `O(1)` or `O(log N)` time. The source does not preserve a callable interface, response shape, clock definition, arrival-order guarantee, exact ten-minute boundary rule, or whether a duplicate refreshes the stored occurrence. Make those choices explicit with the interviewer before selecting a data structure. Do not silently turn them into fixed source facts. ### Constraints & Assumptions - The ten-minute window, UUID identity, approximate throughput, single-instance memory bound, cleanup requirement, and latency target are source facts. - State which clock drives expiration: processing time, event time, or a caller-supplied timestamp. - State whether events can arrive out of order and how late arrivals are handled. - Ask whether an occurrence exactly ten minutes old is included or expired. - Ask whether every arrival refreshes an ID's expiration or only the first accepted arrival does. - Treat durability across process restarts and behavior under concurrent requests as product decisions, not implied requirements. ### Clarifying Questions to Ask - What does check-and-insert return, and must the check and insertion be atomic? - Which time source defines “past ten minutes,” at what precision, and what is the exact boundary predicate? - Can timestamps move backward or arrive late? - Does a duplicate extend the active window for that ID? - Are false positives or false negatives ever acceptable? - What memory budget and peak-rate multiplier must the instance withstand? ```hint Separate membership from expiration Use one structure for fast ID lookup and another expiration mechanism, but make their updates conditional on the confirmed clock, boundary, and refresh rules. ``` ### What a Strong Answer Covers - A precise statement of the missing boundary, ordering, clock, refresh, concurrency, and return semantics - A hash-based membership design paired with queue, heap, or timing-wheel expiration - Correct handling of stale expiration records when an ID is refreshed - Memory sizing from the ten-minute active set and compact UUID storage - Complexity, concurrency, cleanup, restart behavior, overload handling, and tests - A clear distinction between source-preserved facts and chosen design policy ### Follow-up Questions 1. How does the design change when events arrive out of event-time order? 2. What would you do if the estimated active set cannot fit within the instance's memory budget? 3. How would you shard the engine while keeping check-and-insert atomic for one notification ID?