Build a time-based key-value store

Problem

Design a data structure that stores multiple values for the same key at different timestamps, and can retrieve the most recent value as of a given timestamp.

Implement a class TimeMap with the following operations:

• set(key, value, timestamp)
  • Stores the string value for string key at integer timestamp .
• get(key, timestamp) -> string
  • Returns the value associated with key at the largest timestamp t such that t <= timestamp .
  • If there is no such timestamp for the key, return an empty string "" .

Notes / Constraints (typical)

• key and value are strings.
• timestamp is a positive integer.
• set calls for the same key may be given in increasing timestamp order (state your assumption; if not guaranteed, handle it).
• Target complexity: about O(log m) per get , where m is the number of stored timestamps for that key.