Problem overview
A time-based key-value store never forgets. Each time a key is set, the new value is stored together with its timestamp, and the older values stay. The class TimeMap has two methods:
set(key, value, timestamp)storesvalueforkeyattimestamp.get(key, timestamp)returns the value whose timestamp is the largest one that is still<= timestamp. If the key was never set, or has no value that old, it returns the empty string"".
The timestamps of the set calls strictly increase: each set has a larger timestamp than every set before it. That promise is what the solution builds on.
Example: set("love", "high", 10) and set("love", "low", 20). Then get("love", 5) is "", because nothing existed yet. At times 10 and 15 the answer is "high"; at 20 and 25 it is "low". A key never set, such as "hate", gives "" at any time.
Approach: sorted lists and binary search
The first idea is to keep, for each key, a list of (timestamp, value) pairs and scan it in get, remembering the last pair whose timestamp isn't too large. It is correct but costs O(n) per get, where n is the number of values set for that key. With 100,000 values on one key and 2,000 calls to get, a scan like that took about 3.4 seconds in a test run.
Look at what the list looks like instead. Timestamps only increase, so appending each new pair at the end keeps the list sorted by time, with no sorting step. A sorted list can be searched by halving. The question "which is the last pair with a timestamp <= t?" is a binary search for the rightmost match. The same 2,000 calls took about 0.008 seconds with the search below.
So set costs O(1) (a dictionary lookup and an append) and get costs O(log n).
Step by step
- In
__init__, setself.storeto an empty dictionary. It maps each key to its list of pairs. - In
set, if the key isn't inself.storeyet, give it an empty list. - Append the tuple
(timestamp, value)to that list. It has the largest timestamp so far, so the end is its place. - In
get, if the key isn't inself.store, return"". Readingself.store[key]for a missing key would raise aKeyError. - Put the key's list in
entries. This is the same list under a shorter name, not a copy. - Create
resultas the empty string. It holds the best value found so far, and stays empty if nothing is old enough. - Set up the search positions:
left, right = 0, len(entries) - 1. Both ends are inclusive. - Loop while
left <= right. With<, the case where one position is left would be skipped. - Compute
middle = (left + right) // 2. The floor division gives a whole number. - If
entries[middle][0] <= timestamp, that value was already set at the asked time, so it is a candidate. Saveentries[middle][1]inresultand movelefttomiddle + 1, because a later entry might be a better candidate. - Otherwise this entry, and every entry after it, is too new. Move
righttomiddle - 1. - After the loop, return
result. Each saved candidate sits at a later position than the one before, so the last one saved has the largest timestamp not above the request.
The solution in Python
class TimeMap:
def __init__(self):
self.store = {}
def set(self, key: str, value: str, timestamp: int) -> None:
if key not in self.store:
self.store[key] = []
self.store[key].append((timestamp, value))
def get(self, key: str, timestamp: int) -> str:
if key not in self.store:
return ""
entries = self.store[key]
result = ""
left, right = 0, len(entries) - 1
while left <= right:
middle = (left + right) // 2
if entries[middle][0] <= timestamp:
result = entries[middle][1]
left = middle + 1
else:
right = middle - 1
return result
Using the class with three values for one key:
tm = TimeMap()
for ts, v in [(1, "a"), (4, "b"), (9, "c")]:
tm.set("k", v, ts)
print(tm.store)
print([(x, tm.get("k", x)) for x in (0, 1, 3, 4, 8, 9, 20)])
{'k': [(1, 'a'), (4, 'b'), (9, 'c')]}
[(0, ''), (1, 'a'), (3, 'a'), (4, 'b'), (8, 'b'), (9, 'c'), (20, 'c')]
Python details worth knowing:
- A tuple such as
(timestamp, value)is one item holding two values.entries[middle][0]is its timestamp andentries[middle][1]its value. //rounds down, somiddleis a valid position. In Python, integers don't overflow, so(left + right) // 2is safe.- The method name
setshadows nothing: it is looked up on the object (tm.set(...)), and the built-insetis unaffected. - The standard
bisectmodule can do this search too, but writing the loop shows how the narrowing works.
Complexity
Time: set is O(1): a dictionary lookup and an append. get is O(log n), where n is the number of values set for that key. Each pass halves the positions still to check, so about 17 passes cover 100,000 values.
Space: O(N) for N values set in total, since every value is kept.
Edge cases and common mistakes
- Before the first value. At time 0 the first entry is already too new, so every step moves
rightleft andresultstays"". - An exact match. The test is
<=, not<:get("k", 4)must return"b". - A time after the last value. The answer is the last value, as
get("k", 20)shows. - A missing key. Check it before reading the dictionary, or a
KeyErrorstops the program. - Stopping at the first match. A binary search that returns as soon as it finds a timestamp
<= tcan give an old value. The search must keep going right after every match. - Keys are independent. A value set for one key never affects another.
Testing
The love example from the overview, run on the class:
tm = TimeMap()
tm.set("love", "high", 10)
tm.set("love", "low", 20)
print([tm.get("love", x) for x in (5, 10, 15, 20, 25)])
print(repr(tm.get("hate", 25)))
['', 'high', 'high', 'low', 'low']
''
