OA: Versioned store with real clocks and threads

medium 4 levels ~60 min OpenAI

Level 1 Versioned values with real timestamps

Build TimeMap, a key-value store that remembers every version of a value together with when it was written.

set(key, value, timestamp): timestamp is a float (Unix seconds, e.g. 1_700_000_000.25). Writes can arrive out of order: an older timestamp may show up after a newer one. If the same key gets two writes with exactly the same timestamp, the later call replaces the earlier value.
get(key, timestamp) -> str: the value whose timestamp is the largest one <= timestamp, or "" if the key has no value at or before that time (or doesn't exist).

tm = TimeMap()
tm.set("user:1", "online", 1000.0)
tm.set("user:1", "away", 1060.5)
tm.set("user:1", "booting", 990.0)   # late arrival
tm.get("user:1", 995.0)     # "booting"
tm.get("user:1", 1060.49)   # "online"
tm.get("user:1", 5000.0)    # "away"
tm.get("user:1", 10.0)      # ""
tm.get("ghost", 1000.0)     # ""

Scanning every version on each get, or re-sorting on every call, is too slow for the big test: aim for O(log n) per get, plus the cost of inserting a late write.

Show hint

Keep each key's versions sorted by timestamp and binary search them with bisect, both to answer get and to find where a late write goes.

Level 2 unlocks when level 1 passes.

Level 3 unlocks when level 2 passes.

Level 4 unlocks when level 3 passes.

Topic: Time-travel key-value store. Per-key sorted history + binary search on timestamp.