Key-Value Store with Checkpoint Rollback and Ambiguity-Aware Prefix Reads

Implement an in-memory key-value store with string keys and string values. Besides ordinary writes, it must support two features: - **Checkpoints.** The caller can take a checkpoint and later return the store to exactly the state it had at that checkpoint, undoing every write made since. - **Reads by prefix.** A read passes a prefix instead of a full key. If exactly one stored key starts with the prefix, the read returns that key's value. If two or more stored keys start with it, the read must report that the prefix is ambiguous. For example, with the keys `ABC` and `ABD` stored, reading `AB` is ambiguous, while reading `ABD` returns the value stored under `ABD`. A starting interface, to adjust with the interviewer: - `set(key, value)`: store `value` under the full key `key`, overwriting any previous value. - `get(prefix)`: return the value of the single stored key that starts with `prefix`, or report that the prefix is ambiguous or matches no key. - `checkpoint()`: record the current state. - `rollback()`: return the store to a recorded checkpoint. The interviewer imposes time-complexity limits, so give the cost of every operation. In particular, consider what taking a checkpoint and rolling back cost when the store holds many keys. ```hint What a checkpoint must remember Copying every key at each checkpoint makes a checkpoint as expensive as the store is large. Ask what, at minimum, you need to keep in order to put back the state from the time of the checkpoint. ``` ```hint Answering "ambiguous" quickly Scanning every key on each read will not meet a complexity limit. Think about what an index would have to know about each prefix to tell zero, one, or several matching keys apart. ``` ### Constraints and Clarifications - Assume one caller issuing operations one at a time. - The result of `get` must not be confusable with a stored value: a key whose value is the text "ambiguous" must still be readable. ### Clarifying Questions - If one stored key is a prefix of another, for example `AB` and `ABC`, should reading `AB` return the value of `AB` or report that it is ambiguous? - Can several checkpoints be outstanding at once? Does rolling back consume the checkpoint, and can the caller return directly to an older one? - Do writes ever address a key by prefix? If so, must a write to an ambiguous prefix be rejected? - Is the empty string a valid key or prefix? - What are the target complexities for `set`, `get`, `checkpoint` and `rollback`? ### What a Strong Answer Covers - A checkpoint mechanism whose cost does not grow with the size of the store, restoring overwritten values and removing keys created after the checkpoint - A prefix index that distinguishes a unique match, an ambiguous prefix and no match without scanning all keys, kept consistent through writes and rollbacks - Explicit, consistent policies for a key that is a prefix of another key and for multiple checkpoints - Time and space complexity for every operation, including how much memory the checkpoint mechanism accumulates - Test cases or a walkthrough covering overwrite then rollback, create then rollback, and an ambiguity that appears and disappears across a rollback ### Follow-up Questions - How would you add `delete(key)`, and how does it interact with rollback and the prefix index? - How would you discard a checkpoint without rolling back, so that the memory it holds can be freed? - Many keys share long common prefixes, such as identifiers with a fixed leading part. How do your index's memory and time behave, and what would you change? - How would you return to an arbitrary earlier checkpoint without undoing writes one at a time?