Coding - Time Based Key-Value Store

Problem Statement

Design a time-based key-value data structure that can store multiple values for the same key at different timestamps. It should support two operations:

1. set(key, value, timestamp) - Stores the key-value pair with the given timestamp.
2. get(key, timestamp) - Returns the value associated with the largest timestamp less than or equal to the given timestamp. If there is no such value, it returns an empty string.

Here are the specific requirements for each operation:

• set(key, value, timestamp): The value of the key at the given timestamp should be the specified value.
• get(key, timestamp): The key should return the value at the timestamp that is less than or equal to the given timestamp but has the largest timestamp. If there is no such timestamp, return an empty string.

Examples

1. Example 1: TimeMap timeMap = new TimeMap(); timeMap.set("foo", "bar", 1); assert(timeMap.get("foo", 1) == "bar"); assert(timeMap.get("foo", 3) == "bar"); timeMap.set("foo", "bar2", 4); assert(timeMap.get("foo", 4) == "bar2"); assert(timeMap.get("foo", 5) == "bar2");

2. Example 2: TimeMap timeMap = new TimeMap(); timeMap.set("love", "high", 10); timeMap.set("love", "low", 20); assert(timeMap.get("love", 5) == ""); assert(timeMap.get("love", 10) == "high"); assert(timeMap.get("love", 15) == "high"); assert(timeMap.get("love", 20) == "low"); assert(timeMap.get("love", 25) == "low");

Constraints

• All key/value strings are lowercase and only contain ASCII characters.
• All key/value strings have lengths in the range [1, 100].
• The timestamp is a positive integer and can go up to 10^7.
• The number of calls to set and get methods can reach 10^5 in total.
• It's possible that multiple calls of set are made with the same (key, timestamp), but the old value will be overwritten by the new value.

Hints

• Use a map to store the timestamps and values for each key.
• To efficiently find the largest timestamp less than or equal to the given timestamp, consider using a data structure that allows for quick retrieval of the maximum value less than or equal to a given number, such as a balanced binary search tree or a sorted array.