In-Memory Key-Value Store with Nested Begin, Commit, and Rollback Transactions

Implement an in-memory key-value store that supports transactions: - `set(key, value)` sets `key` to `value`. - `unset(key)` removes `key`. - `get(key)` returns the current value of `key`, or `None` if it is not set. A read is needed to observe the store, so implement it too. - `begin()` opens a new transaction block. - `rollback()` undoes every change made in the most recent open block, and closes that block. - `commit()` makes changes permanent. Once a change has been committed, it can no longer be rolled back. Blocks can be nested: a `begin` inside an open block opens an inner block. Changes made outside any block take effect immediately and permanently. ```hint What rollback needs For each open block, think about the minimum information you must remember in order to restore the store, and when you need to capture it. ``` ```hint Absent is a state too Rolling back must also restore keys that did not exist before the block, and keys that the block unset. ``` ### Constraints and Clarifications - A single client issues commands one at a time; there is no concurrency. - Assume keys and values are strings. - Reads inside a block see that block's own uncommitted changes. ### Clarifying Questions - With nested blocks open, does `commit` make every open block permanent and close them all, or does it only merge the innermost block into its parent? - What should `rollback` and `commit` do when no block is open? - Must `get` stay fast however deeply blocks are nested, or is a cost proportional to the nesting depth acceptable? ### What a Strong Answer Covers - A per-block record (an undo log or an overlay) and why it is enough to restore the state - Correct handling of keys that were absent before the block and keys unset inside it - Clearly stated nested-commit semantics, with an implementation that matches them - Time and space complexity of every operation, including `rollback` and `commit` - A walk through a nested example that shows the design is correct ### Follow-up Questions - Add `count(value)`, which returns how many keys currently hold `value`. How do you keep it O(1) through rollbacks? - How would you make committed data survive a process crash? - If several clients each had their own open transactions on a shared store, what isolation would you offer, and how?