# In-Memory Key-Value Store with Nested Transactions Implement an in-memory key-value store that supports basic reads and writes **and** transactions that can be committed or rolled back, including **nested** transactions. Both keys and values are strings. The store starts empty. ## Operations to implement Implement a class (suggested name `KeyValueStore`) exposing the following methods. ### Basic operations - `set(key, value)` — Associate `key` with `value`. If `key` already has a value, overwrite it. Returns nothing. - `get(key)` — Return the current value associated with `key`, taking any open transactions into account. If `key` does not currently have a value, return `null` (use your language's null/None equivalent). - `delete(key)` — Remove `key` and its value from the store. After a delete, `get(key)` returns `null` until the key is set again. Deleting a key that does not exist is a no-op. Returns nothing. ### Transaction operations - `begin()` — Open a new transaction. Transactions may be **nested**: calling `begin()` again while one or more transactions are already open opens an additional, inner transaction. While at least one transaction is open, every `set` and `delete` is buffered in the **innermost** open transaction and is not yet visible to any future `commit` of an outer scope until this transaction is committed. Returns nothing. - `commit()` — Commit the **innermost** open transaction. Its buffered writes and deletes are merged into the enclosing scope: the parent transaction if one exists, otherwise the base (committed) store. Return `true` if a transaction was open and committed; return `false` if there was no open transaction (in which case the store is left unchanged). - `rollback()` — Discard the **innermost** open transaction, throwing away all of its buffered writes and deletes so they never take effect. Return `true` if a transaction was open and rolled back; return `false` if there was no open transaction (in which case the store is left unchanged). ## Read semantics `get(key)` must reflect the combined view of the base store plus all currently open transactions, where inner transactions take precedence over outer ones: 1. Search the open transactions from innermost to outermost. If one of them records a write or a delete for `key`, return that record's value (`null` for a recorded delete). 2. If no open transaction records `key`, return the value from the base (committed) store, or `null` if it has none. A `set` inside a transaction shadows any value the key had in an outer scope, and a `delete` inside a transaction shadows it with "absent" (so `get` returns `null`) until that transaction is committed or rolled back. ## Examples The following call sequence shows the expected return values. Calls that return nothing are shown without a result. ``` set("a", "1") get("a") -> "1" begin() # open transaction T1 set("a", "2") get("a") -> "2" # T1's write shadows the base value begin() # open nested transaction T2 delete("a") get("a") -> null # T2's delete shadows T1's value rollback() -> true # discard T2 (the delete is thrown away) get("a") -> "2" # T1's value is visible again commit() -> true # merge T1 into the base store get("a") -> "2" # change is now permanent rollback() -> false # no transaction is open get("a") -> "2" # unchanged ``` Another example showing that a rolled-back outer transaction discards everything it contained: ``` set("x", "10") begin() set("x", "20") set("y", "30") get("x") -> "20" get("y") -> "30" rollback() -> true get("x") -> "10" # the buffered "20" is gone get("y") -> null # "y" was only ever set inside the rolled-back txn ``` ## Constraints & Assumptions - Keys and values are non-empty strings. You may assume at most $10^5$ total operations across a single run. - Transactions can be nested to a depth of at least several hundred; your solution should not assume a fixed small depth. - `commit` and `rollback` always act on the single innermost open transaction. There is no operation that commits or rolls back all open transactions at once. - All operations should run in time proportional to the work they touch; in particular `get`, `set`, and `delete` should be efficient (roughly $O(d)$ in the number of currently open transactions $d$, or better), and `commit`/`rollback` should touch only the keys buffered in the innermost transaction. - The store is single-threaded; you do not need to handle concurrent access.