Time Based Key-Value Store

Table of Contents +

Time Based Key-Value Store looks like a design question. So people freeze. But underneath it is just a normal hash map plus one binary search. Once you see that, the whole thing becomes easy. The interviewer wants to see if you can pick the right tool for “find the closest time at or before this one.”

🎯 The Problem

You build a store that remembers values over time. Here are the rules.

Each value gets saved with a key and a timestamp. A timestamp is just a number that says when it was saved.
A get(key, time) asks: what was the value for this key at this time?
The asked time may not match any saved time exactly.
Then you return the value from the latest save at that time or before it.
If nothing was saved at or before that time, return an empty string.
Each new save for a key uses a bigger timestamp than the one before. So a key’s times are already in order.

set("foo", "bar", 1)
get("foo", 1)   -> "bar"    (exact time 1 exists)
get("foo", 3)   -> "bar"    (nothing at 3, latest at-or-before is time 1)
set("foo", "baz", 4)
get("foo", 4)   -> "baz"    (exact time 4)
get("foo", 5)   -> "baz"    (latest at-or-before 5 is time 4)

Here is the shape of the data. Each key points to its own time-ordered list of saves.

🐢 Approach 1: Linear Scan of the List (Brute Force)

The idea in one line: keep each key’s saves in a list, then walk the whole list on every get.

The idea:

Each key maps to a list of (time, value) pairs in the order they came.
A get looks at every pair in that list.

How it works:

Walk the full list for the key.
Keep the value whose time is the largest one still at or before the asked time.
Return that value, or the empty string if none fit.

Why it is weak:

Every get scans the whole list for that key.
A key with a million saves costs a million steps per query.
That is O(n) per get, where n is how many values the key has.

Here is the linear-scan code for that idea:

class TimeMap:
    def __init__(self):
        self.store = {}

    def set(self, key, value, timestamp):
        self.store.setdefault(key, []).append((timestamp, value))

    def get(self, key, timestamp):
        answer = ""
        for time, value in self.store.get(key, []):
            if time <= timestamp:
                answer = value
            else:
                break
        return answer

⚡ Approach 2: Binary Search on Timestamps (Best)

The idea in one line: the times are already sorted, so jump with binary search instead of scanning.

The idea:

The timestamps for a key always arrive in increasing order. So the list is already sorted.
A sorted list means you do not scan it. You jump.
Binary search finds a spot in a sorted list by cutting the range in half each step.

How it works:

Store each key’s times and values in the same order.
Look at the middle time.
If the middle time is too big, throw away the right half.
If it is at or before the target, keep it as a candidate, then search the right half for a closer one.
The best candidate’s value is the answer.

Why it is fast:

Each step throws away half the list.
One get becomes O(log n), tiny even for huge lists.

Here is a dry run of get("foo", 5) on timestamps [1, 4]. Watch the range narrow.

Steps to Solve

Keep a hash map. The key maps to two parallel lists: one of timestamps, one of values.
For set(key, value, time), append the time and the value to that key’s lists. They stay sorted because times always grow.
For get(key, time), run a binary search over that key’s timestamp list.
Look for the largest timestamp that is at or before the asked time. Track it as a candidate while narrowing the range.
If a candidate was found, return its value. If no timestamp is at or before the asked time, return an empty string.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

This Python version keeps a dictionary from key to a list of (time, value) pairs and binary searches the times.

class TimeMap:
    def __init__(self):
        self.store = {}  # key -> list of (time, value)

    def set(self, key, value, time):
        if key not in self.store:
            self.store[key] = []
        self.store[key].append((time, value))  # times grow, stays sorted

    def get(self, key, time):
        items = self.store.get(key, [])
        lo, hi, ans = 0, len(items) - 1, ""
        while lo <= hi:
            mid = (lo + hi) // 2            # middle index
            if items[mid][0] <= time:       # candidate, try for closer
                ans = items[mid][1]
                lo = mid + 1                # search the right half
            else:
                hi = mid - 1                # too big, search the left half
        return ans


tm = TimeMap()
tm.set("foo", "bar", 1)
print(tm.get("foo", 1))
print(tm.get("foo", 3))
tm.set("foo", "baz", 4)
print(tm.get("foo", 4))
print(tm.get("foo", 5))

The output of the above code will be:

bar
bar
baz
baz

Let us walk through the Python get line by line, because the binary search is the whole trick.

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 = items[mid][1]
            lo = mid + 1
        else:
            hi = mid - 1
    return ans

items = self.store.get(key, []) grabs the time-ordered list for this key. If the key was never set, we get an empty list, so the loop never runs and we return the empty string.

lo, hi, ans = 0, len(items) - 1, "" sets the search range to the whole list. lo is the left edge, hi is the right edge. ans starts empty, which is our answer if nothing fits.

while lo <= hi keeps going while the range still has at least one item.

mid = (lo + hi) // 2 picks the middle index. We look there first so we can throw away half the list in one step.

if items[mid][0] <= time checks the time at the middle. If that time is at or before the asked time, it is a valid answer. So we save its value in ans. Then lo = mid + 1 moves right, because a later time might be even closer to the asked time while still being valid.

else: hi = mid - 1 runs when the middle time is too big. That value cannot be used. So we drop the middle and everything to its right by moving hi left.

return ans gives back the value of the best candidate we found, or the empty string if there was none.

⏱️ Time and Space Complexity

The brute force scans the whole list for each get, so it is O(n) per query. The binary search cuts the list in half each step, so it is O(log n) per query. Both store every value once, so space is O(n) where n is the total number of saves. The win is on speed. You go from O(n) per query down to O(log n).

Approach	Get Time	Space
Linear scan of the list	O(n)	O(n)
Binary search on timestamps	O(log n)	O(n)

Tip

The whole problem turns on one fact: timestamps arrive in increasing order. Say that out loud in the interview. It is the reason binary search is allowed. Without sorted times you would be stuck scanning.

🧩 Key Takeaways

✅ Store each key’s saves as a list of (time, value) pairs in the order they came.
✅ Timestamps always grow, so each key’s list is already sorted by time.
✅ A get is a binary search for the largest time at or before the asked time.
✅ Keep the middle as a candidate, then search the right half for something closer.
✅ This drops each query from O(n) scanning down to O(log n).

Check Your Knowledge

4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Median of Two Sorted Arrays
Split Array Largest Sum

Previous Koko Eating Bananas Next Median of Two Sorted Arrays

Time Based Key-Value Store

Follow Us

Follow Us