Time Based Key-Value Store
mediumTime: O(log n)Space: O(n)
Recognize the pattern
key-value store with timestampsretrieve value at or before given timebinary search on sorted times
Brute force idea
Linear scan all timestamps per key — O(n).
Better approach
Hash map: key → sorted list of (timestamp, value). Binary search for largest timestamp ≤ query. O(log n) per get.
Key invariant
Timestamps arrive in increasing order — lists are pre-sorted. Binary search finds the rightmost valid version.
Watch out for
Not handling queries before any stored timestamp — return empty string.