Problem overview
A time-based store keeps every value a key has ever had, together with the time it was set. You can then ask what a key's value was at any moment: the value set most recently at or before that moment. The class is TimeMap, with two methods:
set(key, value, timestamp)stores the stringvaluefor the stringkeyattimestamp. Earlier values of the key are kept.get(key, timestamp)returns the value whose timestamp is the largest one that is still<= timestamp. If the key has no value at or before that time, or was never set, it returns the empty string"".
The timestamps of the set calls strictly increase. Here is a run on a new TimeMap:
const m = new TimeMap();
m.set("foo", "bar", 1);
console.log(m.get("foo", 1), m.get("foo", 3)); // bar bar
m.set("foo", "bar2", 4);
console.log(m.get("foo", 4), m.get("foo", 5)); // bar2 bar2At time 3, nothing new was set since time 1, so the value is still bar. A value set exactly at the asked time counts: get("foo", 4) is bar2.
With set("love", "high", 10) and set("love", "low", 20), the calls get("love", t) for t = 5, 10, 15, 20, 25 return "" "high" "high" "low" "low", and get("hate", 25) returns "" because "hate" was never set.
Approach: sorted lists and a binary search
Each key needs its own history. Keep, for every key, an array of [timestamp, value] pairs. Because the timestamps of set calls only go up, each new pair belongs at the end, and every array stays sorted by time, oldest first, with no sorting at all. So set is a push: O(1).
For get, the simple way walks through the key's pairs and remembers the last one that isn't after the asked time. That takes O(n) per call, where n is the number of values set for that key. But the array is sorted by time, which is exactly what binary search needs: ask the middle pair. If its time is at or before the asked time, it is a candidate answer, and a later pair could still beat it, so search the right half. Otherwise it and everything after it are too new, so search the left half. Each pass halves the positions left, so get takes O(log n).
This is a binary search for the last position that satisfies a condition, rather than for an exact match. The candidate is saved in result every time the condition holds. Matches are found at later and later positions, so the last one saved is the best one, and if nothing ever matches, result stays the empty string.
Step by step
- Declare
storeas aMap<string, [number, string][]>, set tonew Map().[number, string]is a tuple type, an array of exactly two items, and[number, string][]is an array of those pairs. set, first value of a key: if the map doesn't have the key, store an empty array for it.set, the push: push[timestamp, value]ontothis.store.get(key). The end is the right place, so the list stays sorted.get, unknown key: return""when the map doesn't have the key.- Take the key's array in
entries. This is the same array, not a copy. - Start
resultas"", the answer if no value is old enough. - Set the bounds:
left = 0andright = entries.length - 1, both inclusive. - Loop while
left <= right. With<=, the case where both are equal still checks the one remaining position. - Find
middlewithMath.floor((left + right) / 2). In TypeScript,/keeps the fraction, soMath.flooris needed to get a valid position. - The key test: if
entries[middle][0] <= timestamp, storeentries[middle][1]inresult, and setleft = middle + 1to look for a later value. - Otherwise set
right = middle - 1: the pair atmiddleand all after it were set aftertimestamp. - After the loop, return
result.
The solution in TypeScript
class TimeMap {
store: Map<string, [number, string][]> = new Map();
set(key: string, value: string, timestamp: number): void {
if (!this.store.has(key)) {
this.store.set(key, []);
}
this.store.get(key).push([timestamp, value]);
}
get(key: string, timestamp: number): string {
if (!this.store.has(key)) {
return "";
}
let entries = this.store.get(key);
let result = "";
let left = 0, right = entries.length - 1;
while (left <= right) {
let middle = Math.floor((left + right) / 2);
if (entries[middle][0] <= timestamp) {
result = entries[middle][1];
left = middle + 1;
} else {
right = middle - 1;
}
}
return result;
}
}Details:
Map.getreturnsundefinedfor a missing key, so thehascheck comes first. After it,this.store.get(key)is known to hold an array.- The method is named
setandgetlike theMapmethods it calls, butthis.store.set(...)andthis.store.get(...)are calls on the inner map, whilem.set(...)is the class's own method. - The tuple types are checked only at compile time. At run time each pair is a plain two-element array.
Complexity
set is O(1): one map lookup and a push. get is O(log n) for the n values of that key, since each pass of the loop halves the range, and 100,000 values need at most 17 passes. Space is O(N) for N values stored in total.
Edge cases and common mistakes
- A time before the first value. Every pair is too new, the loop always goes left and
resultstays"". In the"love"example,get("love", 5)returns"". - An exact match counts. The test is
<=, not<. - Stopping at the first match. The answer is the latest value at or before the time, so after a match the search continues to the right. For five pairs at times 10, 20, 30, 40, 50 and the asked time 35, the loop looks at positions 2 (time 30, a match) and 3 (time 40, too new) and ends with the value stored for time 30.
- Keys keep separate histories. After
set("a", "x", 1),set("b", "y", 2)andset("a", "z", 3), the callsget("a", 2),get("b", 1),get("b", 2)andget("a", 3)returnx,"",yandz. - Wrong bounds.
left < rightwould skip the last remaining position.
