Time Based Key Value Store

The problem

Design a time-based key-value structure:

• set(key, value, timestamp) — store
• get(key, timestamp) — return value for largest timestamp ≤ query among sets for that key; "" if none

Timestamps for a given key are strictly increasing on set (LC constraint) — so append is sorted.

set("foo","bar",1)
get("foo",1) → "bar"
get("foo",3) → "bar"
set("foo","bar2",4)
get("foo",4) → "bar2"
get("foo",5) → "bar2"

Brute force

Store list of pairs; on get linear scan for best timestamp. O(n) per get.

Optimal: Map + binary search

class TimeMap {
  private store = new Map<string, { t: number; v: string }[]>();

  set(key: string, value: string, timestamp: number): void {
    if (!this.store.has(key)) this.store.set(key, []);
    this.store.get(key)!.push({ t: timestamp, v: value });
  }

  get(key: string, timestamp: number): string {
    const arr = this.store.get(key);
    if (!arr || !arr.length) return "";

    let lo = 0;
    let hi = arr.length - 1;
    let ans = "";

    while (lo <= hi) {
      const mid = lo + ((hi - lo) >> 1);
      if (arr[mid].t <= timestamp) {
        ans = arr[mid].v;
        lo = mid + 1; // try later still ≤ timestamp
      } else {
        hi = mid - 1;
      }
    }
    return ans;
  }
}

set	O(1) amortized append
get	O(log n) per key’s history
Space	O(total sets)

If timestamps were not sorted on insert, you’d binary-insert on set (O(n)) or use a tree map.

Edge cases

• get before any set → ""
• exact timestamp hit
• timestamp between two sets → floor
• many keys independent histories
• large timestamps

Common bugs

• Returning first ≤ instead of last ≤ (must keep searching right)
• Using lower_bound wrong for floor
• Mutating shared string refs unnecessarily

Interview delivery

1. Constraints: increasing timestamps.
2. Append on set.
3. Binary search floor on get.
4. Complexities.
5. Follow-up: unordered timestamps.

Related

• Binary Search
• Search in Rotated Sorted Array
• LRU Cache
• Min Stack

Binary search invariant

We want the rightmost index with t ≤ timestamp. When arr[mid].t ≤ timestamp, record arr[mid].v and search right (lo = mid + 1). When too large, hi = mid - 1. Classic “floor” binary search.

Why not a single global timeline

Keys are independent. A global event log would force filtering by key on every get. Per-key arrays keep get logarithmic in that key’s history only.

Production notes (short)

• If sets can arrive out of order, insert with binary position or use a tree map.
• Memory: store references carefully if values are large.
• Concurrency: not required in LC; mention locking if they go system-design.

Complexity recap

set amortized O(1) append; get O(log n); space O(total sets). Good design question hybrid: data structure + binary search.

Further reading

• LeetCode 981 — Time Based Key-Value Store
• MDN: Map