Time Based Key-Value Store

Problem

Design a key-value store where every write is tagged with a timestamp and reads can ask for the value "as of" a given time. Implement a class TimeMap with:

• set(key, value, timestamp): record that key had value at time timestamp.
• get(key, timestamp): return the value that was set for key with the largest timestamp <= timestamp. If no such write exists, return the empty string.

For any given key, calls to set arrive with strictly increasing timestamps.

• Keys and values are non-empty strings of at most 200 characters.
• Timestamps are positive integers no larger than 1,000,000,000.
• Up to 500,000 calls to set and get combined, so per-call work must be logarithmic or better.

Examples

• set("region", "eu-west", 5), then get("region", 5) → "eu-west" and get("region", 9) → "eu-west" (the write at time 5 is the latest one at or before 9).
• Continuing, set("region", "us-east", 12), then get("region", 12) → "us-east", get("region", 30) → "us-east", and get("region", 11) → "eu-west".
• get("region", 4) → "", because nothing was written at or before time 4. get("tier", 100) → "" as well, since that key was never set.

Hints

1. Group the writes by key. Within one key, what order do the timestamps arrive in?
2. get asks for the last timestamp that is not greater than a query value in a sorted list. Which search answers "rightmost element <= x"?
3. Hash map from key to a list of (timestamp, value) pairs; get uses bisect_right on the timestamps and takes the element just before the insertion point.