Problem Description

Implement a time-windowed key-value store (referred to as a "Windowed Map") that processes key/value updates at irregular intervals. The store must only retain and expose entries that fall within the most recent window of a specified length, windowMs.

Each entry in the store consists of a key, a value (which can be assumed to be a numeric type like double or long), and a timestamp (representing milliseconds since epoch, obtainable from System.currentTimeMillis() or an injected clock).

Data points with timestamps older than now - windowMs are considered expired. Expired data must be treated as invisible to users and is eligible for eviction from memory.

Assumptions & Constraints

• At any given moment, all currently valid entries are guaranteed to fit within available memory. However, the cumulative lifetime of all entries (including expired ones) will exceed memory capacity, necessitating proper expiration and eviction mechanisms.
• The system is strictly single-threaded.

API Requirements

Provide the following APIs, aiming for the highest possible efficiency:

1. Get(key):

   • If the key exists and its associated entry is not expired, return its value.
   • Otherwise, return null (or throw an appropriate exception).
   • Calling Get must not update the key's timestamp.

2. Put(key, value):

   • Inserts a new key/value pair or updates an existing one.
   • Each Put operation must update that key’s timestamp to the current now.

3. GetAverage():

   • Return the average of all values belonging to currently valid entries within the window.

Example Scenario

• Put("a", 10) at t=0
• Put("b", 20) at t=1
• GetAverage() returns 15.0
• After waiting 11 seconds (assuming a windowMs of 10 seconds):
  • Get("a") returns null (as it has expired).
  • GetAverage() will only consider still-valid keys in its calculation.

Discussion Points

Candidates should be prepared to discuss:

• The data structures they would use to implement this system.
• The target time complexity for each API (e.g., O(1) average or worst-case), and what complexities are realistically achievable.