Time-Based Key-Value Store (LeetCode 981): Binary Search on Timestamps
The problem: implement set(key, value, timestamp) and get(key, timestamp), where get returns the value set at the largest timestamp less than or equal to the one requested.
Key observation
Timestamps for each key arrive in increasing order. So every key's history is already a sorted list, and get is a binary search.
import bisect
from collections import defaultdict
class TimeMap:
def __init__(self):
self.times = defaultdict(list)
self.values = defaultdict(list)
def set(self, key, value, ts):
self.times[key].append(ts)
self.values[key].append(value)
def get(self, key, ts):
i = bisect.bisect_right(self.times[key], ts)
return self.values[key][i - 1] if i else ""
set is O(1); get is O(log n) for a key with n versions.
Explaining bisect_right
bisect_right returns the first position greater than ts, so the element just before it is the latest timestamp that is at most ts. If the position is 0, nothing qualifies and you return the empty string. Walking through this off-by-one out loud is what the interviewer wants to hear.
Follow-ups
- Timestamps not in order: use a balanced BST or a sorted container (like
SortedList), at O(log n) per insert. - Memory limits: drop old versions beyond a retention window.
- Real systems: this is how multi-version stores work. Bigtable and HBase keep timestamped cells, and databases use MVCC so readers see a consistent snapshot.
Disclosure: I'm on the team behind Linkjob AI, an AI tool for job interviews.