Leetcode - Time Based Key-Value Store

Question

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.
• void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp.
• String get(String key, int 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 "".

Ideas

• Basically the exact same as solving Leetcode - Snapshot Array
• The idea here is that we want to store lists of [timestamp, value] in a hashmap at key where timestamp is guaranteed to be inserted monotonically. As such, we can just append to the end of the key list.
• We want to now run a Binary Search on a mapping[key] to get either the value at a timestamp, or the leftmost value given a timestamp if that timestamp cannot be found.

Solution