Time Based Key-Value Store: Binary Search on Timestamps in an Interview

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.

Data layout

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 '' ```

Why bisect_right

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.

Complexity and follow-ups

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.