Time-Based Key-Value Store

Time-Based Key-Value Store

Design a store that keeps every timestamped version of a value and answers “what was the value at time T?” — LeetCode's TimeMap, the read side of MVCC.

Requirements

• Every set records a new version — an existing key keeps all its earlier versions, it is not overwritten.
• get(key, t) performs a floor query on time: it returns the value whose timestamp is the largest one ≤ t.
• If no version of key exists at time t (the key is unknown, or its first set happened after t), return the literal string null.
• Time is logical: it arrives as an argument. Never read a real clock.
• For a fixed key, set timestamps arrive strictly increasing, so a per-key version list stays sorted by construction — target O(log n) reads via binary search.

API to implement

Implement the class TimeMap. The I/O driver is already written in the starter code — it parses the command script below and calls your methods. You only implement the class.

| Command | Returns | Behavior | |---|---|---| | set <key> <value> <timestamp> | — | Store value under key stamped with timestamp. For a given key, successive set timestamps are strictly increasing. | | get <key> <timestamp> | string | Return the value stored for key at the largest stored timestamp that is ≤ timestamp. If key has no value at or before timestamp (or was never set), return the literal string null. |

Input format

The first line contains Q, the number of operations. Each of the next Q lines is one command as listed above. String arguments contain no spaces.

Output format

For each command with a non-void return, print its result on its own line, in order. The driver does this for you — your methods just return values.

This is a design problem: the hidden tests exercise edge cases and interaction sequences, not performance tricks. Model the state cleanly and the tests will pass.

5
set a x 1
get a 0
get a 1
get a 5
get b 1

null
x
x
null

7
set k v1 1
set k v2 4
set k v3 9
get k 3
get k 4
get k 8
get k 100

v1
v2
v2
v3