In-Memory Key-Value Store with a Per-Key 5-Minute Query Threshold

You are building an in-memory key-value store that also protects itself from hot keys. Besides storing and returning values, the store must enforce a 5-minute query-rate check per key. When a key is queried, if that key has been queried more than a configured threshold number of times within the past 5 minutes, the query must return `False` instead of the value. Assume the caller passes a timestamp (in seconds) with every call, so the behavior is deterministic and testable, and that the threshold is a single integer shared by all keys. Implement the core store first. The interviewer then asks three follow-ups, in order. ### Constraints and Clarifications - The window is the last 5 minutes (300 seconds) relative to the timestamp of the current query. - The threshold is a fixed positive integer given at construction. - Values are opaque, and the store does not need to persist anything. ### Clarifying Questions - Does a query that is rejected with `False` still count toward the key's count, or do only served queries count? - Is the limit crossed when the count in the window is strictly greater than the threshold, and does that count include the current query? - In the base version, do timestamps arrive in non-decreasing order? - Do writes (`put`) count as queries, or only reads? ### Part 1 — Core store with the 5-minute check Implement `put(key, value, timestamp)` and `get(key, timestamp)`. `get` returns the stored value (or `None` for a missing key), unless the key has exceeded the threshold within the past 5 minutes, in which case it returns `False`. State the time and space complexity of both operations. ```hint Per-key history Think about what data you must keep per key so that entries older than the window can be discarded cheaply as time moves forward. ``` #### What This Part Should Cover - A per-key record of recent query times, and how it expires as the window slides - Exact threshold semantics that match the answers to the clarifying questions - Time and space complexity per operation and per key ### Part 2 — Queries arrive as a stream The input is now a stream of query events rather than individual method calls. How does the design change? The interviewer's hint was to use a priority queue. ```hint Why a heap Ask what a heap ordered by time lets you do across all keys at once that per-key structures cannot, and whether events in the stream are guaranteed to arrive in time order. ``` #### Clarifying Questions for this Part - Can stream events arrive out of timestamp order, and if so, by how much? - Is the stream unbounded, so that memory held for keys that stop being queried becomes a problem? #### What This Part Should Cover - What the priority queue is keyed on and what it enables: global expiry, reordering, or both - How memory stays bounded as keys go cold in an unbounded stream - Cost per event, including heap operations ### Part 3 — One server, many worker readers A single server holds the store, and multiple workers read from it concurrently. What must change? ```hint The check is a write Every read updates the key's query history. Consider what happens when two workers check the same key at the same instant, just below the threshold. ``` #### What This Part Should Cover - The race in the check-then-record step, and how to make that step atomic - Lock granularity (global, per key, striped) and its contention trade-offs - What changes if the workers are separate processes rather than threads ### Part 4 — More precise counting A query needs the past 5 minutes of data. Should old data be thrown away? If it is simply dropped, the count becomes imprecise. How do you keep the statistic precise? The interviewer's hint: work out the relationship between the 5-minute window and the "query count exceeds threshold" condition. ```hint Relate window and threshold Ask how many of a key's past query times can ever affect whether the next query is allowed. ``` #### What This Part Should Cover - Why coarse buckets or fixed windows lose precision at the window boundary - An exact scheme whose per-key memory is bounded by something other than traffic volume - The precision versus memory trade-off of the alternatives ### What a Strong Answer Covers - Precise, stated semantics for the window boundary and for counting rejected queries - A clean, working baseline written quickly, leaving time for the follow-ups - Per-key and global memory bounds, both for hot keys and for many cold keys - Correctness under concurrency, not just single-threaded behavior - Honest complexity analysis for each follow-up variant ### Follow-up Questions - How would you make the threshold differ per key or per client, and change it at runtime? - If the store were sharded across several servers, how would you enforce the limit for one key? - How would you expose metrics so operators can see which keys are being throttled?