Time Based Key-Value Store — HashMap + Binary Search [LC 981, Google, Facebook]

Problem Statement#

Implement a time-based key-value store class TimeMap with:

• set(key, value, timestamp): stores the key-value pair at the given timestamp
• get(key, timestamp): returns the most recent value set at or before the given timestamp, or "" if none

All timestamps in set calls are strictly increasing.

Constraints:

• 1 <= key.length, value.length <= 100
• 1 <= timestamp <= 10^7
• At most 2 * 10^5 calls to set and get
• All timestamps in set are strictly increasing

Input:  ["TimeMap","set","get","get","set","get","get"]
        [[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]
Output: [null,null,"bar","bar",null,"bar2","bar2"]

Why This Problem Matters#

LC 981 is asked by Google and Facebook as a system design + algorithms hybrid. It tests whether candidates can design a data structure that stores versioned data and queries it efficiently. The problem is a simplified version of multi-version concurrency control (MVCC) used in real databases like PostgreSQL.

The key insight is that since all set timestamps are strictly increasing, the timestamp list for each key is automatically sorted — enabling binary search for the get operation without any additional sorting cost.

The Core Insight#

Store a dictionary mapping each key to a list of (timestamp, value) pairs. Since timestamps are always strictly increasing in set calls, the list is naturally sorted by timestamp.

For get(key, timestamp): use right-boundary binary search to find the last timestamp in the list that is <= timestamp. Return its corresponding value, or "" if no such timestamp exists.

Right-boundary search: find the largest index i where store[key][i][0] <= timestamp. This is bisect_right(timestamps, timestamp) - 1.

Visual Dry Run#

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

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

get("foo", 3): right-boundary on timestamps [1,4] for t=3:

• bisect_right([1,4], 3) = 1, idx = 0, return "bar" (most recent at or before t=3)

get("foo", 5): bisect_right([1,4], 5) = 2, idx = 1, return "bar2"

get("foo", 0): bisect_right([1,4], 0) = 0, idx = -1, return ""

Solution (Optimal)#

from collections import defaultdict
import bisect
 
class TimeMap:
    def __init__(self):
        # Each key maps to a list of (timestamp, value) pairs
        self.store = defaultdict(list)
 
    def set(self, key: str, value: str, timestamp: int) -> None:
        # Timestamps are strictly increasing, so list stays sorted
        self.store[key].append((timestamp, value))
 
    def get(self, key: str, timestamp: int) -> str:
        if key not in self.store:
            return ""
        pairs = self.store[key]
        # bisect_right finds the first position after all timestamps <= timestamp
        # Subtract 1 to get the last valid entry
        idx = bisect.bisect_right(pairs, (timestamp, chr(127))) - 1
        # Alternatively: binary search manually on timestamps only
        return pairs[idx][1] if idx >= 0 else ""

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) {
        if (!this.store.has(key)) return "";
        const pairs = this.store.get(key);
 
        // Right-boundary binary search: find last timestamp <= given timestamp
        let lo = 0, hi = pairs.length - 1;
        let ans = "";
 
        while (lo <= hi) {
            const mid = lo + Math.floor((hi - lo) / 2);
            if (pairs[mid][0] <= timestamp) {
                ans = pairs[mid][1];  // valid candidate; try to find a later one
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
 
        return ans;
    }
}

Time: set O(1), get O(log n) where n = number of set calls for that key Space: O(n) total across all keys

Common Mistakes#

• Using bisect_left instead of bisect_right — bisect_left finds the first position >= timestamp, while you need the last position <= timestamp.
• Not initialising ans = "" before the binary search — if the loop exits without finding any valid timestamp, you need to return empty string.
• Using bisect_right on just the timestamps list but storing (timestamp, value) pairs — use a separate timestamps list or pass a sentinel to bisect_right.
• Forgetting the case where the key doesn't exist — always check for key existence first.

Interview Tips#

• Mention that strictly increasing timestamps make the list automatically sorted — this justifies binary search without explicit sorting.
• For Python, bisect_right(pairs, (timestamp, chr(127))) is a trick: chr(127) is a character greater than all lowercase letters, so (timestamp, chr(127)) sorts after all (timestamp, value) pairs with the same timestamp.
• The JavaScript version's lo <= hi approach with ans tracking is clean and avoids the sentinel trick.
• This is the same right-boundary pattern as LC 911 (Online Election) — if you solved that, this is identical.

Follow-up Questions#

• LC 911 (Online Election): Identical binary search; precomputed leader array is the "value" array.
• What if timestamps in set can repeat? The problem guarantees they don't. If they could, you'd need to handle ties (return the latest value for the same timestamp).
• Can you do O(1) for get? Not without O(n) space per query or preprocessing. O(log n) is optimal for this query type.
• Real MVCC databases: PostgreSQL uses a similar structure (heap tuples with timestamps) for multi-version concurrency control.

Key Takeaways#

• LC 981 uses a defaultdict of sorted (timestamp, value) lists — set appends in O(1), get binary searches in O(log n).
• Strictly increasing timestamps guarantee the list is always sorted, enabling binary search without explicit sorting.
• The get operation uses right-boundary binary search: find the last timestamp <= t, then return its value (or "" if none exists).
• In Python, bisect_right(pairs, (timestamp, chr(127))) - 1 elegantly handles the right-boundary search on a list of tuples.
• In JavaScript, the lo <= hi template with ans tracking (update ans on every valid match, then continue right) is the clean manual right-boundary implementation.
• Google and Facebook ask this as a design interview warm-up — the data structure design (one sorted list per key) is the main challenge, and binary search makes query efficient.
• This is the same precompute-then-binary-search pattern as LC 911 (Online Election) — recognising the family across different disguises is a strong interview signal.