Design (key, value) Storage with Snapshots

Design a key-value store that supports point-in-time snapshots. Examples Example 1: Input: ["SnapshotMap","put","put","snapshot","put","get","getSnapshot","get","getSnapshot"] [[],["a","a-foo"],["b","b-foo"],[],["a","a-foo-prime"],["a"],[0,"a"],["b"],[0,"b"]] Output: [null,null,null,0,null,"a-foo-prime","a-foo","b-foo","b-foo"] Explanation: 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. Example 2: Input: ["SnapshotMap","put","snapshot","put","snapshot","getSnapshot","getSnapshot","get"] [[],["k","v0"],[],["k","v1"],[],[0,"k"],[1,"k"],["k"]] Output: [null,null,0,null,1,"v0","v1","v1"] Explanation: Two snapshots (ids 0 and 1) capture successive values of "k". getSnapshot reads each historical version; live get returns the latest. Example 3: Input: ["SnapshotMap","snapshot","getSnapshot","get"] [[],[],[0,"missing"],["missing"]] Output: [null,0,"",""] Explanation: Reads for keys that were never set return the empty string, both live and in snapshots. Constraints At most 10^5 total method calls 1 <= key.length, value.length <= 100 (lowercase letters, digits, and dashes) 0 <= snapId < number of snapshots taken snapshot() is O(1); do not copy the full map on snapshot