Problem overview
A time-based key-value store remembers every value a key has ever had, with the time it was set, and can answer what a key's value was at any moment. The class TimeMap has two methods. set(key, value, timestamp) stores a string value for a string key at a time, keeping the key's earlier values. 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, get returns the empty string.
The timestamps of the set calls strictly increase: each set has a larger timestamp than every set before it, whatever the key. The statement asks for O(1) time for set and O(log n) for get, where n is the number of values set for that key.
In the first example, set("foo", "bar", 1) is followed by get("foo", 1) and get("foo", 3), which both return bar: nothing was set between times 1 and 3. After set("foo", "bar2", 4), get("foo", 4) and get("foo", 5) both return bar2. The value set exactly at time 4 counts.
Approach: a sorted list per key, then binary search
The simple solution keeps each key's pairs in a list and scans it from the end, or from the start, until it finds the right one. That is O(n) per get for a key with n values.
The key observation is that the timestamps only go up. So if each key owns a vector of (timestamp, value) pairs and every set appends to the end, each vector is already sorted by time, with no sorting step. set is a single push_back.
A sorted list can be binary searched. The question for get is: what is the last pair whose timestamp is at most the one asked about? Look at the middle pair:
- If its timestamp is
<= timestamp, it could be the answer. Remember its value, then search to the right, because a later pair might still qualify. - Otherwise this pair and everything after it were set too late, so search to the left.
When the search ends, the remembered value is the one with the largest qualifying timestamp. If no pair qualified, nothing was remembered, and the result stays empty. Each pass halves the range, so get takes O(log n): a search over 100,000 values for one key takes 16 passes.
For the key "love", set to high at time 10 and low at time 20, the answers are:
get("love", 5) = ""
get("love", 10) = "high"
get("love", 15) = "high"
get("love", 20) = "low"
get("love", 25) = "low"
get("hate", 25) = ""Step by step
- Declare
storeas anunordered_mapfromstringtovector<pair<int, string>>. Each key maps to its pairs, with.firstthe timestamp and.secondthe value. - In
set, push{timestamp, value}ontostore[key]. For a key that is not in the map yet,store[key]first creates an empty vector, so the first value needs no special case. The new pair has the largest timestamp so far, so the end is its place. - In
get, handle a key that was never set. Ifstore.find(key)equalsstore.end(), return"". - Take a reference to the key's vector:
vector<pair<int, string>> &entries = store[key];. The&makesentriesanother name for the vector inside the map. Without it, C++ would copy the whole vector on every call and undo the speed-up. - Start
resultas the empty string. If no value is old enough, this is the answer. - Set up the search range:
leftat 0 andrightatentries.size() - 1, both ends inclusive. - Loop while
left <= right. With<=, the case where one position is left is still checked. - Compute
middleas(left + right) / 2. Integer division rounds down, which gives a valid position. - If
entries[middle].first <= timestamp, storeentries[middle].secondinresult. - Then move
lefttomiddle + 1to look for a later value that still qualifies. - Otherwise move
righttomiddle - 1. The pair atmiddlewas set aftertimestamp, and so was every pair after it. - Return
result. Each match is at a later position than the one before, soresultends with the value of the largest qualifying timestamp.
The solution in C++
class TimeMap {
public:
unordered_map<string, vector<pair<int, string>>> store;
void set(string key, string value, int timestamp) {
store[key].push_back({timestamp, value});
}
string get(string key, int timestamp) {
if (store.find(key) == store.end()) {
return "";
}
vector<pair<int, string>> &entries = store[key];
string result = "";
int left = 0, right = entries.size() - 1;
while (left <= right) {
int middle = (left + right) / 2;
if (entries[middle].first <= timestamp) {
result = entries[middle].second;
left = middle + 1;
} else {
right = middle - 1;
}
}
return result;
}
};
The C++ details worth a closer look:
operator[]inserts.store[key]creates an empty vector when the key is missing. That is whatsetwants. Inget, it would add a useless empty entry for every unknown key, which is whygetchecks withfindfirst. Afterget("nokey", 5)on a store that holds two keys, the store still holds two keys.- The reference.
vector<pair<int, string>> &entriesbinds to the stored vector. Copying instead would costO(n)per call, and the strings inside would be copied too. pairand braces.push_back({timestamp, value})builds apair<int, string>from the two values. The pair holds its own copy of the string.size()is unsigned.entries.size() - 1would wrap around for an empty vector. Here the vector is never empty: a key is only in the map after asetpushed to it, so there is at least one pair.- The midpoint.
(left + right) / 2could overflowintonly for sizes near 2 billion. With at most 100,000 calls it is safe.
Another way is the standard library's upper_bound, which finds the first pair whose timestamp is greater than the one asked about; the pair just before it is the answer. In a file of your own, with <algorithm> included, this works on the vector {1, "bar"}, {4, "bar2"}:
vector<pair<int, string>> e = {{1, "bar"}, {4, "bar2"}};
auto it = upper_bound(e.begin(), e.end(), ts,
[](int t, const pair<int, string>& p) { return t < p.first; });
string answer = (it == e.begin()) ? "" : (it - 1)->second;For ts equal to 0, 1, 3, 4 and 5, answer is "", bar, bar, bar2 and bar2. The hand-written loop does the same work and shows the idea more directly.
Complexity
Time: O(1) for set, O(log n) for get. set is a hash lookup plus a push_back, which is amortized constant. get does a hash lookup and then a binary search over the n pairs of that key, each pass halving the range. The hash of a key or a string comparison costs time in the length of the strings, which is at most 20 characters.
Space: O(N) for N calls to set, one pair per call.
Edge cases and common mistakes
- A timestamp before the first value.
get("love", 5)must return the empty string. Becauseresultstarts empty and is only assigned on a match, it does. - A timestamp exactly equal to a set time.
get("foo", 4)returnsbar2. Using<instead of<=would skip it and returnbar. - A key that was never set.
get("hate", 25)returns the empty string, and the check withfindkeepsgetfrom creating an entry for it. - Keys do not share values. With
aset toxat 1,btoyat 2, andatozat 3:get("a", 2)isx,get("b", 1)is the empty string,get("b", 2)isyandget("a", 3)isz. The timestamps are increasing across all keys, but each key's own vector is still sorted. - Stopping at the first match. Returning as soon as one pair qualifies gives an old value when a later one also qualifies. The search must keep going right.
- Using
right = entries.size(). The range is inclusive, so the last position issize() - 1. A start ofsize()reads past the end of the vector. - Returning the timestamp instead of the value. The result is
.second, the string.
Testing
set("foo", "bar", 1),get("foo", 1),get("foo", 3),set("foo", "bar2", 4),get("foo", 4),get("foo", 5)givesbar bar bar2 bar2.set("love", "high", 10),set("love", "low", 20), thenget("love", 5),get("love", 10),get("love", 15),get("love", 20),get("love", 25),get("hate", 25)gives"" high high low low "".set("a", "x", 1),set("b", "y", 2),set("a", "z", 3), thenget("a", 2),get("b", 1),get("b", 2),get("a", 3)givesx "" y z.
