Skip to main content

981 - Time Based Key-Value Store

Difficulty: Medium | Pattern: Binary Search + HashMap | Company tags: Google, Amazon, Uber

Problem Statement​

Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key's value at a certain timestamp.

Implement the TimeMap class:

  • TimeMap() Initializes the object of the data structure.
  • void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp.
  • String get(String key, int timestamp) Returns a value such that set was called previously, with timestamp_prev <= timestamp. If there are multiple such values, return the value associated with the largest timestamp_prev. If there are no values, return "".

Example:

TimeMap map = new TimeMap();
map.set("foo", "bar", 1);
map.get("foo", 1)   → "bar"
map.get("foo", 3)   → "bar"
map.set("foo", "bar2", 4);
map.get("foo", 4)   → "bar2"
map.get("foo", 5)   → "bar2"

Algorithm Flow​

Solution: HashMap + Binary Search — O(log n) per get​

Key insight: Store (timestamp, value) pairs in a list per key. Since set is always called with increasing timestamps, the list is sorted. Use binary search to find the largest timestamp <= query timestamp.

from collections import defaultdict
import bisect

class TimeMap:
    def __init__(self):
        self.store = defaultdict(list)  # key → [(timestamp, value)]
    
    def set(self, key: str, value: str, timestamp: int) -> None:
        self.store[key].append((timestamp, value))
    
    def get(self, key: str, timestamp: int) -> str:
        pairs = self.store[key]
        # Binary search for largest timestamp <= given timestamp
        lo, hi = 0, len(pairs) - 1
        result = ""
        while lo <= hi:
            mid = (lo + hi) // 2
            if pairs[mid][0] <= timestamp:
                result = pairs[mid][1]
                lo = mid + 1
            else:
                hi = mid - 1
        return result

Dry Run​

After set("foo","bar",1) and set("foo","bar2",4): store["foo"] = [(1,"bar"), (4,"bar2")]

get("foo", 3):

  • lo=0, hi=1, mid=0 → pairs[0]=(1,"bar") → 1 lte 3 → result="bar", lo=1
  • lo=1, hi=1, mid=1 → pairs[1]=(4,"bar2") → 4 gt 3 → hi=0
  • Loop ends → return "bar" ✓

get("foo", 5):

  • mid=0 → 1 lte 5 → result="bar", lo=1
  • mid=1 → 4 lte 5 → result="bar2", lo=2
  • Loop ends → return "bar2" ✓

Edge Cases​

  • Key not in store → empty list, binary search returns ""
  • Timestamp before any stored → return ""
  • Multiple equal timestamps → problem guarantees timestamps are strictly increasing per call

Complexity​

  • Time: O(1) set, O(log n) get
  • Space: O(n) total entries

Key Terms​

TermDefinition
Binary searchO(log n) search over a sorted sequence by repeatedly halving the search range.
Monotonic appendProperty that set calls arrive with strictly increasing timestamps, keeping each key's list sorted without extra sorting.
HashMap of listsMaps each key to its own sorted list of (timestamp, value) pairs.
Floor queryFinding the largest stored timestamp that is <= a target timestamp.
Amortized designTrading O(1) writes for O(log n) reads by deferring ordering work to query time via binary search.

FAQ​

  1. Can this be solved without extra space? No — values across timestamps must be retained; O(n) total storage across all keys is unavoidable for correctness.
  2. What if timestamps could be inserted out of order? The per-key list would no longer be sorted, so binary search would require inserting in sorted position (O(n) insert) or re-sorting before queries.
  3. How would this change if we needed range queries instead of floor queries? You'd binary search both bounds and slice the list, or use a different structure like a sorted map with range iteration.
  4. What if get is called far more often than set? The current design already favors this — O(1) set and O(log n) get is optimal for read-heavy workloads.
  5. Could a balanced BST or sorted container replace the list? Yes, e.g. Python's sortedcontainers.SortedList, but a plain list plus binary search is simpler and equally efficient here since inserts are always at the end.

Quick Revision​

  • Store each key's values as a list of (timestamp, value) pairs.
  • set appends in O(1) since timestamps are guaranteed increasing.
  • get binary searches for the largest timestamp <= the query timestamp.
  • Track the best-found value as lo advances past valid candidates.
  • If no valid timestamp exists, return "".
  • Time: O(1) set, O(log n) get; Space: O(n) total entries.
  • Core pattern: HashMap + binary search for "floor" lookups on sorted data.
  • Generalizes to any "latest value at or before time T" query.