Time-Versioned Key-Value Store and Time-Window Event Counter

Build two small time-aware data structures. The first is a key-value store that keeps every value a key has had, each tagged with the timestamp at which it was set, and answers what a key's value was at a given time. The second, a variant of the same question, counts events by time.

kv = TimeMap()
kv.set("color", "red", 1)
kv.set("color", "blue", 4)
kv.get("color", 3) # "red"
kv.get("color", 4) # "blue"
kv.get("color", 0) # "" (nothing was set at or before time 0)

Clarifying Questions

• Do set calls for one key always arrive with increasing timestamps, or can they arrive out of order?
• Can two set calls for the same key use the same timestamp, and if so, which value wins?
• Roughly how many keys and versions are stored, and must old versions ever be discarded?
• Are reads mostly for recent timestamps, or spread across the whole history?

Part 1 — The value at a point in time

Implement set(key, value, timestamp) and get(key, timestamp). get returns the value that was set for key at the largest timestamp less than or equal to timestamp, or an empty string if there is none.

What This Part Should Cover

• The per-key structure and the lookup, with the cost of set and get
• A missing key, a timestamp before the first write, and an exact match
• What changes if timestamps for a key can arrive out of order

Part 2 — Counting events

Record events as they happen with record(timestamp), and answer how many events fall in a time window with count(...).

Clarifying Questions for this Part

• Is the window an arbitrary range from start to end, or a trailing window that ends at the current time, such as the last five minutes?
• Are events counted for the whole system, or separately per key?
• Must events be kept forever, or only while some window can still include them?

What This Part Should Cover

• A structure matched to the chosen window, with the cost of record and count
• What can be discarded and when, so that memory stays bounded
• Many events sharing one timestamp, and whether the window's edges are inclusive