Problem overview
A time-based key-value store remembers every value a key has ever had, together with the time it was set. The class TimeMap has two methods. set(key, value, timestamp) stores a string value for a string key at a given time and keeps the key's earlier values. get(key, timestamp) returns the value set for that key with the largest timestamp that is still less than or equal to timestamp. If the key had no value at or before that time, or was never set, it returns the empty string.
The constraints add one important promise: the timestamps of set calls are strictly increasing, so each new set is later than every one before it.
The first example: set("foo", "bar", 1), then get("foo", 1) and get("foo", 3), then set("foo", "bar2", 4), then get("foo", 4) and get("foo", 5). The four get calls return:
"bar" "bar" "bar2" "bar2"
At time 3 nothing newer than "bar" has been set, so "bar" is still the value. A value set exactly at the asked time counts, so get("foo", 4) already sees "bar2".
Approach: sorted lists and binary search
For each key, keep a list of [timestamp, value] pairs. Because timestamps only go up, a new pair belongs at the end of its list, and every list stays sorted by time with no sorting at all. So set is a push: O(1).
A simple get walks through the key's list and remembers the last pair whose timestamp is not after the query. That costs O(n) per call, where n is the number of values set for that key. With a key that holds 100,000 values, 2,000 get calls of this kind took 486 ms in a test run, while the binary search version took 0.93 ms for the same 2,000 calls, with identical answers.
A sorted list can be binary searched. The question is "the last pair whose timestamp is at most timestamp", which is a slight variation on finding an exact match. Look at the middle pair. If its timestamp is at most the query, it is a candidate answer, and every pair before it is older, so only a later pair could beat it: remember it and search the right half. If its timestamp is after the query, so is everything to its right: search the left half. When the range is empty, the last remembered candidate is the answer, or nothing was remembered and the answer is the empty string. Each pass halves the range, so get takes O(log n): about 17 passes for 100,000 values.
Here is a key "k" with five values, stored as [[1,"a"],[3,"b"],[5,"c"],[7,"d"],[9,"e"]], and the query get("k", 6). The search visits:
left 0 right 4 middle 2 time 5
left 3 right 4 middle 3 time 7
result "c"
At middle 2 the time 5 is at most 6, so "c" is remembered and the search moves right. At middle 3 the time 7 is after 6, so the right edge moves left of it, the range is empty, and "c" is returned. For the same list, get("k", 0) returns "" because no value is that old, get("k", 100) returns "e", and get("k", 1) returns "a".
Step by step
- Constructor: set
this.storeto a newMap. It maps each key to its array of pairs. - set: if
this.storedoes not havekeyyet, store an empty array for it. The first value of a key needs a list to go into. - Push
[timestamp, value]onto the key's array,this.store.get(key). This pair has the largest timestamp so far, so the end is its place. - get: if the store does not have
key, return"". A key that was never set has no value at any time. - Put the key's array in
entries. It is the same array under a shorter name, not a copy. - Declare
resultas the empty string. It holds the best value found so far, and stays empty if no value is old enough. - Declare
leftas 0 andrightasentries.length - 1. Both ends are inclusive. - Loop while
left <= right. With<the loop would skip the case where one position is left to check. - Compute
middleasMath.floor((left + right) / 2). In JavaScript/keeps the fraction, soMath.floorturns it into a valid position. - If
entries[middle][0] <= timestamp, storeentries[middle][1]inresult. This is the key idea: the value was already set at the asked time, so it can be the answer. The comparison is<=, not<, because a value set exactly attimestampcounts. - In the same branch, move
lefttomiddle + 1to look for a later value that is still not aftertimestamp. - Otherwise move
righttomiddle - 1: the value atmiddlewas set aftertimestamp, and so was every value after it. - After the loop, return
result.
The solution in JavaScript
class TimeMap {
constructor() {
this.store = new Map();
}
set(key, value, timestamp) {
if (!this.store.has(key)) {
this.store.set(key, []);
}
this.store.get(key).push([timestamp, value]);
}
get(key, timestamp) {
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;
}
}
JavaScript details:
Mapinstead of a plain object.has,getandsetread and write entries by key. The method namedsetonTimeMapis separate from theMap's ownset: inside the class,this.store.set(key, [])calls the map's.- Pairs are arrays. For a pair
p,p[0]is the timestamp andp[1]the value. Pushing one array per call keeps the two together. - Arrays are shared.
let entries = this.store.get(key)does not copy:entriesand the stored array are the same object, which is why this line is free. let left = 0, right = ...declares two variables in one statement.
Complexity
Time: set is O(1): a map lookup and an array push. get is O(log n), where n is the number of values set for that key: one map lookup and a binary search that halves the range on every pass.
Space: O(N) for N stored values in total, one pair each.
Edge cases and common mistakes
- A key that was never set.
get("hate", 25)returns"". Without thehascheck,entries.lengthwould fail onundefined. - A time before the first value. In the second example,
get("love", 5)returns""because "love" was first set at time 10. The result variable starts empty and nothing overwrites it. - The exact timestamp.
get("love", 10)returns"high", the value set at 10. Using<instead of<=would miss it. - Returning the first match. Stopping at the first pair with a timestamp at most the query returns an old value. Keep searching to the right to find the latest one.
- Keys are independent. In the third example,
get("a", 2)returns"x", because "z" is set only at time 3, andget("b", 1)returns"", because "b" first gets a value at time 2. - Sorting on every call. Unnecessary and slow. Timestamps arrive in order, so the end of the list is always the right place.
Testing
Outputs of the solution above:
- Example 1 returns
"bar" "bar" "bar2" "bar2". - Example 2 (
"love"set to "high" at 10 and "low" at 20), the gets at times 5, 10, 15, 20, 25 return"" "high" "high" "low" "low", andget("hate", 25)returns"". - Example 3 returns
"x" "" "y" "z". - The key with five values above:
get("k", 6)returns"c",get("k", 0)returns"",get("k", 100)returns"e".
