Time Based Key-Value Store
Problem
Design a store with set(key, value, timestamp) and get(key, timestamp). get returns the value from the latest set for that key whose timestamp is ≤ the given timestamp, or "" if there is none. Timestamps for set arrive in strictly increasing order.
Example 1
Input: set("foo","bar",1), get("foo",1), get("foo",3), set("foo","bar2",4), get("foo",4), get("foo",5)
Output: "bar", "bar", "bar2", "bar2"Test cases
Case 1
Input: new TimeMap()
.set("foo", "bar", 1)
.get("foo", 1)
.get("foo", 3)
.set("foo", "bar2", 4)
.get("foo", 4)
.get("foo", 5)
.get("foo", 0)
.get("nope", 1)
Expected: [null,"bar","bar",null,"bar2","bar2","",""]Case 2
Input: new TimeMap()
.set("k", "v1", 1)
.set("k", "v2", 2)
.get("k", 1)
.get("k", 2)
.get("k", 10)
Expected: [null,null,"v1","v2","v2"]Case 3
Input: new TimeMap()
.get("a", 1)
.set("a", "x", 5)
.get("a", 4)
.get("a", 5)
Expected: ["",null,"","x"]View solutionHide solution1 approach
1. Per-key list + upper-bound search
Time set O(1), get O(log n)Space O(n)
Timestamps arrive increasing, so each key’s list is already sorted. get finds the last entry with timestamp ≤ t.
class TimeMap { constructor() { this.m = new Map(); } set(key, value, t) { if (!this.m.has(key)) this.m.set(key, []); this.m.get(key).push([t, value]); } get(key, t) { const a = this.m.get(key) ?? []; let lo = 0, hi = a.length; // first index with time > t while (lo < hi) { const mid = (lo + hi) >> 1; if (a[mid][0] <= t) lo = mid + 1; else hi = mid; } return lo === 0 ? '' : a[lo - 1][1]; }}