## Design a Key-Value Store with Hit Counting Design an in-memory key-value store together with a hit-counter capability. The phrase "hit counter" is ambiguous, so first clarify whether it counts all requests, successful reads, writes, or activity in a time window, and whether counts are global or per key. For one concrete practice contract, support `put(key, value)`, `get(key)`, and `delete(key)`. A successful `get` increments that key's hit count. `getHits(key, now, window)` returns successful reads with timestamps in the half-open interval `(now - window, now]`. Operation timestamps are nondecreasing, keys and values are strings, and a missing `get` is not a hit. ### Constraints & Assumptions - A `put` replaces the current value but does not erase earlier hit history. - A `delete` removes the value; the practice contract retains hit history until it naturally expires. - `window` is positive, and one declared clock unit is used consistently. - All operations are linearizable in the single-process baseline. - Memory must be bounded in terms of live keys and hits retained inside the largest supported window. ### Clarifying Questions to Ask - Which operations count as hits, and do failed reads count? - Is the count global, per key, per caller, or available in several dimensions? - Is the time window fixed or chosen by each query? - Can timestamps arrive out of order? - Are TTL, persistence, concurrency, and process recovery in scope? ### Part 1 — Define State and Operations Give the class interfaces, return values, and invariants for key-value mutations, reads, and hit queries. Explain how the contract distinguishes a missing key from a stored empty string. #### What This Part Should Cover - Hash-map state for current values. - A precise hit event and window boundary. - Unambiguous missing-value and deletion behavior. - Complexity targets for each operation. ```hint Keep current value and history separate Replacing or deleting a value need not rewrite the already-recorded read events when the contract gives them different lifetimes. ``` ### Part 2 — Bound and Query Hit History Choose a representation for hit timestamps, evict expired events, and explain the trade-off between exact per-hit storage and bucketed counts. #### What This Part Should Cover - Monotonic-time cleanup without scanning every key on every request. - Exact deque storage for sparse hits. - Time buckets for high-volume keys and their precision cost. - Behavior after a long idle interval. ```hint Expire from the oldest edge With nondecreasing timestamps, only the oldest retained events can fall out of the current window first. ``` ### Part 3 — Make the Component Safe Under Load Discuss concurrent operations, hot keys, persistence, tests, and metrics. State what must change if callers supply out-of-order timestamps or arbitrary query windows. #### What This Part Should Cover - A lock or atomic boundary covering value lookup and successful-hit recording. - Sharding by key without multiplying counts. - Snapshot or log recovery if persistence is required. - Tests for exact boundaries, replacement, deletion, missing reads, and bursts. ```hint Define the read commit point If a successful read and its hit record are one logical operation, concurrency must not allow one to happen without the other. ``` ### What a Strong Answer Covers - Refuses to guess the hit-counter semantics and then applies one explicit contract consistently. - Separates current key-value state from time-bounded event state. - Gives feasible exact and bucketed designs with honest complexity and precision. - Handles concurrency, memory bounds, hot keys, and failure according to scope. ### Follow-up Questions 1. How would you answer several fixed windows, such as one minute and one hour, efficiently? 2. What changes if a missing `get` must also count as traffic? 3. How would you preserve exact counts across process restart? 4. How would you merge counters from several replicas without double counting retried reads?