Time Based Key-Value Store
Medium · Design · Hash Table · String · Binary Search · Design
Problem
Build a key-value store that keeps every version of each key:
- set(key, value, timestamp) stores value for key at time timestamp.
- get(key, timestamp) returns the value key had at time timestamp: the value from the latest set whose timestamp is at or before timestamp. If there is none, because the key was never set or was only set later, return the empty string "".
The timestamps passed to set are strictly increasing across all calls, so each key's versions arrive already in time order. get may ask about any time: before the first version, exactly at one, between two, or after the newest.
Tests replay a call sequence: the first entry names the class, each later entry is a method with its arguments, and calls returning nothing report None.
Examples
Input: set("foo","bar",1), get("foo",1), get("foo",3), set("foo","bar2",4), get("foo",4), get("foo",5)
Output: "bar", "bar", "bar2", then "bar2"At time 3 the latest version at or before 3 is the one from time 1. From time 4 on, bar2 is the newest.
Input: set("love","high",10), set("love","low",20), get("love",5), get("love",10), get("love",15), get("love",20), get("love",25)
Output: "", "high", "high", "low", then "low"Nothing was stored for love before time 10, so time 5 gives the empty string. Time 15 falls between the two versions and gets the older one.
Constraints
- 1 <= len(key), len(value) <= 100
- key and value are lowercase English letters and digits
- 1 <= timestamp <= 10^7
- set timestamps are strictly increasing
- Up to 2 * 10^5 calls to set and get in total
Approaches
- Scan the history backwards — time O(1) set, O(k) get, space O(n)
Related problems
Start free on Cariara · Coding problems · System design studio
