visual walkthrough
Time Based Key-Value Store
A design question whose core is upper-bound search.
The idea
Timestamps only go up, so appending each set keeps the history sorted with no extra work.
get(t) is then "the last entry with time ≤ t": a binary search for a boundary.
Complexity
| approach | time | space |
|---|---|---|
| Scan the history | O(n) per get | O(n) |
| Binary search the history | O(log n) per get | O(n) |