Windowed Map (Time-Windowed Key-Value Store) with O(1) Operations and Window Average

Windowed Key-Value Store Medium · Topics · Company Tags · Hints

Design a time-windowed key-value store that retains only the entries updated within a specified duration W from the current moment. Updates can occur at arbitrary times, and the system must automatically discard entries that fall outside the window. Expired entries should be invisible to read operations and must be removed from memory to prevent unbounded growth.

You must implement the following three methods. The interviewer expects worst‑case O(1) time for each operation.

1) Get(key)

• If key is present and its last update timestamp lies within the window (i.e., currentTime - timestamp <= W), return its associated value.
• Otherwise return null.
• Required: O(1)
• Calling Get does not alter the timestamp of the entry.

2) Put(key, value)

• Insert or update the mapping key → value.
• Record the current system time as the key’s timestamp.
• Required: O(1)

3) GetAverage()

• Compute and return the arithmetic mean of all non‑expired values currently in the store.
• If no valid entries exist, return 0.0.
• Goal: O(1) worst‑case.

---

Time & Expiration Details

• Use system time (e.g., System.currentTimeMillis()) to obtain the current timestamp.
• W is given in the same time unit as system time (milliseconds for Java implementations).
• An entry is considered expired when currentTime - entry.timestamp > W.

---

Constraints & Assumptions

• The number of valid entries inside the window at any instant fits comfortably in memory.
• Over the lifetime of the store the total number of updates may be arbitrarily large, so stale data must be physically evicted.
• Operations are single‑threaded; no concurrency support is needed.
• Get reads without refreshing timestamps; only Put records a new timestamp.

---

Example 1:

Input:
W = 10
Put("a", 10) at t = 0
Put("b", 20) at t = 1
GetAverage() at t = 1

Output: 15.0

Explanation: Both "a" (10) and "b" (20) are valid at t=1, so average = (10+20)/2 = 15.

Example 2:

Input:
W = 10
Put("a", 10) at t = 0
Put("b", 20) at t = 1
// wait until t = 12
Get("a") at t = 12
GetAverage() at t = 12

Output:
null
20.0

Explanation: At t=12, "a" has timestamp 0 and is expired (12-0 > 10). "b" with timestamp 1 is still valid (12-1 <= 10). GetAverage returns 20.0.

Example 3:

Input:
W = 10
GetAverage() at t = 0

Output: 0.0

Constraints:

• W > 0
• Keys and values are non‑null
• The store may hold at most N valid entries at any time, where N fits in standard heap memory
• Lazy or eager eviction is acceptable, provided Get and GetAverage never see expired data
• All three operations must achieve O(1) worst‑case time complexity