Design a Near-Real-Time Top-K Customers by Purchases in a Sliding 60-Minute Window

Design a system that maintains the top K customers ranked by how many purchases each made in the last 60 minutes. The window slides: a purchase stops counting 60 minutes after it happened, and the ranking must be updated in near real time as new purchases arrive and old ones drop out. The report states only this requirement, so the purchase volume, the value of K, the freshness target and the readers of the ranking are open: agree on them with the interviewer before designing. ```hint Counts go down too In a sliding window a customer's count falls when an old purchase expires. Think about which data structures keep a ranking correct under both increments and decrements. ``` ```hint How exact must the window be Ask whether the window has to move with every event or may advance in small fixed steps, and what that choice saves in state. ``` ### Clarifying Questions - How many purchases per second arrive on average and at peak, and how many distinct customers buy within an hour? - How large is K, and is the ranking global or per segment, such as per country or per merchant? - What does "near real time" mean here: within a second, a few seconds, or a minute? Who reads the ranking, and how often? - Must the window slide continuously, or may it advance in steps such as one second or one minute? - Do refunds or cancelled purchases remove a purchase from the count? Can purchase events arrive late or twice? - How should ties at the K-th position be broken? ### What a Strong Answer Covers - Requirements, an estimate of event rate and customer cardinality, and agreed window semantics - An ingestion path that partitions purchase events by customer and deduplicates them - Per-customer sliding-window counts with expiry, and the memory they need - A ranking structure that supports increments and decrements, and a correct merge of per-partition top-K lists into a global one - How the ranking is served with low latency and bounded staleness - Event-time handling, late and duplicate events, failure recovery, hot customers and monitoring ### Follow-up Questions - The number of distinct customers per hour grows tenfold and exact counts no longer fit in memory. What approximation would you use, and what error does it allow? - How would you support several windows at once, such as 5, 60 and 1,440 minutes, without three separate pipelines? - A partition's processor crashes. How do you restore its window state without double counting? - How would you show that merging per-partition top-K lists returns the exact global top K?