Time Based Key-Value Store asks you to design set(key, value, timestamp) and get(key, timestamp), where get returns the value with the largest timestamp not after the one given. It mixes a little design with a binary search.
Map each key to a list of (timestamp, value) pairs. The problem guarantees timestamps for set are strictly increasing, so appending keeps each list sorted for free. Point that guarantee out; it is the whole reason the design is simple.
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): i = bisect.bisect_right(self.times[key], timestamp) return self.vals[key][i - 1] if i else '' ```
bisect_right returns the first index with a timestamp strictly greater than the query, so the answer is just before it. Using bisect_left would miss an exact match. Keeping timestamps and values in parallel lists avoids comparing tuples.
set is O(1) amortized and get is O(log n) for that key. If timestamps can arrive out of order, switch to a sorted container or a balanced tree. If memory matters, discuss expiring old versions, which is how real systems with versioned keys behave.
Practising design-flavoured coding questions out loud? An AI interview copilot can give you real-time hints. Disclosure: I help build Linkjob AI.