How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at StackAdapt.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at StackAdapt during technical interviews.

Design a time-windowed key-value store | StackAdapt Coding Question

Design a time-windowed key-value store

Company: StackAdapt

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

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

Quick Answer: This question evaluates a candidate's ability to design efficient data structures and algorithms for a time-windowed key-value store, focusing on expiration handling, update semantics, and maintaining aggregate metrics under memory constraints.

Implement a batch simulator for a time-windowed key-value store. Each key maps to a numeric value and the timestamp of its most recent Put. The store only exposes entries whose timestamp is within the most recent window of length windowMs. For an operation at time now, an entry is valid if its timestamp is greater than or equal to now - windowMs; entries with timestamp less than now - windowMs are expired. Get does not refresh a key timestamp. Put inserts or updates a key and sets its timestamp to the operation timestamp. GetAverage returns the average of all currently valid values, or None if there are no valid entries. The operation timestamps are nondecreasing, simulating a single-threaded clock moving forward.

Constraints

0 <= windowMs <= 10^12
0 <= len(operations) <= 200000
Operation timestamps are integers and are nondecreasing
Keys are strings
Values are numeric integers or floats
All currently valid keys fit in memory, but the total lifetime of updates may be large

Examples

Input: (10000, [['put', 0, 'a', 10], ['put', 1, 'b', 20], ['avg', 1], ['get', 10000, 'a'], ['avg', 10001], ['get', 10001, 'a']])

Expected Output: [15.0, 10, 20.0, None]

Explanation: At t=1 both a and b are valid, so the average is 15.0. At t=10000, a is exactly on the boundary and is still valid. At t=10001, a is expired but b is still valid.

Input: (5, [['put', 0, 'x', 10], ['put', 2, 'y', 30], ['put', 4, 'x', 20], ['avg', 4], ['get', 6, 'x'], ['get', 6, 'y'], ['avg', 8]])

Expected Output: [25.0, 20, 30, 20.0]

Explanation: Updating x replaces its old value and timestamp. At t=4, x=20 and y=30, average 25.0. At t=8, y's timestamp 2 is outside the window, leaving only x.

Input: (0, [['put', 5, 'a', 1], ['put', 5, 'b', 3], ['avg', 5], ['get', 5, 'a'], ['avg', 6], ['put', 6, 'a', 7], ['get', 6, 'a'], ['avg', 6]])

Expected Output: [2.0, 1, None, 7, 7.0]

Explanation: With a zero-length window, only entries with timestamp exactly equal to now are valid. The entries from t=5 expire at t=6.

Input: (10, [['put', 100, 'a', -5], ['put', 105, 'b', 15], ['avg', 106], ['put', 111, 'c', -10], ['avg', 111], ['get', 111, 'a'], ['avg', 116]])

Expected Output: [5.0, 2.5, None, -10.0]

Explanation: Negative values are included in the running average. At t=111, a has expired, so b and c average to 2.5. At t=116, only c remains valid.

Input: (10, [])

Expected Output: []

Explanation: There are no operations, so there are no query results.

Input: (3, [['put', 0, 'k', 5], ['get', 3, 'k'], ['get', 4, 'k'], ['avg', 4]])

Expected Output: [5, None, None]

Explanation: At t=3, k is exactly on the boundary and valid. At t=4, it is older than now - windowMs and has expired.

Hints

Use a hash map for direct key lookup, but also keep keys ordered by their latest update timestamp so expired entries can be removed from oldest to newest.
When Put updates an existing key, make sure the old value is removed from the running sum and the key is moved to the newest position. Get should not move the key.

Quick Overview

This question evaluates a candidate's ability to design efficient data structures and algorithms for a time-windowed key-value store, focusing on expiration handling, update semantics, and maintaining aggregate metrics under memory constraints.