Design and implement a snapshotable key–value map supporting the following APIs:
-
S(key, value): set the current value of a string key to a string value.
-
G(key): get the current value for key (or null if absent).
-
Snapshot(): capture the current state and return a snapshotId (opaque string).
-
GS(snapshotId, key): get the value of key as of the given snapshot.
Requirements:
-
Support arbitrarily many snapshots; later writes must not affect earlier snapshots.
-
Be space‑efficient across snapshots (avoid full copies; consider copy‑on‑write or per‑key versioned logs).
-
Target time complexity around O(log u) per operation where u is updates per key (justify alternatives).
-
Define behavior for overwrites, deletions, unknown keys, and consecutive snapshots without intervening writes.
-
Specify snapshotId generation and ordering guarantees.
-
Discuss how to extend to concurrency (reads during writes) and persistence/durability (optional).
Example scenario to satisfy:
S("a", "a-foo"); S("b", "b-foo"); id = Snapshot(); S("a", "a-foo-prime");
G("a") -> "a-foo-prime"
GS(id, "a") -> "a-foo"
G("b") -> "b-foo"
GS(id, "b") -> "b-foo".