Windowed Key-Value Map
Updated
Problem statement
Implement a key-value map whose entries remain active for a fixed time window. You are given the window length windowSeconds and a chronological array of commands operations. Each command begins with a nondecreasing integer timestamp in seconds.
The supported commands are:
put timestamp key value: insert or replacekeywith the integervalue. The new value is active during[timestamp, timestamp + windowSeconds).get timestamp key: append the active value forkeyto the output, or appendNOT_FOUNDwhen the key is absent or expired.delete timestamp key: remove the key if it is active. This command produces no output.average timestamp: append the average of all active values. AppendEMPTYwhen no value is active. Otherwise return the exact reduced fractionnumerator/denominator; when the denominator is1, return only the numerator.
Before applying any command at time timestamp, all entries whose expiry time is at most timestamp are inactive. Replacing a key removes its previous value and expiry before adding the new entry. Return the outputs from get and average commands in order.
The follow-up asks how to keep frequent average queries efficient and how the structure changes when several threads call the API concurrently.
Further discussion
- This is sometimes called an LRU cache with TTL, but the operations are timestamped add/get and the average of all active values, with no capacity limit or recency eviction. Keep the fixed-lifetime map rules above; reading a key does not renew its expiry.
- Timestamps need not be strictly increasing: this exercise permits equal timestamps and processes them in input order. Explain why monotonic time and a fixed lifetime allow expiration records to stay ordered.
- Compare read-heavy and write-heavy workloads, memory use, hash collisions, frequent average requests, and concurrent calls. Keep expiry, replacement, active count and active sum consistent.
Function
processWindowedMap(operations: String[], windowSeconds: int) → String[]Examples
Example 1
operations = ["put 0 a 10","put 1 b 20","average 2","get 5 a","average 5"]windowSeconds = 5return = ["15","NOT_FOUND","20"]At time 2, both values are active, so the average is 30/2 = 15. Entry a expires at time 5, while b remains active until time 6.
Example 2
operations = ["put 3 x 4","put 4 x 9","get 7 x","average 7","delete 8 x","average 8"]windowSeconds = 5return = ["9","9","EMPTY"]The second put replaces the old value and resets x's expiry to time 9. Deleting it at time 8 leaves the map empty.
Example 3
operations = ["put 0 a -2","put 0 b 5","average 0"]windowSeconds = 10return = ["3/2"]The active sum is 3 across two entries, so the exact average is the reduced fraction 3/2.
Constraints
1 <= operations.length <= 100000.1 <= windowSeconds <= 10^9.- Command timestamps are integers in
[0, 10^9]and are nondecreasing. - Every key contains only ASCII letters, digits, underscores, and hyphens and has length from
1through30. - Every inserted value is an integer in
[-10^9, 10^9]. - The exact active-value sum fits in a signed 64-bit integer.
- Every command has exactly the fields shown in the statement.