Design KV store with sliding-window average QPS

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.