Implement a Transactional In-Memory Key-Value Store with Begin, Commit and Rollback

Implement a key-value store that supports transactions. Keys and values are strings, and the store lives in memory in a single process. Outside a transaction, every write takes effect immediately. A client can open a transaction, read and write inside it, and then either commit it, which makes its changes take effect, or roll it back, which discards them as if they had never been made. Implement these operations: - `get(key) -> str | None`: return the value currently visible for `key`, or `None` if it has none. - `set(key, value)`: write `value` under `key`. - `delete(key)`: remove `key`. - `begin()`: open a transaction. - `commit()`: make the open transaction's writes and deletes take effect. - `rollback()`: discard the open transaction's writes and deletes. Inside a transaction, `get` must see that transaction's own uncommitted writes and deletes. After a rollback, every key must read exactly as it did before the matching `begin`. ```hint What rollback must restore List what `rollback` has to put back for a key the transaction overwrote, for a key it created, and for a key it deleted. Your data structure must remember enough to handle all three. ``` ```hint Deletes inside a transaction If a transaction deletes a key that exists outside it, a later `get` inside the transaction must return `None`, yet a rollback must bring the value back. Think about how "deleted" is represented while the transaction is still open. ``` ### Constraints and Clarifications - Start with one client issuing operations one at a time. Concurrent clients are a follow-up. ### Clarifying Questions - Can transactions nest, that is, can `begin` be called while another transaction is open? If so, does committing an inner transaction make its changes permanent, or merge them into the enclosing transaction so that a rollback of the outer transaction still discards them? - What should `commit` or `rollback` do when no transaction is open: raise an error, or return a status? - Is there one client, or can several clients run transactions at the same time? If several, what isolation is expected, and what happens when two transactions write the same key? - Must committed data survive a process restart, or is an in-memory store enough? ### What a Strong Answer Covers - A representation of uncommitted state that lets `get` see the transaction's own writes and deletes, and lets `rollback` restore created, overwritten and deleted keys exactly - A stated policy for nested transactions, applied consistently to commit and rollback at every depth - The cost of every operation, with commit and rollback cost tied to what a transaction touched rather than to the size of the store - Defined behavior for `commit` or `rollback` without an open transaction - Test cases or a walkthrough covering read-your-own-writes, delete followed by rollback, and an inner transaction committed inside an outer one that is rolled back ### Follow-up Questions - Two clients each open a transaction and write the same key. How would you add isolation, and which conflicts would you detect at commit time? - How would you make committed transactions survive a crash without forcing a disk sync on every `set`? - A long-running reader needs a consistent view while writers keep committing. What would you change? - A single transaction writes the same few keys thousands of times. How do your design's memory use and commit cost behave?