Problem Statement
Time Based Key-Value Store
We need to build a small storage box that remembers values over time. Each entry has three parts: a key (a name, like "foo"), a value (what we store under that name), and a timestamp (a number that says when we stored it). The box does two jobs. set(key, value, timestamp) saves a value under a key at a certain time. get(key, timestamp) looks up a key and gives back the value that was stored at the latest time that is still at or before the time you asked about. If nothing was stored at or before that time, it returns an empty string. One helpful fact: every time we set the same key, the timestamp is bigger than the last one. So the saved entries for a key naturally come out in order from earliest to latest. When a list is already in order, we can use binary search, which means we cut the list in half over and over instead of checking every item one by one. That is what makes get fast.
Signals to notice
Brute force first
Linear scan all timestamps per key — O(n).
The key insight
Hash map: key → sorted list of (timestamp, value). Binary search for largest timestamp ≤ query. O(log n) per get.
Trace it on set("foo","bar",1); set("foo","bar2",4); get("foo",3) → entries=[(1,"bar"),(4,"bar2")]
set/set build store["foo"]=[(1,"bar"),(4,"bar2")] (appended in ts order)
get("foo",3): left=0, right=1, result=""
mid=0 → ts=1<=3 → result="bar", left=mid+1=1 (search right half for a later valid ts)
mid=1 → ts=4>3 → too late → right=mid-1=0
left=1 > right=0 → loop ends
return result="bar"What must stay true
Timestamps arrive in increasing order — lists are pre-sorted. Binary search finds the rightmost valid version.
Shape of the loop
left, right = 0, len(entries)-1; result = ""
while left <= right:
mid = (left + right) // 2
if entries[mid].ts <= timestamp: # candidate, try for a later one
result = entries[mid].val; left = mid + 1
else: # too late, go earlier
right = mid - 1
return resultPseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Not handling queries before any stored timestamp — return empty string.