Time Based Key-Value Store

Examples

Input: set("foo", "bar", 1), then get("foo", 1)
Output: "bar"

"bar" was stored for "foo" at exactly timestamp 1.

Input: get("foo", 3) (right after the set above, with nothing new set in between)
Output: "bar"

Nothing was set between timestamps 1 and 3, so the most recent value at or before timestamp 3 is still "bar".

Input: set("foo", "bar2", 4), then get("foo", 4) and get("foo", 5)
Output: "bar2" for both

Timestamp 4 introduces a newer value, and it remains the answer for any query timestamp of 4 or later, until something even newer is set.

Constraints

• 1 <= key.length, value.length <= 100

• key and value consist of lowercase English letters and digits.

• 1 <= timestamp <= 10^7

• All the timestamps passed to set for the same key are strictly increasing.

• At most 2 * 10^5 calls total will be made to set and get.

Approach

The simplest approach is to store every (timestamp, value) pair for a key in a list, and on get, scan that list to find the latest timestamp that doesn't exceed the query. Because set calls for a given key always arrive with strictly increasing timestamps, this list comes out naturally sorted — there's never a need to sort it yourself.

Since the list is already sorted by timestamp, a get doesn't need to look at every entry. It's really asking "what's the rightmost timestamp that is <= this value?", which is a binary search for a boundary rather than a search for an exact match. Narrow a left/right range as usual, and whenever an entry's timestamp qualifies (is <= the target), remember its value as the best answer so far and keep searching further right to see if there's an even better one.

Solutions

Brute Force — Scan Backwards

Keep each key's (timestamp, value) pairs in the order they were set, then on get, scan from the most recent entry backwards until one has a timestamp at or before the query.

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 entries = this.store.get(key);
    if (!entries) return "";

    for (let i = entries.length - 1; i >= 0; i--) {
      if (entries[i][0] <= timestamp) {
        return entries[i][1];
      }
    }
    return "";
  }
}

Time: set: O(1). get: O(n) in the worst case, where n is the number of values stored for that key. · Space: O(n) total across all set calls.

Optimal — Binary Search

Binary search the sorted list of (timestamp, value) pairs for a key, looking for the rightmost timestamp that's less than or equal to the query, tracking the best match found so far as the range narrows.

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 entries = this.store.get(key);
    if (!entries) return "";

    let left = 0;
    let right = entries.length - 1;
    let result = "";

    while (left <= right) {
      const mid = Math.floor((left + right) / 2);

      if (entries[mid][0] <= timestamp) {
        result = entries[mid][1];
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }

    return result;
  }
}

Time: set: O(1). get: O(log n), where n is the number of values stored for that key. · Space: O(n) total across all set calls.