Map With History

Build a key-value store that remembers every version of a value, stamped with the time it was written. Unlike a normal Map, where setting a key throws away whatever was there before, this store keeps the full history per key. A read isn't "what is the value now?" — it's "what was the value as of time t?" This is the classic time-based key-value store (sometimes called a TimeMap): writes are timestamped, and a read returns the value of the most recent write at or before the time you ask about.

Signature

class MapWithHistory {
  // Record that `key` had `value` as of `timestamp`.
  // For a given key, timestamps arrive strictly increasing.
  set(key: string, value: unknown, timestamp: number): void;

  // Return the value of the write with the LARGEST timestamp <= `timestamp`.
  // Returns undefined when no such write exists: the key was never written,
  // or every write for it happened strictly after `timestamp`.
  get(key: string, timestamp: number): unknown;
}

Examples

// A read snaps back to the most recent earlier write.
const store = new MapWithHistory();
store.set('a', 'first', 10);
store.set('a', 'second', 20);

store.get('a', 10); // → 'first'   (exact hit on the first write)
store.get('a', 15); // → 'first'   (t=15 is between writes; floor is t=10)
store.get('a', 20); // → 'second'  (exact hit on the second write)
store.get('a', 99); // → 'second'  (after the last write; latest value wins)
store.get('a', 5);  // → undefined (before any write for 'a' existed)

// Each key keeps its own independent history.
const store = new MapWithHistory();
store.set('x', 'x@1', 1);
store.set('y', 'y@2', 2);
store.set('x', 'x@3', 3);

store.get('x', 2); // → 'x@1'      (y's write at t=2 does not leak into x)
store.get('y', 2); // → 'y@2'
store.get('z', 1); // → undefined  (unknown key)

Notes

• A read returns the floor write, not the exact one. Given a query time t, find the write whose timestamp is the largest value that is still <= t. An exact match is just the case where that largest value equals t.
• No write at or before the query means undefined. That happens two ways: the key was never written, or its earliest write is strictly later than t.
• Timestamps per key are strictly increasing. Every set for a given key uses a larger timestamp than the previous set for that key. You may rely on this — but keeping each key's writes sorted by time is the safe assumption either way.
• Values can be anything, including falsy. A stored 0, '', false, or null must come back as itself. Don't let "falsy value" get confused with "no write found," which is the one case that returns undefined.
• The teaching point is the lookup. A correct get should not scan a key's writes one by one. Because each key's list is sorted by time, you can binary search for the floor in O(log n) instead of O(n).
• Keys are independent. Writes under one key never affect reads under another. Don't share a single timeline across keys.