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

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

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.

What difficulty level is this interview question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Apple.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Apple during technical interviews.

Design a snapshotable key-value store | Apple Interview 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 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

Quick Overview

Submit Your Answer

Design a snapshotable key-value store

Quick Overview

Submit Your Answer