Time Based Key-Value Store
Design a key-value store that returns the value at any past time: append on set, and binary search the timestamps on get.
Problem Understanding
Time Based Key-Value Store: implement set(key, value, timestamp) and get(key, timestamp). get returns the value set for key at the largest timestamp not later than the one asked for, or "" if there is none. Timestamps given to set strictly increase.
Example: after set("foo", "bar", 1), both get("foo", 1) and get("foo", 3) return "bar". After set("foo", "bar2", 4), get("foo", 4) and get("foo", 5) return "bar2".
The Intuition: Each Key's History Is a Sorted Array
Because timestamps only increase, appending each set to its key's list keeps that list sorted by time for free. A get then asks a classic binary search question: what is the last entry with time ≤ t?
- Search the half-open range
[0, len)for the first timestamp greater than t. - If
pairs[mid].time ≤ t, that entry is usable but a later one might be too:lo = mid + 1. - Otherwise it is too late:
hi = mid. - When the loop ends,
lo − 1is the last usable entry; iflois 0, return"".
This is the mirror image of Search Insert Position, which looks for the first value ≥ a target.
Interactive Walkthrough
The calls run in order along the top, with each return value shown once it is known. Below, the key's entries are listed oldest first; during a get, the search range is shaded, mid is filled, and the returned entry turns green.
Dry Run Table
Store: foo → [(1, bar), (4, bar2)], call get("foo", 2)
| lo | hi | mid | time | Action |
|---|---|---|---|---|
| 0 | 2 | 1 | 4 | 4 > 2: hi = 1 |
| 0 | 1 | 0 | 1 | 1 ≤ 2: lo = 1 |
| 1 | 1 | — | — | return pairs[0] = bar |
The Solution Template
A list of (timestamp, value) per key, and an upper-bound binary search in get. The C snippet keeps keys in a small array with fixed capacities, for brevity.
Time Based Key-Value Store Code
1var TimeMap = function() {2 this.store = new Map();3};45TimeMap.prototype.set = function(key, value, timestamp) {6 if (!this.store.has(key)) this.store.set(key, []);7 this.store.get(key).push([timestamp, value]);8};910TimeMap.prototype.get = function(key, timestamp) {11 const pairs = this.store.get(key) || [];12 let lo = 0, hi = pairs.length;13 while (lo < hi) {14 const mid = (lo + hi) >> 1;15 if (pairs[mid][0] <= timestamp) lo = mid + 1;16 else hi = mid;17 }18 return lo === 0 ? '' : pairs[lo - 1][1];19};
Edge Cases & Common Mistakes
- A key that was never set: return
""; don't index into an empty list. - A time earlier than every set:
loends at 0, so return"". - Searching for ≥ instead of >: for an exact match you would return the next entry; it is
time ≤ tthat must moveloright. - Scanning the list linearly: correct but O(n) per get; with up to 2 × 10⁵ calls that times out.
Summary
Keep a list of (timestamp, value) per key; set appends, and the increasing timestamps keep it sorted. get binary searches for the first timestamp greater than t and returns the entry before it, or "" if there is none. set is O(1), get is O(log n).
More practice: DSA interview questions with answers · patterns cheat sheet