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