Implement a Versioned Key-Value Store

Design and implement an in-memory versioned key-value store.

Requirements:

• put(key, value, timestamp): store value for key at the given integer timestamp.
• get(key, timestamp): return the value for key with the greatest write timestamp less than or equal to timestamp.
• If no such version exists, return null.
• A key may be updated many times.
• If the same key is written multiple times at the same timestamp, the latest write should overwrite the previous value at that timestamp.
• Discuss the time and space complexity of your implementation.

Example:

put("campaignA", "v1", 10)
put("campaignA", "v2", 20)
get("campaignA", 15) -> "v1"
get("campaignA", 20) -> "v2"
get("campaignA", 5)  -> null

Implement a Versioned Key-Value Store

Design and implement an in-memory versioned key-value store. Process a sequence of operations of two types:

• put(key, value, timestamp): store value for key at the given integer timestamp.
• get(key, timestamp): return the value for key with the greatest write timestamp less than or equal to timestamp.

If no such version exists, return None (this represents null in Python).

A key may be updated many times. If the same key is written multiple times at the same timestamp, the latest write overwrites the previous value at that timestamp.

For this coding problem, implement a function that receives all operations in batch form and returns the results of every get operation in order.

Constraints

• 0 <= n <= 20000, where n is the number of operations
• len(actions) == len(keys) == len(values) == len(timestamps)
• actions[i] is either "put" or "get"
• timestamps[i] are integers in the range [-10^9, 10^9]
• Keys and stored values are strings

Hints

1. Store the version history for each key separately using a hash map.
2. If each key keeps its timestamps sorted, you can use binary search to find the latest timestamp less than or equal to a query time.