Time Based Key-Value Store

The key idea

For each key keep its (timestamp, value) pairs in a list. Because every set uses a strictly increasing timestamp, that list is already sorted by time, so a get is just a binary search for the largest timestamp that is <= the query time (the floor).

Problem

Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key's value at a certain timestamp.

Implement the TimeMap class:

- TimeMap() initializes the object of the data structure.
- set(key, value, timestamp) stores the key with the value at the given time timestamp.
- get(key, timestamp) returns a value such that set was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns "".

It is guaranteed that the timestamps passed to set for the same key are strictly increasing, so each key's history is stored in time order.

Constraints

1 <= key.length, value.length <= 100
key and value consist of lowercase English letters and digits
1 <= timestamp <= 10^7
All the timestamps timestamp of set are strictly increasing per key
At most 2 * 10^5 calls will be made to set and get

Examples

Input: ["TimeMap","set","get","get","set","get","get"] [[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]] Output: [null,null,"bar","bar",null,"bar2","bar2"]

Complexity

Time: O(log n) Space: O(n)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →