Time Based Key-Value Store

Design a class TimeMap that stores several versions of each key, one per timestamp, and can answer “what was this key’s value at time t?”.

• TimeMap() creates an empty store.
• set(key, value, timestamp) records that key had value starting at timestamp.
• get(key, timestamp) returns the value from the set call for key with the largest timestamp that is at most timestamp. If key has never been set, or all of its timestamps are later than timestamp, return the empty string "".

Across all set calls, timestamps are strictly increasing. Each test is a list of method names and a matching list of argument lists; the judge compares the list of return values (null for the constructor and set).

Example 1

Example 2

Example 3

Constraints

• 1 <= key.length, value.length <= 100; keys and values are lowercase letters and digits
• 1 <= timestamp <= 107
• Timestamps of set calls are strictly increasing.
• At most 2 × 105 calls in total.

Pattern Path · Binary Search · problem 60 of 169

Start simple

Store every (timestamp, value) per key and scan the whole list on each get: O(1) per set but O(k) per get, where k is that key's number of versions.

The key idea

Use a hash map from each key to a list of its versions. Every set appends (timestamp, value); since timestamps arrive in increasing order, each list stays sorted without any extra work.

A get(key, t) needs the last version with timestamp ≤ t. In a sorted list the versions with timestamp ≤ t form a prefix, so binary search finds where that prefix ends: the first index whose timestamp is greater than t. The answer is the entry just before it. If that index is 0, no version is old enough and the result is "".

Searching for “first timestamp > t” (an upper bound) rather than “equal to t” is the key detail: it handles exact matches and gaps between versions with the same code. Each set costs O(1) and each get O(log k), where k is the number of versions of that key.

Complexity

• Time: set O(1), get O(log k)
• Space: O(total number of set calls)

Python

from bisect import bisect_right


class TimeMap:
    def __init__(self):
        self.times = {}    # key -> sorted list of timestamps
        self.values = {}   # key -> values, parallel to times[key]

    def set(self, key, value, timestamp):
        # Timestamps only increase, so appending keeps each list sorted.
        self.times.setdefault(key, []).append(timestamp)
        self.values.setdefault(key, []).append(value)

    def get(self, key, timestamp):
        times = self.times.get(key, [])
        # Index of the first version newer than `timestamp`.
        i = bisect_right(times, timestamp)
        return self.values[key][i - 1] if i > 0 else ""

JavaScript

class TimeMap {
  constructor() {
    this.store = new Map(); // key -> array of [timestamp, value], sorted by timestamp
  }

  set(key, value, timestamp) {
    // Timestamps only increase, so pushing keeps each array sorted.
    if (!this.store.has(key)) this.store.set(key, []);
    this.store.get(key).push([timestamp, value]);
  }

  get(key, timestamp) {
    const versions = this.store.get(key) || [];
    // Find the first version newer than `timestamp`.
    let lo = 0, hi = versions.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (versions[mid][0] <= timestamp) lo = mid + 1;
      else hi = mid;
    }
    return lo > 0 ? versions[lo - 1][1] : "";
  }
}

What the interviewer is checking

The interviewer checks that you exploit the sorted-by-construction timestamps and implement an upper-bound binary search without off-by-one errors.

Mistakes to avoid

• Looking only for an exact timestamp match instead of the latest one at or before it.
• Returning null or None instead of the empty string when nothing qualifies.
• Off-by-one in the binary search, returning the version just after t instead of just before.

Follow-ups to expect

• What if set timestamps can arrive out of order? (Sorted container or tree map per key.)
• Support deleting or expiring old versions. (Trim list prefix, or TTL index.)
• How would this scale across many machines? (Shard by key, MVCC-style storage.)

In real software

Multi-version databases, configuration history, feature-flag audit logs and time-travel queries on time-series stores all answer “value as of time t” with this layout.

Practice next