Design (key, value) Storage with Snapshots

Design a key-value store that supports point-in-time snapshots. Implement the SnapshotMap class:

• SnapshotMap() Initializes an empty store. The next snapshot id is 0.
• void put(String key, String value) Sets key to value in the current (live) state.
• String get(String key) Returns the current value for key, or "" if key has never been set.
• int snapshot() Freezes the current state and returns its snapshot id. The returned id is the id the snapshot was taken under; the next snapshot will have id one larger. Ids start at 0.
• String getSnapshot(int snapId, String key) Returns the value of key at the moment snapshot snapId was taken. If key had not been set yet at that snapshot, return "". Constraints that motivate the design (from the interviewer):
• The total number of put calls can be very large, so you cannot afford to copy the entire map on every snapshot() call — snapshot() should be O(1).
• put, get, and getSnapshot should each run in O(log U) time, where U is the number of historical versions for the given key. Writes that happen after snapshot() only affect live state and later snapshots — not earlier ones. A snapshot is immutable.

Put two keys, take a snapshot (id=0), overwrite "a". Live get of "a" sees the overwrite; getSnapshot(0, "a") still sees the old value. Key "b" was unchanged after the snapshot, so live and snapshot reads match.

Two snapshots (ids 0 and 1) capture successive values of "k". getSnapshot reads each historical version; live get returns the latest.

Reads for keys that were never set return the empty string, both live and in snapshots.