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(String key, String value, int timestamp) stores a value for a key at a time and keeps the key's earlier values. get(String key, int timestamp) returns the value that was set for the key with the largest timestamp that is still less than or equal to the one asked about. If nothing was set for the key at or before that time, or the key was never set, it returns the empty string "".
The constraints say that the timestamps of the set calls are strictly increasing: each set has a larger timestamp than every set before it. Here is a session.
TimeMap tm = new TimeMap();
tm.set("foo", "bar", 1);
System.out.println("[" + tm.get("foo", 1) + "] [" + tm.get("foo", 3) + "]");
tm.set("foo", "bar2", 4);
System.out.println("[" + tm.get("foo", 4) + "] [" + tm.get("foo", 5) + "]");
System.out.println("[" + tm.get("foo", 0) + "] [" + tm.get("nope", 5) + "]");
[bar] [bar]
[bar2] [bar2]
[] []
At time 1, "foo" was set to "bar", so get("foo", 1) returns it. Nothing changed until time 4, so at time 3 the value is still "bar". From time 4 on, the answer is "bar2". Before the first value, at time 0, and for a key never set, the answer is the empty string. The brackets in the output only make the empty strings visible.
Approach: a sorted list per key, then binary search
The simple approach stores each key's values in a list and, for every get, scans the list for the latest entry whose timestamp is not after the one asked about. That is O(n) per call, where n is the number of values set for that key, and it is slow when one key has tens of thousands of values.
The guarantee about set makes something better possible. Because timestamps only go up, appending each new pair to the end of its key's list keeps the list sorted by timestamp, oldest first, with no sorting at all. So set costs O(1). And a sorted list can be binary searched, which makes get cost O(log n).
The search is not the usual one for an exact match. It looks for the last position whose timestamp is at most the one asked about. Whenever the middle entry qualifies (its timestamp is less than or equal to the query), it is a candidate answer, and anything better must lie to its right, so the search moves right. Whenever the middle entry is too new, it and everything after it are ruled out, so the search moves left. The last candidate seen is the answer, and if there was none, the answer stays empty.
Step by step
- Declare the field
store: a map from each key to a list of (timestamp, value) pairs. Java's pair isMap.Entry<Integer, String>, made withMap.entry(a, b)and read withgetKey()andgetValue(). - In
set, create an empty list for the key if the key is new. - Add
Map.entry(timestamp, value)to the key's list. It has the largest timestamp so far, so the end is its place. - In
get, return""if the key was never set. - Keep the key's list in the variable
entries. This is the same list under a shorter name, not a copy. - Declare
resultas"". It holds the best value found so far, and stays empty if no value is old enough. - Declare
leftas 0 andrightasentries.size() - 1, both ends inclusive. - Loop while
left <= right. With<the last remaining position would never be checked. - Compute
middleas(left + right) / 2. Integer division rounds down, so it is a valid position. - If the timestamp at
middleis at most the query, this value was already set at that time. Store its value inresult. - Then set
left = middle + 1to look for a later value that still qualifies. - Otherwise set
right = middle - 1. This entry was set after the query, and so was every entry after it. - After the loop, return
result.
The solution in Java
class TimeMap {
Map<String, List<Map.Entry<Integer, String>>> store = new HashMap<>();
public void set(String key, String value, int timestamp) {
if (!store.containsKey(key)) {
store.put(key, new ArrayList<>());
}
store.get(key).add(Map.entry(timestamp, value));
}
public String get(String key, int timestamp) {
if (!store.containsKey(key)) {
return "";
}
List<Map.Entry<Integer, String>> entries = store.get(key);
String result = "";
int left = 0, right = entries.size() - 1;
while (left <= right) {
int middle = (left + right) / 2;
if (entries.get(middle).getKey() <= timestamp) {
result = entries.get(middle).getValue();
left = middle + 1;
} else {
right = middle - 1;
}
}
return result;
}
}
A few details about the Java code:
Map.Entryas a pair.Map.entry(timestamp, value)boxes theintinto anInteger. The entries it creates are immutable: callingsetValueon one throwsUnsupportedOperationException, which is fine because the store never changes a pair.- Comparing a boxed value.
entries.get(middle).getKey() <= timestampunboxes theIntegerand compares numbers. The relational operators unbox, which is safe. Writing==between twoIntegerobjects would compare references instead, and gives wrong answers for larger values. (left + right) / 2. With at most 100,000 values per key this sum cannot overflow anint. With lists of billions of entries,left + (right - left) / 2would be the safe form.- Empty string, not
null.store.get(key)would returnnullfor a missing key, so the method checkscontainsKeyfirst and returns"".
Seeing it work
Each key keeps its own list. After set("love", "high", 10) and set("love", "low", 20), asking at times 5, 10, 15, 20 and 25 gives:
TimeMap tm2 = new TimeMap();
tm2.set("love", "high", 10);
tm2.set("love", "low", 20);
for (int t : new int[]{5, 10, 15, 20, 25}) {
System.out.print("[" + tm2.get("love", t) + "] ");
}
[] [high] [high] [low] [low]
At time 5 the key has no value yet. Times 10 and 15 see "high": a value set exactly at the asked time counts, which is why the comparison is <=. Times 20 and 25 see "low".
To follow a search by hand, take that list, [(10, high), (20, low)], and the query 15. The range is positions 0 to 1, so middle is 0. The timestamp 10 is at most 15, so result becomes "high" and left moves to 1. Now middle is 1, and 20 is more than 15, so right moves to 0. The range is empty and the method returns "high".
Complexity
set: O(1). It is a map lookup and a list append. No sorting is needed, because timestamps arrive in increasing order.
get: O(log n), where n is the number of values set for that key. Each pass of the loop halves the range, so a list of 100,000 values needs about 17 passes. The lookup of the key in the map is O(1) on average. Scanning the list would take O(n) per call.
Space: O(N) for N pairs in total, because every value is kept.
Edge cases and common mistakes
- A key that was never set. Return
""before touching the list, since there is none. - A time before the first value. Every entry is too new, so the search keeps moving left and
resultstays"". - Using
<instead of<=. A value set exactly at the asked time would be missed:get("foo", 4)would return"bar"instead of"bar2". - Stopping at the first match. An exact-match binary search returns as soon as it finds the timestamp, but here a later entry may also qualify. After a match the search must keep going right.
- Using
left < rightas the loop condition. A one-element range would be skipped and a single stored value would never be found. - Sorting in
set. It is unnecessary. The sorted order comes for free from the increasing timestamps, and sorting would turnsetintoO(n log n).
