Time Based Key-Value Store
mediumTime: O(log n)Space: O(n)
Signals to notice
key-value store with timestampsretrieve value at or before given timebinary search on sorted times
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.
What must stay true
Timestamps arrive in increasing order — lists are pre-sorted. Binary search finds the rightmost valid version.
Easy way to go wrong
Not handling queries before any stored timestamp — return empty string.