← Create New Paste

Time Based Key-Value Store (LeetCode 981): Binary Search Over Timestamps

7 views
Design a data structure that stores multiple values for the same key at different timestamps and can return the value for a key at a given time. You implement two methods: - set(key, value, timestamp): store value for key at timestamp. - get(key, timestamp): return the value set for key at the largest timestamp less than or equal to the given timestamp, or "" if none exists. The problem guarantees that timestamps passed to set are strictly increasing. That one sentence is the key to an efficient solution, and pointing it out early is what interviewers want to hear. Step 1: choose the structure Use a hash map from key to a list of (timestamp, value) pairs. Because set calls arrive with increasing timestamps, appending to the list keeps it sorted automatically. No insertion sort, no tree map needed. Step 2: answer get with binary search For get(key, t), find the rightmost pair whose timestamp is <= t. That is a classic "upper bound minus one" search. import bisect from collections import defaultdict class TimeMap: def __init__(self): self.times = defaultdict(list) self.vals = defaultdict(list) def set(self, key, value, timestamp): self.times[key].append(timestamp) self.vals[key].append(value) def get(self, key, timestamp): ts = self.times.get(key) if not ts: return "" i = bisect.bisect_right(ts, timestamp) - 1 return self.vals[key][i] if i >= 0 else "" Keeping timestamps and values in parallel lists lets bisect compare plain integers. Complexity: set is O(1) amortized, get is O(log n) for n entries under that key, and space is O(total entries). If you write the binary search by hand, state the invariant clearly: lo starts at 0, hi at len, and you look for the first timestamp greater than t; the answer is the index before it. Off-by-one errors here are the most common bug, so trace one example: timestamps [1, 4, 7], query 5 should return the value at 4; query 0 returns ""; query 7 returns the value at 7. Follow-up questions interviewers ask - "What if timestamps are not increasing?" Then you need a sorted structure per key: a balanced BST or a sorted container (TreeMap.floorEntry in Java), giving O(log n) set and get. Alternatively, insert with bisect.insort at O(n) cost per set. - "What if memory is limited?" Discuss expiring old versions with a retention window, or compacting entries. - "How would this work in a distributed system?" This structure is the core idea behind multi-version concurrency control (MVCC) and time-travel queries in databases. Keys are partitioned across nodes, and each node keeps versions sorted by timestamp. Clock skew between servers becomes the hard problem, which is why systems use logical clocks or hybrid logical clocks. - "Can get be O(1)?" Only with heavy precomputation for a bounded time range, which is rarely worth it. How to present it A crisp opening sounds like: "Each key gets a list that stays sorted because set timestamps increase, so get is a binary search for the floor timestamp." Then code, then test the edge cases above. Mentioning MVCC at the end shows you can connect a LeetCode problem to real systems. Explaining invariants clearly under time pressure is a skill of its own. Linkjob AI (https://linkjob.ai) gives real-time help during live job interviews and technical interviews, helping you stay structured while the interviewer probes follow-ups.
Created Nov 18, 2026 02:26 Expires Nov 18, 2027 02:26