Time Based Key-Value Store — HashMap Plus Binary Search for Temporal Queries

Problem Statement#

Design a time-based key-value data structure that can store multiple values for the same key at different timestamps and retrieve the value at a given timestamp.

Implement the TimeMap class:

• TimeMap() — initialises the data structure.
• void set(String key, String value, int timestamp) — stores key with value at timestamp.
• String get(String key, int timestamp) — returns the value where set was called previously with timestamp_prev <= timestamp. If multiple values qualify, returns the one with the largest timestamp_prev. If none qualifies, returns "".

Constraints:

• 1 <= key.length, value.length <= 100
• key and value consist of lowercase English letters and digits
• 1 <= timestamp <= 10^7
• All calls to set use strictly increasing timestamps
• At most 2 × 10^5 calls to set and get

TimeMap timeMap = new TimeMap();
timeMap.set("foo", "bar", 1);
timeMap.get("foo", 1);   // returns "bar"
timeMap.get("foo", 3);   // returns "bar" (t=1 is latest timestamp <= 3)
timeMap.set("foo", "bar2", 4);
timeMap.get("foo", 4);   // returns "bar2"
timeMap.get("foo", 5);   // returns "bar2" (t=4 is latest <= 5)

Why This Problem Matters#

Time Based Key-Value Store (LC 981) is a condensed version of a fundamental real-world system: temporal databases, version control, and event-sourcing. It appears in interviews at Google, Amazon, and Facebook because it combines three important skills: hash map design, binary search, and understanding of temporal queries.

The "largest timestamp <= query timestamp" requirement maps directly to bisect_right in Python, upper_bound in C++, and a right-boundary binary search in other languages. Candidates who reach for linear search O(n) when binary search O(log n) is available immediately signal a gap in their repertoire.

At Google, this problem probes candidates' understanding of time-series data structures. The pattern it teaches — hash map of sorted lists queried with binary search — is the backbone of many time-series databases like InfluxDB and Prometheus, and Apache Cassandra's version columns.

The strictly increasing timestamp guarantee is a critical constraint that justifies appending to the list (no sorting needed) and enables binary search. Interviewers sometimes remove this guarantee to see if candidates notice the change in complexity implications.

The Core Insight#

Data structure: A hash map where each key maps to a sorted list of (timestamp, value) pairs. Since set is called with strictly increasing timestamps, appending maintains sorted order automatically — no sorting step needed.

For get(key, timestamp): Find the rightmost entry where timestamp_entry <= timestamp. This is a classic right-boundary binary search: find the last element not greater than the query timestamp.

In Python, bisect.bisect_right(list, (timestamp, chr(127))) - 1 gives the index of the largest timestamp not exceeding the query. If this index is -1 (all timestamps are larger), return "".

• set: O(1) amortised — just append.
• get: O(log n) — binary search over the stored list for this key.

Visual Dry Run#

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

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

Solution (Optimal)#

from collections import defaultdict
import bisect
 
class TimeMap:
    def __init__(self):
        # key -> list of (timestamp, value), maintained in sorted order
        self.store = defaultdict(list)
 
    def set(self, key: str, value: str, timestamp: int) -> None:
        # Strictly increasing timestamps: appending keeps the list sorted
        self.store[key].append((timestamp, value))
 
    def get(self, key: str, timestamp: int) -> str:
        if key not in self.store:
            return ""
 
        entries = self.store[key]
        # bisect_right with chr(127) finds rightmost timestamp <= query
        idx = bisect.bisect_right(entries, (timestamp, chr(127))) - 1
 
        if idx >= 0:
            return entries[idx][1]
        return ""

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 entries = this.store.get(key);
        // Binary search for the largest timestamp <= query
        let lo = 0, hi = entries.length - 1, result = -1;
 
        while (lo <= hi) {
            const mid = (lo + hi) >> 1;
            if (entries[mid].timestamp <= timestamp) {
                result = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
 
        return result === -1 ? "" : entries[result].value;
    }
}

Time: set O(1). get O(log n) where n = number of set calls for this key. Space: O(n) total across all keys and timestamps.

Common Mistakes#

• Using bisect_left instead of bisect_right: bisect_left finds the leftmost insert position; after subtracting 1, it may miss an exact timestamp match. Use bisect_right for "largest timestamp not exceeding query."
• Not handling idx = -1: If the query timestamp is smaller than all stored timestamps, bisect_right returns 0, and 0 - 1 = -1. Always check idx >= 0.
• Not handling a missing key: Check for key existence before accessing the store. Return "" for missing keys.
• Storing timestamps and values in separate parallel lists: Works but is error-prone. Paired tuples or objects are cleaner and less prone to index-mismatch bugs.
• Assuming timestamps might not be increasing: The problem guarantees strictly increasing timestamps for set, which justifies appending. If this guarantee were lifted, you would need insort — O(n) per insert.

Interview Tips#

• Point out that the strictly increasing timestamp constraint is what makes set O(1) — it eliminates the need to sort.
• Explain bisect_right with a concrete example before using it.
• Note the chr(127) trick for tuple comparison: it ensures the search finds the rightmost entry at exactly the query timestamp.
• Draw the timeline diagram to show what "largest timestamp not exceeding query" means visually.

Follow-up Questions#

• What if timestamps are not strictly increasing? Use bisect.insort to maintain sorted order on insert — O(n) per insert, or use a balanced BST.
• How would you add a delete(key, timestamp) operation? Use tombstone entries — mark deletions and filter during get.
• How would you implement TTL (time-to-live) for entries? Store an expiry timestamp alongside each entry; during get, skip expired entries.
• How would you design this for billions of keys across distributed machines? Consistent hashing for key distribution, replicated sorted lists per node, distributed binary search within each node.
• What if you want exact timestamp matches only? Change the binary search condition to == and return "" if no exact match exists.

Key Takeaways#

• Time Based Key-Value Store (LC 981) combines a hash map of sorted lists with binary search for O(1) set and O(log n) get.
• The strictly increasing timestamp guarantee makes set an O(1) append — no sorting needed.
• The query asks for the "largest timestamp not exceeding the query" — this is the right-boundary binary search (bisect_right minus 1).
• Always check for missing keys and for idx = -1 (query timestamp smaller than all stored timestamps).
• The bisect_right(entries, (timestamp, chr(127))) pattern handles exact timestamp matches correctly.
• This design pattern (hash map of sorted lists + binary search) underlies time-series databases like InfluxDB, Prometheus, and Cassandra's version columns.
• For distributed systems, the same design extends to consistent hashing for key placement and per-node binary search for time queries.