Katkat
Back

Design a snapshotable key-value store

AppleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Design a snapshotable key-value store states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

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