Time Based Key-Value Store
Problem
Implement a time-based key-value store with set and get operations, where get returns the value associated with a key at the largest timestamp less than or equal to the given timestamp.
- All timestamps for set operations are strictly increasing for each key.
- 1 ≤ key.length, value.length ≤ 100
- 1 ≤ timestamp ≤ 10⁷
- At most 2 * 10⁵ calls will be made to set and get.
Example
set("foo", "bar", 1), get("foo", 1), get("foo", 3), set("foo", "bar2", 4), get("foo", 4), get("foo", 5)[null, "bar", "bar", null, "bar2", "bar2"]Initially, set("foo", "bar", 1) stores the value "bar" at timestamp 1. get("foo", 1) returns "bar" because the timestamp matches exactly. get("foo", 3) returns "bar" because the largest timestamp less than or equal to 3 is 1. Then set("foo", "bar2", 4) stores "bar2" at timestamp 4. get("foo", 4) returns "bar2" (exact match), and get("foo", 5) returns "bar2" because 4 is the largest timestamp <= 5.
Approach
Straightforward Solution
A naive approach would scan all stored timestamps for a key linearly to find the largest timestamp <= query timestamp, resulting in O(n) time per get call, which is inefficient for large inputs.
Core Observation
The problem requires retrieving the value associated with the largest timestamp less than or equal to a given timestamp. Since timestamps for each key are strictly increasing, the stored values form a sorted list by timestamp, enabling efficient binary search.
Path to Optimal
Recognizing that timestamps are strictly increasing for each key, the stored values can be maintained as a sorted list. This allows binary search to find the correct timestamp in O(log n) time. The key insight is to leverage this sorted order to perform efficient lookups instead of linear scans.
Optimal Approach
Store for each key a list of (value, timestamp) pairs sorted by timestamp. For get operations, perform a binary search on the timestamps to find the rightmost timestamp less than or equal to the query timestamp. Return the corresponding value or an empty string if none exists. This approach guarantees O(log n) time per get and O(1) amortized time per set.
Time
O(log n) per get, O(1) amortized per set
Each get operation performs a binary search on the sorted list of timestamps for a key, which takes O(log n) time where n is the number of timestamps for that key. Each set appends to the list in O(1) amortized time.
Space
O(n)
All set operations store values and timestamps in lists, requiring O(n) space proportional to the number of set calls. No additional significant auxiliary space is used.
Pattern Spotlight
Binary Search (Rightmost Element Search in Sorted Array)
When searching for the largest element less than or equal to a target in a sorted list, use binary search to find the rightmost position where the element satisfies the condition, enabling O(log n) retrieval.
Solution
| 1 | class TimeMap:
|
| 2 | def __init__(self):
|
| 3 | self.store = {}
|
| 4 |
|
| 5 | def set(self, key: str, value: str, timestamp: int) -> None:
|
| 6 | if key not in self.store:
|
| 7 | self.store[key] = []
|
| 8 | self.store[key].append([value, timestamp])
|
| 9 |
|
| 10 | def get(self, key: str, timestamp: int) -> str:
|
| 11 | res = ""
|
| 12 | values = self.store.get(key, [])
|
| 13 |
|
| 14 | l, r = 0, len(values) - 1
|
| 15 | while l <= r:
|
| 16 | m = (l + r) // 2
|
| 17 | if values[m][1] <= timestamp:
|
| 18 | res = values[m][0]
|
| 19 | l = m + 1
|
| 20 | else:
|
| 21 | r = m - 1
|
| 22 |
|
| 23 | return res |
| 1 | class TimeMap { |
| 2 | private Map<String, List<Entry>> store; |
| 3 | |
| 4 | private static class Entry { |
| 5 | String value; |
| 6 | int timestamp; |
| 7 | |
| 8 | Entry(String value, int timestamp) { |
| 9 | this.value = value; |
| 10 | this.timestamp = timestamp; |
| 11 | } |
| 12 | } |
| 13 | |
| 14 | public TimeMap() { |
| 15 | store = new HashMap<>(); |
| 16 | } |
| 17 | |
| 18 | public void set(String key, String value, int timestamp) { |
| 19 | if (!store.containsKey(key)) { |
| 20 | store.put(key, new ArrayList<>()); |
| 21 | } |
| 22 | store.get(key).add(new Entry(value, timestamp)); |
| 23 | } |
| 24 | |
| 25 | public String get(String key, int timestamp) { |
| 26 | if (!store.containsKey(key)) { |
| 27 | return ""; |
| 28 | } |
| 29 | |
| 30 | String res = ""; |
| 31 | List<Entry> values = store.get(key); |
| 32 | |
| 33 | int l = 0; |
| 34 | int r = values.size() - 1; |
| 35 | while (l <= r) { |
| 36 | int m = l + (r - l) / 2; |
| 37 | if (values.get(m).timestamp <= timestamp) { |
| 38 | res = values.get(m).value; |
| 39 | l = m + 1; |
| 40 | } else { |
| 41 | r = m - 1; |
| 42 | } |
| 43 | } |
| 44 | |
| 45 | return res; |
| 46 | } |
| 47 | } |
Step-by-Step Solution
Store Values and Timestamps in Sorted Lists per Key
| 3 | self.store = {}
|
| 6 | if key not in self.store:
|
| 7 | self.store[key] = []
|
| 8 | self.store[key].append([value, timestamp])
|
Objective
To maintain a mapping from keys to lists of (value, timestamp) pairs sorted by timestamp.
Key Insight
Since timestamps are strictly increasing for each key, appending new (value, timestamp) pairs to the list preserves sorted order. This structure enables efficient binary search later without additional sorting overhead.
Interview Quick-Check
Core Logic
Appending values with strictly increasing timestamps ensures the list remains sorted, which is essential for binary search.
Common Pitfalls & Bugs
Failing to maintain sorted order would prevent binary search from working correctly.
Perform Binary Search to Retrieve Value at or Before Timestamp
| 11 | res = ""
|
| 12 | values = self.store.get(key, [])
|
| 14 | l, r = 0, len(values) - 1
|
| 15 | while l <= r:
|
| 16 | m = (l + r) // 2
|
| 17 | if values[m][1] <= timestamp:
|
| 18 | res = values[m][0]
|
| 19 | l = m + 1
|
| 20 | else:
|
| 21 | r = m - 1
|
| 23 | return res |
Objective
To efficiently find the value associated with the largest timestamp less than or equal to the query timestamp using binary search.
Key Insight
Binary search narrows the search space by comparing the middle timestamp to the query timestamp, moving left or right pointers accordingly. By updating the result whenever a timestamp <= query is found, the algorithm ensures the rightmost valid timestamp is returned.
Interview Quick-Check
Core Logic
Binary search finds the rightmost timestamp <= query by moving the left pointer forward when the mid timestamp is valid, and the right pointer backward otherwise.
State & Boundaries
The loop continues while left <= right, ensuring all candidates are considered.
Common Pitfalls & Bugs
Not updating the result when a valid timestamp is found can cause incorrect returns.
Complexity
Binary search reduces the search space logarithmically, enabling O(log n) retrieval.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
self.store[key].append([value, timestamp])Append the new value-timestamp pair.
Appending works because timestamps are inserted in increasing order, so the per-key history stays sorted.
if values[m][1] <= timestamp:Check whether the midpoint timestamp is valid for the query.
A midpoint timestamp less than or equal to the query is a valid candidate answer.
res = values[m][0]Update the result with the midpoint value.
When the midpoint timestamp is valid, its value becomes the best answer seen so far.
return resReturn the resolved value.
Returning the stored result satisfies the requirement to return the value at the greatest timestamp not exceeding the query, or empty if none exists.
self.store = {}Initialize the main storage dictionary.
The main dictionary stores each key's timestamped history and is the foundation of the data structure.
l = m + 1Move the left pointer rightward.
Moving left rightward continues searching for a later timestamp that still satisfies the constraint.
else:Enter the branch that discards timestamps greater than the query.
If the midpoint timestamp is too large, the search must continue on the left side.
r = m - 1Move the right pointer leftward.
Moving right leftward removes timestamps that are too large to be valid answers.
if key not in self.store:Check whether the key is missing from storage.
A new key needs its own history list before timestamped values can be appended.
self.store[key] = []Create a history list for a new key.
Creating the list preserves the invariant that every stored key maps to a list of timestamped values.
values = self.store.get(key, [])Load the timestamped history for the key, or an empty list.
Missing keys are handled safely by falling back to an empty list.
l, r = 0, len(values) - 1Initialize the binary search boundaries.
These pointers define the current binary search interval over the timestamp list.
while l <= r:Binary search while the interval is valid.
The loop narrows the search to find the rightmost timestamp not exceeding the query.
m = (l + r) // 2Compute the midpoint index.
The midpoint splits the remaining candidate timestamps for the next decision.
res = ""Initialize the result to the empty string.
The answer starts empty so the function still returns the correct value if no valid timestamp is found.
Test Your Understanding
Why is binary search the appropriate method to find the value for a given timestamp in this problem?
Because the timestamps for each key are strictly increasing, the stored values form a sorted list by timestamp, allowing binary search to efficiently find the largest timestamp less than or equal to the query timestamp in O(log n) time, which is much faster than linear search.
Related Problems
Binary Search pattern
Don't just read it. Drill it.
Reconstruct Time Based Key-Value Store from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Time Based Key-Value Store drill