Design SnapshotMap with Sparse Histories and Constant-Time Snapshots

Problem Statement

Design an in-memory key-value map, SnapshotMap, that supports constant-time snapshots and historical point-in-time queries.

To make storage scalable across long-lived processes, the data structure must maintain sparse histories: keys that are not modified in a snapshot period must not duplicate memory. In addition, consecutive modifications or deletions to the same key within the same snapshot window must be coalesced into a single historical record.

Implement the SnapshotMap class with the following methods:

• __init__(): Initializes the map. The initial active snapshot ID is 0.
• put(key: str, val: int) -> None: Sets the key to val for the current active snapshot. Overwrites any previous uncommitted write in the current snapshot.
• get(key: str) -> Optional[int]: Returns the latest value of key. Returns None if the key does not exist or was deleted.
• delete(key: str) -> None: Removes key in the current active snapshot by writing a tombstone. If the key already does not exist, this is a no-op.
• take_snapshot() -> int: Freezes the current state under the current snapshot ID and advances the active snapshot ID by 1. Returns the frozen snapshot ID.
• get_snapshot(key: str, snap_id: int) -> Optional[int]: Returns the value of key as of snap_id. Returns None if the key did not exist or was marked deleted at that snapshot. Raises ValueError if snap_id is invalid (i.e., = current active snapshot ID).

Complexity Requirements

• take_snapshot: O(1) time.
• put, delete: O(1) amortized time.
• get: O(1) average time.
• get_snapshot: O(log H_k) time, where H_k is the number of distinct snapshot versions recorded for key.
• Space: O(K + U), where K is the number of distinct keys and U is the total number of unique (key, snap_id) modification pairs.

Example

sm = SnapshotMap()
sm.put("a", 10)
sm.put("b", 20)

# Coalescing test: overwrite "a" before taking snapshot 0
sm.put("a", 15)

snap0 = sm.take_snapshot()  # returns 0; captures {"a": 15, "b": 20}

sm.put("a", 30)
sm.delete("b")
snap1 = sm.take_snapshot()  # returns 1; captures {"a": 30, "b": None}

sm.get("a")                       # returns 30
sm.get("b")                       # returns None
sm.get_snapshot("a", snap0)       # returns 15
sm.get_snapshot("b", snap0)       # returns 20
sm.get_snapshot("b", snap1)       # returns None (tombstone)
sm.get_snapshot("c", snap0)       # returns None (never set)

Edge Cases to Consider

• Querying a snap_id that does not exist yet (should raise an exception or handle out-of-range cleanly).
• A key deleted and recreated across different snapshots.
• Multiple delete calls or put followed by delete in the same snapshot epoch.
• Keys that were never modified after snapshot 0 must correctly read from their initial entry in future snapshots.