Time-based key-value store
A settings service never forgets. Every write is stamped with the second it happened, and a read can ask what a key held at any second.
Build a class TimeMap:
TimeMap()starts with no keys.set(key, value, timestamp)records thatkeytook the valuevalueat secondtimestamp.get(key, timestamp)returns whatkeyheld at secondtimestamp: the value of the latestseton that key whose timestamp is at mosttimestamp. If there is no suchset(the key was never written, or only later), return the empty string"".
The timestamps of set calls strictly increase from one call to the next, across all keys. A get can ask about any second, earlier or later than the last write, and changes nothing.
set("color", "red", 1), set("color", "blue", 4), get("color", 3), get("color", 4), get("color", 9), get("color", 0)Outputthe four get calls return "red", "blue", "blue", ""At second 3 the latest write is red, from second 1. At second 4 the blue write counts, because its timestamp is at most 4. At second 0 nothing had been written yet.
set("mode", "on", 2), set("size", "big", 3), set("mode", "off", 7), get("mode", 6), get("size", 6), get("mode", 7), get("theme", 7)Outputthe four get calls return "on", "big", "off", ""Each key has its own history, so the write to size at second 3 does not touch mode. The key theme was never written.
0 ≤ timestamp ≤ 107
Timestamps of
setcalls strictly increase across all calls.Keys and values are non-empty strings of lowercase letters and digits.
Up to 2 × 105 calls in total. One key can be written up to 105 times.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.