Design a time-windowed key-value store

Implement a time-windowed key-value store ("Windowed Map") that receives key/value updates at irregular times and only keeps entries from the most recent window of length windowMs.

• Each key has a value (assume numeric, e.g., double or long) and a timestamp (milliseconds since epoch, e.g., from System.currentTimeMillis() or an injected clock).
• Data older than now - windowMs is expired and must be treated as invisible to the user and eligible for eviction.
• You may assume that at any moment, all currently valid entries fit in memory, but the entire lifetime of all entries does not (so you must expire/evict old data).
• Single-threaded only.

Provide these APIs and aim to make them as efficient as possible:

1. Get(key): if key exists and is not expired, return its value; otherwise return null (or throw).

   • Get does not update the timestamp.

2. Put(key, value): insert or update the key/value.

   • Each Put updates that key’s timestamp to now.

3. GetAverage(): return the average of all currently valid values in the window.

Example:

• Put("a", 10) at t=0
• Put("b", 20) at t=1
• GetAverage() returns 15.0
• After waiting 11 seconds (for a 10-second window):
  • Get("a") returns null (expired)
  • GetAverage() only considers still-valid keys.

Discuss the data structures you would use and the time complexity targets (e.g., O(1) average or worst-case, and what is or isn’t achievable).

Design a Time-Windowed Key-Value Store

Implement a batch simulator for a time-windowed key-value store. Each key maps to a numeric value and the timestamp of its most recent Put. The store only exposes entries whose timestamp is within the most recent window of length windowMs. For an operation at time now, an entry is valid if its timestamp is greater than or equal to now - windowMs; entries with timestamp less than now - windowMs are expired. Get does not refresh a key timestamp. Put inserts or updates a key and sets its timestamp to the operation timestamp. GetAverage returns the average of all currently valid values, or None if there are no valid entries. The operation timestamps are nondecreasing, simulating a single-threaded clock moving forward.

Constraints

• 0 <= windowMs <= 10^12
• 0 <= len(operations) <= 200000
• Operation timestamps are integers and are nondecreasing
• Keys are strings
• Values are numeric integers or floats
• All currently valid keys fit in memory, but the total lifetime of updates may be large

Hints

1. Use a hash map for direct key lookup, but also keep keys ordered by their latest update timestamp so expired entries can be removed from oldest to newest.
2. When Put updates an existing key, make sure the old value is removed from the running sum and the key is moved to the newest position. Get should not move the key.