Time Based Key-Value Store

Medium

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"]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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];
}
}