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).