# 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. ```python 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](https://www.linkjob.ai/), an AI tool for job interviews.*