Time Based Key-Value Store

Time Based Key-Value Store is a classic interview problem that hides a binary search inside an innocent-looking data structure. It teaches you to spot when a list is secretly sorted and to reach for the largest-value-not-exceeding search.

The slow way first

The obvious idea: for each key keep a list of (timestamp, value) pairs, and on get scan the whole list to find the largest timestamp that is still ≤ the query. That works, but every get is O(n) in the number of pairs for that key. With many gets on a long history, that is far too slow.

The question to ask: is there any structure I can exploit? Yes — the problem promises timestamps are set in increasing order, so the list is already sorted by timestamp. A sorted list is an invitation to binary search.

The idea: binary search for the best timestamp

For each key store an append-only list of (timestamp, value) pairs. Because timestamps only ever increase, that list stays sorted. On get(key, t), binary-search the timestamps for the largest one ≤ t.

The trick is the comparison. When timestamps[mid] ≤ t, mid is a valid candidate, so we record it and push lo to the right hoping for an even closer match. When timestamps[mid] > t, mid is too big, so we move hi left. Whatever we last recorded is the answer.

The key insight: we never give up the moment we find a fit. We save it and keep searching right, because a later timestamp might be even closer to t while still not exceeding it.

Walk through it

Step through the animation for get(key, 13). The pointers lo, hi, and mid bracket the sorted timestamp row. At mid = 10 we have a hit (10 ≤ 13), so we record value 'c' and go right. At mid = 14 we overshoot (14 > 13), so we go left, the window crosses, and the loop ends — leaving the recorded 'c' as the answer.

Pseudocode

on get(key, t):
    look up the sorted (timestamp, value) list for key
    lo, hi = 0, len(list) - 1
    ans = ""                         # default if nothing fits
    while lo <= hi:
        mid = (lo + hi) // 2
        if timestamp[mid] <= t:
            ans = value[mid]         # candidate; try for something closer
            lo = mid + 1             # search the right half
        else:
            hi = mid - 1             # too big, search the left half
    return ans

The Python solution

def get(stamps, values, t):
    lo, hi = 0, len(stamps) - 1
    ans = ""
    while lo <= hi:
        mid = (lo + hi) // 2
        if stamps[mid] <= t:
            ans = values[mid]
            lo = mid + 1
        else:
            hi = mid - 1
    return ans

• stamps and values are the sorted, parallel lists stored for one key (in a real store, a dict maps each key to them).
• ans starts as "" — the answer when no timestamp is small enough.
• mid = (lo + hi) // 2 is the usual binary-search midpoint.
• Lines 6-8 are the heart: when stamps[mid] <= t, mid fits, so we record its value and move lo right to chase a closer timestamp.
• When stamps[mid] > t, mid overshoots, so we drop the right half by moving hi left.
• When the loop ends, ans holds the value for the largest qualifying timestamp.

Complexity

set is O(1) amortized — just append, since timestamps already arrive sorted. get drops from O(n) to O(log n) by binary-searching that sorted list. Storage is O(n) across all pairs.

When this pattern shows up

Practice