You are asked to design an in-memory key–value store that supports versioning and rollback.
Requirements
-
Store key–value pairs in memory (
string
keys, arbitrary JSON/string values is fine).
-
Support
multiple versions
of the store over time.
-
Ability to
rollback
the entire store to a
previous version
.
-
Reads should return values from the
current active version
.
-
Assume single-process (no distributed requirements) unless you explicitly choose to extend it.
Suggested API (you may change it)
-
put(key, value) -> version_id
: writes and creates a new version
-
get(key) -> value | null
: reads from the current version
-
delete(key) -> version_id
-
snapshot() -> version_id
: optional explicit snapshot
-
rollback(version_id) -> void
: make
version_id
the current version
Constraints / Discussion points
-
Target good asymptotic performance for
get
,
put
, and
rollback
.
-
Discuss time/space trade-offs (copy-on-write vs. log-based vs. persistent data structures).
-
Consider edge cases: rolling back and then writing again (branching history), deleting keys, and memory growth.