Time-Traveling Key-Value Store

Data Structures Design Binary Search

Problem Description

Design and implement a time-based key-value store. This data structure should support storing multiple values for the same key at different timestamps and retrieving the value associated with a key at a given timestamp.

Requirements

Implement the following methods:

  • set(key, value, timestamp): Stores the key and value, along with the given timestamp.
  • get(key, timestamp): Returns the value associated with the key for the largest timestamp less than or equal to the given timestamp. If there is no such timestamp, return an appropriate null/none value.

Consider that multiple values for the same key might be stored, and that retrieval should be optimized for multiple queries. Your solution should efficiently handle a large number of calls and data entries.

Additional Details

  • The keys and values can be assumed to be strings (or any hashable type in your language of choice). The timestamps will be represented as integers, and they are strictly increasing for each key when using the set method.

  • Think about how you will store the data in a way that allows quick look-up and efficient retrieval of the correct value using the timestamp.

  • You are free to choose your programming language and to design the code structure as you see fit. The focus should be on correctness, efficiency, and clarity of your implementation.

Example

Suppose you execute:

set("foo", "bar", 1)
get("foo", 1) // returns "bar"
get("foo", 3) // returns "bar"

set("foo", "bar2", 4)
get("foo", 4) // returns "bar2"
get("foo", 5) // returns "bar2"

In this example, the value retrieved from get for a given timestamp is the value set at the latest timestamp that does not exceed the query timestamp.

Implement this data structure and ensure that your code handles all edge cases as described.