Load Monitoring Store

Medium

Design · Databricks

Implement a key-value store that can report its recent load. operations is processed in order, and every operation produces one entry in the output list:

["put", time, key, value]: store value under key (overwriting any previous value). Output None.
["get", time, key]: output the value stored under key, or "" if the key was never stored.
["put_load", time]: output how many put operations so far have a timestamp t with time - window < t <= time.
["get_load", time]: the same count, for get operations.

So a load query looks back over the last window time units, including time itself. Load queries are not counted as operations. Timestamps are non-decreasing across all operations, and operations sharing a timestamp are processed in list order (a load query counts the earlier operations at its own timestamp).

Return the list of outputs.

Example 1

Input:: operations = [["put", 1, "a", "x"], ["get", 2, "a"], ["put", 3, "a", "y"], ["get", 4, "b"], ["get_load", 5], ["put_load", 6], ["get", 8, "a"], ["get_load", 8]], window = 5
Output:: [None, "x", None, "", 2, 1, "y", 2]
Explanation: A put returns None; gets return the stored value or "". At time 5 the window covers times 1 to 5, holding gets at 2 and 4. At time 6 it covers 2 to 6, so only the put at 3 counts. At time 8 it covers 4 to 8: the gets at 4 and 8.

Example 2

Input:: operations = [["get_load", 10], ["put_load", 10]], window = 5
Output:: [0, 0]
Explanation: Nothing has happened yet, so both loads are 0.

Example 3

Input:: operations = [["put", 0, "k", "v"], ["put", 0, "k", "w"], ["get", 0, "k"], ["put_load", 1], ["put_load", 2]], window = 2
Output:: [None, None, "w", 2, 0]
Explanation: With a window of 2, the query at time 1 covers times 0 and 1, so both puts count. At time 2 the window covers 1 to 2, and puts at time 0 are no longer included. The second put overwrote the value, so the get returns "w".

Constraints

0 <= operations.length <= 10^5
0 <= time <= 10^9, non-decreasing across operations
1 <= window <= 10^9
Keys and values are strings