In-Memory Key-Value Store with a Per-Key 5-Minute Query Threshold
Company: Databricks
Role: Software Engineer
Category: Software Engineering Fundamentals
Difficulty: medium
Interview Round: Onsite
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?
Overview: Design an in-memory key-value store whose lookups return false once a key has been queried more than a threshold number of times in the past five minutes. Follow-ups cover stream input with a priority queue, many concurrent worker readers, and exact sliding-window counting with bounded memory.
Community answers
Answer by dwivediaman7601
**## Part 1:
Clarification Question
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?
| // Time: O(1)
// Space: O(U+K) here U is unique keys and K is active queries stored in the queue within the window.
#include
#include
#include
#include
class KVStoreQueueBase {
private:
int threshold;
const long long WINDOW_SIZE = 300; // 5 minutes
struct KeyRecord {
std::string value;
std::queue timestamps;
};
std::unordered_map store;
public:
struct Result {
enum Status { NOT_FOUND, RATE_LIMITED, SUCCESS } status;
std::string value;
};
explicit KVStoreQueueBase(int threshold) : threshold(threshold) {}
void put(const std::string& key, const std::string& value, long long timestamp) {
store[key].value = value;
}
Result get(const std::string& key, long long timestamp) {
auto it = store.find(key);
if (it == store.end()) return {Result::NOT_FOUND, ""};
auto& record = it->second;
// Slide window: pop timestamps older than 300 seconds
while (!record.timestamps.empty() && (timestamp - record.timestamps.front()) >= WINDOW_SIZE) {
record.timestamps.pop();
}
// Check threshold limit
if (record.timestamps.size() >= static_cast(threshold)) {
return {Result::RATE_LIMITED, ""};
}
// Record curr