Value at a Point in Time
Problem
A config service keeps every version of every setting. set(key, value, t) records that key took value at time t, and for any one key the times always arrive in strictly increasing order. get(key, t) returns the value the key had at time t, meaning the value from the latest set with time at most t, or "" if the key had no value yet. There are up to 200,000 calls in total and times go up to 10^7, so a get must not scan all of a key's versions.
Examples
Input: set("theme", "light", 1), get("theme", 1), get("theme", 3),
set("theme", "dark", 4), get("theme", 4), get("theme", 5)
Output: ["light", "light", "dark", "dark"]
Why: at time 3 the latest version is still the one written at 1Input: set("port", "80", 10), get("port", 9), get("port", 10)
Output: ["", "80"]
Why: before time 10 the key has no value yetInput: get("missing", 7)
Output: [""]
Why: edge case, a key that was never setHints
0 / 3
Store each key's versions in a list. Since times arrive in increasing order, appending keeps the list sorted for free.
A lookup needs the last version whose time is at most t, which is a boundary search on a sorted list rather than a search for an exact match.
bisect_right(times, t) returns the number of versions with time at most t. If it is 0 the answer is the empty string, otherwise take the value just before that position.
Solution
Each key gets two parallel lists, one of times and one of values. Because set is called with increasing times for a key, appending keeps the time list sorted without any extra work, so set is O(1). A lookup wants the rightmost time that is at most t, and bisect_right answers exactly that: it returns the position where t would be inserted after any equal times, so everything before that position is at most t. A position of 0 means no version is old enough and the answer is the empty string; otherwise the value just before it is the one in effect. Each get costs O(log v) for v versions of the key, and space is O(total calls).
from bisect import bisect_right
class VersionedStore:
def __init__(self):
self.times, self.values = {}, {}
def set(self, key, value, t):
self.times.setdefault(key, []).append(t) # times stay sorted
self.values.setdefault(key, []).append(value)
def get(self, key, t):
i = bisect_right(self.times.get(key, []), t) # versions with time <= t
return self.values[key][i - 1] if i else ""
store = VersionedStore()
store.set("theme", "light", 1)
early = [store.get("theme", 1), store.get("theme", 3)]
store.set("theme", "dark", 4)
store.set("port", "80", 10)
print(early + [store.get("theme", 4), store.get("theme", 5)]) # -> ['light', 'light', 'dark', 'dark']
print([store.get("port", 9), store.get("port", 10)]) # -> ['', '80']
print([store.get("missing", 7)]) # -> ['']Stuck on the idea rather than the code? Binary Search covers it.