981. Time Based Key-Value Store
Asked at Apple, Databricks, Netflix, OpenAI and 1 more
Difficulty
Medium
Time
set: O(1) amortized; get: O(log
Space
O(n) for all stored entries
Pattern
Hash Table
Companies
5
Problem
Design a data structure that works like a key-value store, but each value is saved together with a timestamp. The same key can be saved many times at different timestamps.
Implement a class TimeMap with two methods. set(key, value, timestamp) saves value under key at that timestamp. get(key, timestamp) returns the value saved for key at the largest timestamp that is less than or equal to the given one. If no such entry exists, return an empty string "".
Timestamps passed to set always come in strictly increasing order. That means the entries for any single key are already sorted by time, so you can use binary search on them instead of scanning.
Save many values per key, read the newest one in range
Constraints
- ●
1 <= key.length, value.length <= 100 - ●
key and value consist of lowercase English letters and digits - ●
1 <= timestamp <= 10^7 - ●
All timestamps passed to set are strictly increasing - ●
At most 2 * 10^5 calls will be made to set and get
Examples
["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]][null, null, "bar", "bar", null, "bar2", "bar2"]["TimeMap", "get", "set", "get"]
[[], ["a", 1], ["a", "x", 5], ["a", 3]][null, "", null, ""]Asked At
5 companies| Company | Difficulty | |
|---|---|---|
| Apple | Medium | View all Apple questions → |
| Databricks | Medium | View all Databricks questions → |
| Netflix | Medium | View all Netflix questions → |
| OpenAI | Medium | View all OpenAI questions → |
| Oracle | Medium | View all Oracle questions → |
How to Think About It
Brute force: store every (key, timestamp, value) triple. For get(key, t), scan all entries for that key and find the one with the largest timestamp <= t. That's O(n) per get call, too slow for millions of calls.
Key insight: timestamps for each key are always inserted in increasing order. That means for each key, the list of timestamps is already sorted. Sorted data + lookup = binary search.
Data structure: use a hash map where each key maps to a list of [timestamp, value] pairs. Since set() is called with increasing timestamps, the list for each key is naturally sorted by timestamp. No need to sort explicitly.
The get(key, t) operation: look up the key in the hash map to get its list of [timestamp, value] pairs. Run binary search on the timestamps to find the largest timestamp <= t. Return the corresponding value.
Edge cases: get with no entries for that key returns empty string. get with timestamp smaller than all stored timestamps returns empty string. All timestamps for a key are unique per the problem constraints.
Optimal Approach
Step 1: Create a hash map where each key maps to a list of [timestamp, value] pairs.
Step 2: For set(key, value, timestamp), append [timestamp, value] to the list for that key. Timestamps arrive in increasing order, so the list stays sorted.
Step 3: For get(key, timestamp), look up the key in the hash map. If not found, return empty string. If found, run binary search on the timestamps to find the rightmost entry with timestamp <= given timestamp.
Step 4: The binary search can use Python's bisect_right to find the insertion point, then check the element just before it.
Walkthrough: set("foo", "bar", 1), set("foo", "bar2", 4), get("foo", 3)
hash_map["foo"]= [[1,"bar"], [4,"bar2"]]bisect_righton timestamps [1, 4] for value 3 returns index 1 (insertion point)- Check index 0: timestamp 1 <= 3. Return "bar".
Time: set is O(1) amortized. get is O(log n) where n is the number of entries for that key. Space: O(n) total for all entries.
Binary search the sorted timestamps
What Trips People Up in Real Interviews
Using a BST or sorted list instead of a simple list with binary search. A BST adds overhead with no benefit here since insertions are always at the end (append-only). The list stays sorted naturally.
Forgetting that set() always receives timestamps in increasing order. This is guaranteed by the problem. You do NOT need to insert into the correct position -- just append. The list is sorted by construction.
Implementing binary search incorrectly for "largest timestamp <= target". The standard binary search finds an exact match. You need a modified version that tracks the last valid result seen when mid value is <= target.
Not handling the case where get() is called with a timestamp smaller than all stored timestamps for that key. The binary search should return empty string in this case, not crash or return the wrong value.
Using bisect_right in Python without understanding the offset. bisect_right returns the insertion point to the right of equal elements. For timestamps, you want bisect_right(timestamps, target) - 1 to get the largest timestamp <= target. Off-by-one errors are common here.
Solution Code
set: O(1) amortized; get: O(log timeclass TimeMap:
def __init__(self):
self.store = {}
def set(self, key, value, timestamp):
if key not in self.store:
self.store[key] = []
self.store[key].append((timestamp, value))
def get(self, key, timestamp):
if key not in self.store:
return ""
entries = self.store[key]
lo, hi = 0, len(entries) - 1
result = ""
while lo <= hi:
mid = (lo + hi) // 2
if entries[mid][0] <= timestamp:
result = entries[mid][1]
lo = mid + 1
else:
hi = mid - 1
return resultFrequently Asked Questions
What is the Time Based Key-Value Store problem?
Design a time-based key-value store that supports set(key, value, timestamp) and get(key, timestamp). The set method stores the key-value pair at the given timestamp, and get returns the value at the largest timestamp less than or equal to the given timestamp. This problem tests your ability to combine `hash map` lookups with `binary search` on sorted timestamps.
How do you solve Time Based Key-Value Store?
The optimal approach runs in set: O(1) amortized; get: O(log time and O(n) for all stored entries space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Time Based Key-Value Store?
Time Based Key-Value Store is asked at Apple, Databricks, Netflix, OpenAI, Oracle. It is a medium difficulty problem.
What are common mistakes on Time Based Key-Value Store?
- Using a `BST` or `sorted list` instead of a simple list with `binary search`. A `BST` adds overhead with no benefit here since insertions are always at the end (append-only). The list stays sorted naturally.
- Forgetting that set() always receives timestamps in increasing order. This is guaranteed by the problem. You do NOT need to insert into the correct position -- just append. The list is sorted by construction.
- Implementing `binary search` incorrectly for "largest timestamp <= target". The standard `binary search` finds an exact match. You need a modified version that tracks the last valid result seen when `mid` value is <= target.
- Not handling the case where `get()` is called with a timestamp smaller than all stored timestamps for that key. The `binary search` should return empty string in this case, not crash or return the wrong value.
- Using `bisect_right` in Python without understanding the offset. `bisect_right` returns the insertion point to the right of equal elements. For timestamps, you want `bisect_right(timestamps, target) - 1` to get the largest timestamp <= target. Off-by-one errors are common here.