Approach Summary
Store values as list of (timestamp, value) pairs per key. Binary search for the largest timestamp <= given timestamp.
How to Recognize This Pattern
- Versioned key-value store
- Binary search on timestamps
Complexity Analysis
Time Complexity
O(log n) get
Space Complexity
O(n)
Tags
Hash Map Binary Search Design