Time Based Key-Value Store

The machine implements a store where set(key, value, timestamp) writes and get(key, timestamp) returns the value whose timestamp is the largest one ≤ the query, or "" if none. Timestamps strictly increase per key, so each key's timeline is sorted — which makes the lookup a binary search over that timeline. Per key: one list of timestamps, one parallel list of values.

from bisect import bisect_right
 
class TimeMap:
    def __init__(self):
        self.store = {}  # key -> [timestamps, values]
 
    def set(self, key, value, timestamp):
        if key not in self.store:
            self.store[key] = [[], []]
        self.store[key][0].append(timestamp)
        self.store[key][1].append(value)
 
    def get(self, key, timestamp):
        if key not in self.store:
            return ""
        ts, vals = self.store[key]
        i = bisect_right(ts, timestamp) - 1
        return vals[i] if i >= 0 else ""

Steps: (1) append on every set — monotonic timestamps keep the lists sorted, (2) on get, locate the insertion point of the query timestamp with bisect_right, (3) step back one position; a negative index means nothing qualified.

Time: set is O(1) amortized; get is O(log k) for k versions of the key. Space is O(n) total.

Trickiest edge case: a query earlier than the first stored timestamp — bisect_right returns 0, minus 1 is -1, and the answer is "", not the first value. bisect_right (not bisect_left) matters: with duplicate timestamps, right-bias keeps the latest value.