Time Based Key-Value Store — Binary Search on Timestamps

Problem Statement#

Design a time-based key-value store with two operations:

• set(key, value, timestamp) — store key at value with timestamp (timestamps always increasing per key)
• get(key, timestamp) — return the value with the largest timestamp at or before the given timestamp; return "" if none exists

Constraints:

• 1 <= key.length, value.length <= 100
• 1 <= timestamp <= 10^7
• All set calls have strictly increasing timestamps per key

Input:  set("foo","bar",1), get("foo",1), get("foo",3), set("foo","bar2",4), get("foo",4), get("foo",5)
Output: "bar", "bar", "bar2", "bar2"

Why This Problem Matters#

Time Based Key-Value Store (LeetCode 981) is a Google and Amazon interview problem that directly models versioned data systems — the architecture behind Git, database MVCC (multi-version concurrency control), and time-series databases like InfluxDB and TimescaleDB. Every system that needs to "show the state of X at time T" uses this exact pattern.

The naive approach stores all (timestamp, value) pairs and does linear scan — O(N) per get. Since timestamps are strictly increasing per key, the list is always sorted, enabling O(log N) binary search. The get operation asks "find the largest timestamp that is at most the given timestamp" — a classic upper-bound binary search.

This problem is also a gateway to understanding how databases implement historical queries and how stream processors maintain windowed state. Google uses it to test whether candidates recognize sorted-list + binary search as the right tool for time-range queries.

The Core Insight#

Store a hashmap from key to a sorted list of (timestamp, value) pairs. Since timestamps are always inserted in increasing order, the list is inherently sorted — no additional sorting needed.

For get(key, timestamp): binary search in the list for the rightmost timestamp that is at most the given timestamp. Use bisect_right((timestamp, chr(127))) in Python, or a manual binary search with upper bound semantics in JavaScript.

If no timestamp is at most the query timestamp, return "".

Visual Dry Run#

set("foo","bar",1), set("foo","bar2",4):

Store: {"foo": [(1,"bar"), (4,"bar2")]}

get("foo", 3):

• Binary search for rightmost timestamp <= 3 in [(1,"bar"),(4,"bar2")]
• 3 falls between 1 and 4 → take index 0 → return "bar"

get("foo", 4):

• Binary search for rightmost timestamp <= 4
• 4 matches exactly → return "bar2"

Solution (Optimal)#

from collections import defaultdict
import bisect
 
class TimeMap:
    def __init__(self):
        self.store = defaultdict(list)
 
    def set(self, key: str, value: str, timestamp: int) -> None:
        self.store[key].append((timestamp, value))
 
    def get(self, key: str, timestamp: int) -> str:
        arr = self.store.get(key, [])
        # bisect_right with a tuple that sorts after all values at this timestamp
        idx = bisect.bisect_right(arr, (timestamp, chr(127)))
        if idx == 0:
            return ""
        return arr[idx - 1][1]

class TimeMap {
    constructor() {
        this.store = new Map();
    }
 
    set(key, value, timestamp) {
        if (!this.store.has(key)) this.store.set(key, []);
        this.store.get(key).push([timestamp, value]);
    }
 
    get(key, timestamp) {
        const arr = this.store.get(key) || [];
        let lo = 0, hi = arr.length - 1, result = "";
 
        while (lo <= hi) {
            const mid = (lo + hi) >> 1;
            if (arr[mid][0] <= timestamp) {
                result = arr[mid][1];
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
 
        return result;
    }
}

Time: set O(1); get O(log N) where N is number of timestamps for the key Space: O(N) total — N is total number of set calls

Common Mistakes#

• Using bisect_left instead of bisect_right — may miss exact timestamp matches or return wrong index
• Returning arr[idx][1] instead of arr[idx-1][1] — off-by-one after bisect_right
• Not handling the case where idx == 0 (all timestamps are after the query) — return "" not arr[0]
• Storing a flat list of timestamps and values separately — harder to binary search correctly
• Using timestamp + 1 as the search key instead of (timestamp, chr(127)) — works for integers but not strings

Interview Tips#

• Explain the binary search semantics: "find largest timestamp not exceeding query" = upper bound - 1
• Python's bisect_right with (timestamp, chr(127)) is the cleanest trick — chr(127) sorts after all printable chars
• In JavaScript, implement the binary search manually — while (lo <= hi) with lo = mid+1 when arr[mid][0] <= timestamp
• Mention that set is always O(1) because timestamps arrive in increasing order per key
• This is MVCC at its simplest — databases like PostgreSQL use the same pattern for historical queries

Follow-up Questions#

• How do you handle concurrent set calls? — Use a read-write lock per key
• What if timestamps are not monotonically increasing? — Must sort on insert; binary search still works
• How do you expire old data? — Lazy deletion: ignore entries older than a cutoff in get
• How do you get all values in a time range? — Binary search for both boundaries; return slice
• How does this relate to Git history? — Git's git log --before=DATE uses the same upper-bound query on commits

Key Takeaways#

• Store (timestamp, value) pairs per key in insertion order — they are already sorted because timestamps increase
• get uses binary search (upper bound) to find the largest timestamp at or before the query — O(log N)
• Python bisect_right(arr, (timestamp, chr(127))) correctly handles exact timestamp matches
• Return arr[idx-1][1] after bisect_right; if idx==0, no valid timestamp exists — return ""
• This pattern is the core of MVCC databases, Git history, and time-series stores like InfluxDB
• Google tests this to verify binary search fluency applied to a real versioned data structure
• Space is O(N) total across all keys; per-key lists are always sorted without explicit sorting overhead