Time based key-value store

Implement set(key, value, timestamp) and get(key, timestamp), where get returns the value set for the key at the largest timestamp less than or equal to the given one, or "" if there is none. Timestamps for each key arrive in increasing order.

Before you code

Because timestamps arrive in order, each key's history is already a sorted list: no sorting needed. A query is "last entry with timestamp ≤ t".

Hints

1. Map each key to two parallel lists: timestamps and values.
2. get: i = upper_bound(times, t) - 1. If i < 0, return "".
3. Each operation is O(1) for set (append) and O(log n) for get.

Production & complexity notes

When solving Time based key-value store on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Lower and upper bounds to reinforce the underlying pattern.

What it practices

"Last element ≤ x" with an upper bound, from Lower and upper bounds.