Description
Store string values for keys at integer timestamps. get(key, time) returns the value at the largest stored timestamp no greater than time, or an empty string. set timestamps are strictly increasing.
Solution
def create_time_map():
return {}
def set_value(state, key, value, timestamp):
state.setdefault(key, []).append((timestamp, value))
def get(state, key, timestamp):
entries = state.get(key, [])
left, right = 0, len(entries)
while left < right:
middle = (left + right) // 2
if entries[middle][0] <= timestamp:
left = middle + 1
else:
right = middle
return entries[left - 1][1] if left else ""Examples
Example 1
- Input
[["TimeMap"],["set","foo","bar",1],["get","foo",1],["get","foo",3],["set","foo","baz",4],["get","foo",4]]- Output
[null,null,"bar","bar",null,"baz"]
Queries retain the latest value at or before their time.
Example 2
- Input
[["TimeMap"],["get","missing",1]]- Output
[null,""]
An unseen key returns an empty string.
Example 3
- Input
[["TimeMap"],["set","x","a",5],["get","x",4]]- Output
[null,null,""]
No stored timestamp precedes the query.
Approach
Append timestamp/value pairs for each key. A get performs an upper-bound binary search for the first timestamp greater than the query, then returns the previous value.
Time & space
set: amortized O(1); get: O(log m), where m is that key's entry count. O(N) auxiliary space for N stored entries.