Time Based Key-Value Store
Asked at Apple, Databricks, Netflix, OpenAI, Oracle
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.
Asked At
| 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.
Visual walkthrough: set("foo", "bar", 1), set("foo", "bar2", 4), set("foo", "bar3", 5)
hash_map = {"foo": [[1,"bar"], [4,"bar2"], [5,"bar3"]]}
get("foo", 3): binary search on [1, 4, 5] for largest <= 3. Answer: index 0, return "bar".
get("foo", 5): binary search on [1, 4, 5] for largest <= 5. Answer: index 2, return "bar3".
get("foo", 6): all timestamps <= 6. Return "bar3".
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.
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
class 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.