Time-based key-value store

Question

Design a store (think: the last-known reference price of each symbol over a trading day) supporting:

set(key, value, timestamp), record that key had value at time timestamp;
get(key, timestamp), return the value that was set for key at the greatest timestamp less than or equal to the query time, or "" if none exists.

You may assume set is always called with strictly increasing timestamps for a given key.

Make set run in $O(1)$ and get in $O(\log n)$ .

Accepted Answer

For each key you keep a time-ordered history. Because set is called with increasing timestamps, appending keeps the list sorted for free, so set is O(1). A get(key, t) is then a search for the rightmost stored time that does not exceed t, which is a binary search: O(\log n). The clean way to phrase "greatest timestamp \le t" with a library is bisectright, which returns the insertion point just past all entries <= t. The element one slot before it is the answer; index 0 means nothing qualifies. Tracing: set("foo", "bar", 1). Then get("foo", 1): bisectright([1], 1) = 1, so we return vals[0] = "…

Time-based key-value store

Your answer

More Coding questions