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. ```python 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. ```hint What the history looks like Think about the shape of one key's history when its timestamps arrive in increasing order, and what that allows a lookup to do. ``` #### 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(...)`. ```hint The window decides what to keep Compare what an arbitrary-range query needs to keep with what a trailing window that only moves forward needs. ``` #### 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 ### What a Strong Answer Covers - Settles timestamp order, ties and the window semantics before coding - Binary search over a sorted per-key history, with correct boundary handling - An event counter matched to the window, bounded in memory where the window allows it - The cost of every operation, and the trade-off between exact counts and memory - Boundary tests: before the first write, exact timestamps, and the edges of a window ### Follow-up Questions - The process restarts. How do you keep the history? - Only the last N versions of each key may be kept. What should `get` return for an older timestamp? - A million events per second arrive from many threads. How do you keep `record` cheap? - Several servers record events. How do you combine their counts?