Design a snapshotable key-value store

Q: Design a snapshotable key-value store

This question evaluates understanding of versioned key-value data structures, snapshot semantics, API design, complexity analysis, and reasoning about concurrency and durability trade-offs.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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".

Design a snapshotable key-value store

Overview

Comments (0)