Problem overview
You write the class TimeMap. 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 the one asked about. If the key had no value yet at that time, or was never set, Get returns the empty string.
The timestamps of the Set calls are strictly increasing, which makes the whole design possible. Here is the first example, with what each Get returned:
Set("foo", "bar", 1)
Get("foo", 1) gives bar
Get("foo", 3) gives bar
Set("foo", "bar2", 4)
Get("foo", 4) gives bar2
Get("foo", 5) gives bar2
Between times 1 and 3 nothing changed, so the value stays bar. A value set exactly at the time asked about counts, which is why Get("foo", 4) already returns bar2.
In the second example, "love" is set to "high" at 10 and to "low" at 20. Asking at times 5, 10, 15, 20 and 25 gives "", "high", "high", "low" and "low". Asking for the never-set key "hate" gives "".
Approach: sorted lists and binary search
Each key gets its own list of (timestamp, value) pairs. A loop through the list in Get works but costs O(n) per call, where n is the number of values set for that key.
The lists are sorted for free. Every Set has a larger timestamp than every Set before it, so a new pair always belongs at the end of its key's list. Set is a plain Add, O(1), with no sorting.
A sorted list can be searched by halving. Get asks for the last pair whose timestamp is at most the given one. That is a binary search with one twist: when the middle pair is old enough, it is a candidate answer, but a later pair might also qualify, so remember the middle value and keep searching to the right. When the middle pair is too new, so is every pair after it, so search to the left. Each pass halves the positions left to check, so Get takes O(log n): about 17 passes for 100,000 values.
Here is the search over four pairs with timestamps 10, 20, 30, 40, asking for time 35:
left=0 right=3 middle=1 ts=20 -> keep "low", go right
left=2 right=3 middle=2 ts=30 -> keep "mid", go right
left=3 right=3 middle=3 ts=40 -> go left
result mid
The values at those positions were "high", "low", "mid" and "end". The search keeps the best candidate found so far and ends with the pair at timestamp 30, the latest one not after 35.
Step by step
- Declare
store, aDictionary<string, List<(int timestamp, string value)>>set tonew(). The element type is a tuple with two named items, read as.timestampand.value.new()creates an object of the type the field already names. - In
Set, create the key's list if the key is new, then add(timestamp, value)to it. - In
Get, return""if the key was never set. - Put the key's list in
entries(the same list, not a copy) and declareresultas the empty string. If no value is old enough,resultstays empty and that is the answer. - Set
leftto 0 andrighttoentries.Count - 1, both inclusive, and loop whileleft <= 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
entries[middle].timestampis<= timestamp, saveentries[middle].valueinresultand setlefttomiddle + 1. Otherwise setrighttomiddle - 1. - After the loop, return
result.
The solution in C#
class TimeMap {
Dictionary<string, List<(int timestamp, string value)>> store = new();
public void Set(string key, string value, int timestamp) {
if (!store.ContainsKey(key)) {
store[key] = new();
}
store[key].Add((timestamp, value));
}
public string Get(string key, int timestamp) {
if (!store.ContainsKey(key)) {
return "";
}
List<(int timestamp, string value)> entries = store[key];
string result = "";
int left = 0, right = entries.Count - 1;
while (left <= right) {
int middle = (left + right) / 2;
if (entries[middle].timestamp <= timestamp) {
result = entries[middle].value;
left = middle + 1;
} else {
right = middle - 1;
}
}
return result;
}
}
On the C# side: a tuple such as (int timestamp, string value) is a value type with named fields, and (timestamp, value) in Add builds one. Reading store[key] for a missing key would throw a KeyNotFoundException, which is why both methods check ContainsKey first. The expression (left + right) / 2 could overflow for lists with more than a billion entries, but here a key holds at most 100,000 values.
Complexity
- Set: O(1), apart from the occasional growth of a list or the dictionary.
- Get: O(log n), where n is the number of values set for that key. The dictionary lookup is O(1) and the search halves its range each pass.
- Space: O(total number of Set calls), since every value is kept.
Edge cases and common mistakes
- Asking before the first value. Every pair is newer than the time asked about, the search only moves left, and
resultstays"". In the second example,Get("love", 5)does this. - A key that was never set. There is no list for it; return
""before indexing. <instead of<=. A value set exactly at the time asked about must count.- Stopping at the first match. A match is only the latest one so far. Keep searching to the right.
- Each key has its own list. In the third example, "a" is set to "x" at 1 and to "z" at 3, and "b" to "y" at 2. Asking "a" at time 2 gives
x, "b" at time 1 gives"", "b" at time 2 givesy, and "a" at time 3 givesz.
