Design KV store with sliding-window average QPS
Company: Databricks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
Design an in-memory key–value store that supports mutation operations and can report the **average QPS (queries per second)** over a recent time window.
You are given a sequence of operations with **non-decreasing integer timestamps** (in seconds). Each operation is one of:
- `PUT t key value` — store/update `key -> value` at time `t`.
- `DELETE t key` — delete `key` at time `t` if it exists.
- `AVG_QPS t windowSeconds` — return the **average QPS** over the last `windowSeconds` seconds ending at time `t`.
For `AVG_QPS`, define the numerator as the number of **mutation requests** (`PUT` + `DELETE`, regardless of whether the key existed) whose timestamps are in the interval:
- `(t - windowSeconds, t]`
The result is:
- `count / windowSeconds`
Return the answer as a floating-point number (double).
### Requirements
- The key–value store must correctly apply `PUT`/`DELETE` updates.
- `AVG_QPS` should be efficient over many operations (avoid scanning the full history each time).
- Follow-up: `windowSeconds` is not fixed (e.g., not always 300 seconds); it varies per query.
### Input/Output format (for testing)
Implement a function that processes the operations in order and outputs a list of results for each `AVG_QPS` operation.
### Constraints (assume)
- Number of operations `N` up to `2 * 10^5`.
- Timestamps up to `10^9`.
- `windowSeconds` up to `10^5`.
- Operation timestamps are non-decreasing.
### Example
Operations:
1. `PUT 10 a 1`
2. `PUT 11 b 2`
3. `DELETE 13 a`
4. `AVG_QPS 13 5`
Mutation operations in `(8, 13]` are 3, so result is `3/5 = 0.6`.
Quick Answer: This question evaluates a candidate's ability to design an in-memory key–value store and compute average QPS over a sliding time window, testing competencies in time-windowed aggregation, handling mutation operations, and maintaining efficient update/query performance.
Implement an in-memory key-value store that processes operations in order and reports the average QPS (queries per second) over a recent time window.
Each operation is represented as a tuple in one of these forms:
- ("PUT", t, key, value): store or update key -> value at timestamp t.
- ("DELETE", t, key): delete key at timestamp t if it exists.
- ("AVG_QPS", t, windowSeconds): return the average QPS over the interval (t - windowSeconds, t].
For AVG_QPS, the numerator is the number of mutation requests already processed so far whose timestamps fall in (t - windowSeconds, t]. Mutation requests are PUT and DELETE operations. DELETE counts even if the key does not exist.
Important: operations are processed strictly in the given order. If multiple operations have the same timestamp, an AVG_QPS query only counts mutation operations that appeared earlier in the list.
Return a list containing the result of every AVG_QPS operation, in order.