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).
PUT
/
DELETE
updates.
AVG_QPS
should be efficient over many operations (avoid scanning the full history each time).
windowSeconds
is not fixed (e.g., not always 300 seconds); it varies per query.
Implement a function that processes the operations in order and outputs a list of results for each AVG_QPS operation.
N
up to
2 * 10^5
.
10^9
.
windowSeconds
up to
10^5
.
Operations:
PUT 10 a 1
PUT 11 b 2
DELETE 13 a
AVG_QPS 13 5
Mutation operations in (8, 13] are 3, so result is 3/5 = 0.6.