You're given a time-based key-value store that keeps having new key-value pairs added. Implement a windowed average.

To implement a windowed average for a time-based key-value store, we need to efficiently track values within a specified time window for relevant keys. A common approach involves using a data structure that supports time-based querying and aggregation.

One effective method is to maintain a collection of time-stamped key-value pairs. When a new pair arrives, we add it to our collection. To calculate the windowed average for a given key and time t with window size w, we would query for all entries associated with that key where the timestamp falls within the range (t - w, t). The average is then computed by summing the values of these entries and dividing by the count of entries within the window.

For performance, especially with frequent updates and queries, consider using a data structure like a time-series database or a specialized in-memory structure. A sliding window approach can be optimized by maintaining a running sum and count. When a new value arrives, add it to the sum and increment the count. Concurrently, remove values that have fallen outside the window (i.e., their timestamp is older than t - w) from the sum and decrement the count. This avoids re-scanning the entire history for each average calculation.