Marauder Bot

Problem

Design a structure that stores a string value under a key together with a timestamp, where timestamps are always inserted in increasing order for a given key. It must support looking up, for a key and a query timestamp, the value most recently set at or before that timestamp; if none exists, return an empty result.

Example. After setting key "foo" to "bar" at timestamp 1 and to "bar2" at timestamp 4, querying at timestamp 5 returns "bar2", while querying at timestamp 2 returns "bar".

Key idea

Scanning every stored entry for a key to find the closest timestamp not exceeding the query would cost time proportional to how many values had ever been set for that key. The way out is exploiting that insertions arrive in increasing timestamp order: the timestamp-value pairs for each key are naturally already sorted as they accumulate, with no extra work needed to keep them that way.

Store each key's history as a growing sequence of timestamp-value pairs in a hash map keyed by the string key, appending new entries onto the end since they always arrive in order. To answer a query, binary search that key's sequence for the largest timestamp that does not exceed the query timestamp, and return its paired value; if every stored timestamp is larger than the query, nothing qualifies.

Solution

class TimeMap {
  private history: Map<string, Array<[number, string]>>;

  constructor() {
    this.history = new Map();
  }

  set(key: string, value: string, timestamp: number): void {
    const entries = this.history.get(key);
    if (entries) {
      entries.push([timestamp, value]);
    } else {
      this.history.set(key, [[timestamp, value]]);
    }
  }

  get(key: string, timestamp: number): string {
    const entries = this.history.get(key);
    if (!entries) {
      return '';
    }

    let low = 0;
    let high = entries.length - 1;
    // largest timestamp not exceeding the query, or empty if none qualifies
    let result = '';

    while (low <= high) {
      const mid = low + Math.floor((high - low) / 2);
      if (entries[mid][0] <= timestamp) {
        // candidate found, keep looking right for a later timestamp that still qualifies
        result = entries[mid][1];
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }

    return result;
  }
}

Complexity

Time: O(1) for a set call; O(log k) for a get call, where k is the number of entries stored under that key.
Space: O(total entries stored). Every set call adds one entry.

Watch out for

The binary search looks for the largest timestamp less than or equal to the query, not an exact match.
Handle the case where the key has never been set, or every stored timestamp exceeds the query, by returning an empty result rather than erroring.

Pattern

This combines a hash map for key-based lookup with binary search over an append-only sorted sequence, a common shape for versioned or time-series data: group entries by identity, then binary search within each group's chronological history to answer "as of" queries.

Time Based Key-Value Store