How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Databricks.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Databricks during technical interviews.

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

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.

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.

Input: [("PUT", 1, "a", 1), ("PUT", 3, "b", 2), ("DELETE", 6, "a"), ("AVG_QPS", 6, 3), ("AVG_QPS", 6, 5)]

Expected Output: [0.3333333333333333, 0.4]

Explanation: For window 3, the interval is (3, 6], so timestamp 3 is excluded and only timestamp 6 counts: 1 / 3. For window 5, the interval is (1, 6], so timestamps 3 and 6 count: 2 / 5.

Input: [("DELETE", 2, "ghost"), ("PUT", 4, "a", 7), ("DELETE", 10, "a"), ("AVG_QPS", 10, 10), ("AVG_QPS", 10, 6)]

Expected Output: [0.3, 0.16666666666666666]

Explanation: DELETE on a missing key still counts as a mutation. In (0, 10], all three mutations count, so 3 / 10 = 0.3. In (4, 10], timestamp 4 is excluded, so only the DELETE at 10 counts: 1 / 6.

Input: [("AVG_QPS", 7, 4)]

Expected Output: [0.0]

Explanation: No mutation operations have occurred before the query, so the count is 0 and the average QPS is 0.0.

Input: []

Expected Output: []

Explanation: With no operations, there are no AVG_QPS results to return.

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.

Quick Overview