Design SnapshotMap with Sparse Histories and Constant-Time Snapshots

Design a `SnapshotMap` with the following operations: - `put(key, value)` writes the current value. - `get(key)` reads the current value. - `delete(key)` removes the key from the current map. - `take_snapshot()` returns a snapshot identifier. - `get(key, snapshot_id)` reads the value present in that historical snapshot. A value that does not change between snapshots must not be copied into storage again for each snapshot. Every operation must avoid work linear in the entire map size. The approximate workload is one million keys, ten snapshots, and changes to about 1% of keys between snapshots. Explain the data structures, version semantics, deletion behavior, and storage costs. State assumptions about missing keys, value mutability, snapshot numbering, and whether time guarantees are expected, amortized, or worst case. Those API details are not fully specified. ### What a Strong Answer Covers - Historical reads that remain stable after later writes or deletions. - A way to capture a snapshot without copying or scanning the full map, including unchanged snapshots. - Coalescing repeated writes to one key between snapshots and retaining deletion information when older snapshots still need the key. - Predecessor lookup in each key's change history, with a distinction between an absent key and a stored null-like value. - Complexity in the number of tracked keys, snapshots, and actual changes, including the fact that a fixed 1% scan is still linear in map size. ```hint Snapshot work need not happen at snapshot time Decide whether a write can record the version interval it belongs to before a snapshot freezes that interval. ``` ### Follow-up Questions - What should remain in history if a key changes and then returns to its previous snapshot value before the next snapshot? - How would the design preserve snapshot stability if callers can mutate a value object after passing it to `put`?