Design a key-value store that can return the value of a key as it existed at a given timestamp.
Problem
Design a data structure that stores multiple values for the same key over time.
Implement a TimeMap class with two operations:
set(key, value, timestamp): store the stringvalueforkeyat the giventimestamp.get(key, timestamp): return the value associated withkeywhose timestamp is the largest timestamp less than or equal to the giventimestamp.
If no such timestamp exists for the key, return an empty string.
You may assume timestamps for a given key are added in increasing order.
Input Format
A sequence of operations on a TimeMap object:
set(key, value, timestamp)get(key, timestamp)
Output Format
For each get operation, return the stored string value or an empty string if no valid timestamp exists.
Constraints
- Keys and values are strings.
- Timestamps are integers.
- For each key,
setcalls are made with strictly increasing timestamps. - Multiple
getcalls may be made for the same key or timestamp.
Hints
- Store all historical values for each key instead of overwriting the previous one.
- Since timestamps are increasing per key, think about keeping the history in sorted order.
- For a
get, find the latest timestamp that does not exceed the query time.
Constraints
- Keys and values are strings.
- Timestamps are integers.
- For each key,
setcalls are made with strictly increasing timestamps. getshould return the value for the greatest timestamp<=query timestamp.- Return
""if no such timestamp exists.
Example 1
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"]
Explanation
The first value for foo is stored at timestamp 1. A query at timestamp 3 returns the latest value at or before 3, which is bar. After storing bar2 at timestamp 4, queries at 4 and 5 both return bar2.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.