Time Based Key-Value Store
Part of Practice: Rotations & Partitions
Design a key-value store where every write is stamped with a time. It must support two operations:
set(key, value, timestamp)— store the value for the key at the given time.get(key, timestamp)— return the value that was most recently set for the key at or before the given time. If nothing was set that early, return the empty string"".
The crucial guarantee: for each key, set is always called with strictly increasing timestamps. There can be up to 2 * 10^5 total calls, so get needs to be faster than scanning all of a key's history.
Examples
- Input:
- set("foo", "bar", 1); get("foo", 1); get("foo", 3)
- Output:
- "bar", "bar"
At time 1 the stored value is "bar". At time 3 nothing newer exists, so the latest value at-or-before 3 is still "bar".
- Input:
- set("foo", "bar2", 4); get("foo", 4); get("foo", 5)
- Output:
- "bar2", "bar2"
The write at time 4 supersedes the old value for any query at time 4 or later.
- Input:
- get("love", 5) when "love" was never set
- Output:
- ""
Unknown keys return the empty string.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.