Design KV store with sliding-window average QPS

Quick Overview

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.

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`.

Overview: 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.

Constraints

0 <= len(operations) <= 2 * 10^5
Timestamps are non-decreasing integers in the range [0, 10^9]
1 <= windowSeconds <= 10^5
Keys are strings; values can be any Python literal
DELETE counts as a mutation even if the key is absent

Examples

Input: [("PUT", 10, "a", "1"), ("PUT", 11, "b", "2"), ("DELETE", 13, "a"), ("AVG_QPS", 13, 5)]

Expected Output: [0.6]

Explanation: Mutation timestamps are 10, 11, and 13. In the interval (8, 13], all 3 are included, so the answer is 3 / 5 = 0.6.

Input: [("PUT", 5, "x", 1), ("AVG_QPS", 5, 5), ("DELETE", 5, "y"), ("AVG_QPS", 5, 5)]

Expected Output: [0.2, 0.4]

Explanation: At the first query, only the earlier PUT at timestamp 5 has been processed, so the count is 1. At the second query, both the PUT and DELETE at timestamp 5 have been processed, so the count is 2.

Hints

The QPS calculation depends only on mutation timestamps, not on stored values. Try keeping the timestamps of PUT and DELETE operations in sorted order as you process the list.
For a query at time t, use binary search to find how many processed mutation timestamps are greater than t - windowSeconds and less than or equal to t.

Approach

Approach. We replay operations in order, keeping a running, append-only list mutation_times of the timestamps of every PUT/DELETE already processed. Because every AVG_QPS query is answered from only the mutations seen so far, the "same-timestamp ties count only earlier list positions" rule is satisfied for free — later mutations simply aren't in the list yet.

Key steps.

PUT (_, t, key, value): set store[key] = value, then mutation_times.append(t).
DELETE (_, t, key): remove key if present (state-only effect), then mutation_times.append(t) — a DELETE always counts as a mutation even when the key is absent.
AVG_QPS (_, t, windowSeconds): count mutations whose timestamp lies in the half-open interval (t - windowSeconds, t], then divide by windowSeconds.

Why the boundaries are right. Constraints guarantee timestamps are non-decreasing, so mutation_times is sorted and we can use binary search. bisect_right(mutation_times, t - windowSeconds) returns the first index strictly past the left bound, making the left side exclusive. bisect_right(mutation_times, t) counts everything <= t, making the right side inclusive. The difference end - start is exactly the number of qualifying mutations; dividing by windowSeconds yields the average QPS over the window.

Data structures. A dict tracks live KV state (needed so DELETE semantics are realistic, though state doesn't affect QPS), and a sorted list mutation_times enables O(log N) range counting per query. An unknown op type raises ValueError. The empty-input case returns [] naturally.

Time complexity:

O(N log N)

Space complexity:

O(N)