Time Based Key-Value Store

class TimeMap:
    def __init__(self):
        self.store = {}          # key -> [(time, value)]
    def set(self, key, value, time):
        self.store.setdefault(key, []).append((time, value))
    def get(self, key, time):
        items = self.store.get(key, [])
        lo, hi, ans = 0, len(items) - 1, ""
        while lo <= hi:
            mid = (lo + hi) // 2
            if items[mid][0] <= time:
                ans, lo = items[mid][1], mid + 1   # fits: go right
            else:
                hi = mid - 1                       # too new: go left
        return ans

Time Based Key-Value Store. One key can hold many values, each set at a timestamp. Get, with a key and a time, returns the value set most recently at or before that time.

Set foo to bar at time one. Get foo at one: bar. At three, still bar. Set foo to bar two at time four. Get at four or five: bar two. At time zero, get returns an empty string: nothing was set yet.

The simple way keeps every pair for a key, and scans them all on each get, looking for the newest time that isn't too late. With n entries, each get is order n.

But set's timestamps always increase. So each key's list is already sorted, just by appending. Now get can binary search for the last entry whose time is at most the target.

Set appends to the key's list. Get keeps two bounds and checks the middle. If its time fits, remember its value and look right for a newer one. If it's too new, look left. When the bounds cross, return the last value that fit.

Sky holds seven snapshots: times one, three, five, eight, eleven, fourteen and eighteen. Get sky at twelve. The middle is eight: it fits, remember snow, go right. Next middle, fourteen: too new, go left. Eleven fits: remember fog. The bounds cross, so the answer is fog.

Set takes constant time. Get takes log n, so a million snapshots need about twenty checks. Space is one entry per set.

Append in order, search by time. That's Time Based Key-Value Store.