Key-Value Store with Transactions

Design and implement an in-memory key-value database that supports nested transactions. Your database should allow storing integer values associated with string keys and expose the following operations:

• set(key, value) – set the given key to the given value.
• get(key) – return the current value for the key, or null if the key has no value.
• delete(key) – remove the key from the store.
• begin() – start a new transaction. Changes made after this call are isolated until the transaction is committed or rolled back. Transactions may be nested; each begin() creates a new deeper level.
• commit() – persist all changes made in the current transaction to its parent. If there is no active transaction, raise an error. On success, the current transaction is closed and its parent becomes active again.
• rollback() – discard all changes made in the current transaction. If there is no active transaction, raise an error. On success, the current transaction is closed and its parent becomes active again.

Reads (get) must return the most-recently-written value from the current transaction or any ancestor. Writes (set/delete) inside a transaction must not be visible to any outer scope until committed. Deletions must shadow keys that exist in an outer scope so that get returns null until the deletion is committed or rolled back. All operations must run in O(1) average time.