Time Based Key-Value Store

Design a time-based key-value data structure that supports storing multiple values for the same key at different timestamps.

set(key, value, timestamp) stores the key-value pair, and get(key, timestamp) returns the value associated with the largest timestamp less than or equal to timestamp, or an empty string if none exists.

Examples

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"]

Constraints

• 1 <= key.length, value.length <= 100
• 1 <= timestamp <= 10^7
• Timestamps for each key are strictly increasing across set calls.

Company Notes

Reported as LeetCode 981 in a software engineer onsite round.