How do you approach Time Based Key-Value Store?

Store, per key, two parallel arrays: the timestamps (already sorted because sets are increasing) and the corresponding values.

What is the time complexity of Time Based Key-Value Store?

Time complexity: set is O(1) amortized; get is O(log n) per key via binary search.. Space complexity: O(n) across all stored entries..

What are common mistakes on Time Based Key-Value Store?

Hitting the stated complexity for one operation by making another linear. These problems grade every operation. Keeping two structures in sync but updating only one of them on the delete path. Skipping the capacity edges: insert when full, read when empty.

gitGood.dev

← Back to problems

Time Based Key-Value Store

MediumObject-Oriented Design

Description

Design a time-based key-value store that can store multiple values for the same key at different timestamps and retrieve the value as of a given time. - `set(key, value, timestamp)` stores `value` for `key` at the given `timestamp`. - `get(key, timestamp)` returns the value that was set with the largest stored timestamp that is `<= timestamp`. If there is no such value, return the empty string `""`. For each key, the `set` calls are made with strictly increasing timestamps. Implement the function `timeMap(operations)` where `operations` is a list of `[op, ...args]`: `["set", key, value, timestamp]` and `["get", key, timestamp]`. For `"set"` return `null`; for `"get"` return the resolved value (or `""`). Return the list of results, one per operation (use null for operations that return nothing).

Example 1

Input: operations = [["set","foo","bar",1],["get","foo",1],["get","foo",3],["set","foo","bar2",4],["get","foo",4],["get","foo",5]]

Output: [null, "bar", "bar", null, "bar2", "bar2"]

Example 2

Input: operations = [["get","x",1],["set","x","a",5],["get","x",1],["get","x",5],["get","x",10]]

Output: ["", null, "", "a", "a"]

Example 3

Input: operations = [["set","k","v1",10],["set","k","v2",20],["set","k","v3",30],["get","k",15],["get","k",25],["get","k",30]]

Output: [null, null, null, "v1", "v2", "v3"]

Constraints

1 <= key, value length <= 100. 1 <= timestamp <= 10^7. For a given key, set timestamps are strictly increasing. At most 20000 operations. get should be faster than linear scan - use binary search.

Time Based Key-Value Store: approach, complexity and pitfalls

A medium design problem, graded against 6 test cases (3 of them hidden).

The pattern: Design

Build a working data structure to an API - LRU caches, rate limiters, and iterators.

Reach for it when you see: "Design a class supporting these operations in O(1)" - an API rather than a single function.

More Designproblems →

If you are stuck

Show the 3-step hint ladder

Store, per key, two parallel arrays: the timestamps (already sorted because sets are increasing) and the corresponding values.
For get(key, timestamp), binary search the timestamps for the rightmost entry that is <= timestamp. In Python, bisect.bisect_right gives the insertion point; the answer is at index - 1.
If the binary search lands at index 0 (no timestamp <= the query) or the key was never set, return the empty string.

The optimal approach

Show the approach: The approach

Maintain a map from key to two parallel lists: sorted `times` and matching `values`. Because `set` timestamps for a key strictly increase, appends keep `times` sorted. For `get`, binary search for the rightmost timestamp `<= query` (an upper-bound search, then step back one). If that index is before the start, or the key is unknown, return the empty string.

Time: set is O(1) amortized; get is O(log n) per key via binary search.
Space: O(n) across all stored entries.

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Design mistakes

These apply to the pattern as a whole, not just this problem.

Hitting the stated complexity for one operation by making another linear. These problems grade every operation.
Keeping two structures in sync but updating only one of them on the delete path.
Skipping the capacity edges: insert when full, read when empty.