In-Memory Key-Value Database with Nested Transactions

Problem Description

Design an in-memory key-value database that supports nested transactions. Changes made inside an active transaction should remain isolated until committed, and rolling back a transaction should restore the state prior to that transaction's initiation.

Transactions can be nested arbitrarily deep:

• When a nested transaction commits, its modifications are merged into the enclosing (parent) transaction scope.
• When the outermost transaction commits, its modifications are permanently applied to the base database.
• When any transaction is rolled back, all changes made within that transaction's scope are discarded, returning the database to the state of the parent scope.

Class Interface

Implement the TransactionalKV class:

class TransactionalKV:
    def __init__(self):
        pass

    def set(self, key: str, value: str) -> None:
        """Sets the key to value in the current context."""
        pass

    def get(self, key: str) -> Optional[str]:
        """Returns the value associated with key, or None if it does not exist."""
        pass

    def delete(self, key: str) -> bool:
        """Deletes the key in the current context. Returns True if key existed, False otherwise."""
        pass

    def begin(self) -> None:
        """Starts a new transaction scope."""
        pass

    def commit(self) -> bool:
        """Commits the current transaction. Returns False if no transaction is active, True otherwise."""
        pass

    def rollback(self) -> bool:
        """Rolls back the current transaction. Returns False if no transaction is active, True otherwise."""
        pass

Examples

Example 1

db = TransactionalKV()
db.set("a", "10")
db.begin()
db.set("a", "20")
db.get("a")      # returns "20"
db.rollback()    # returns True
db.get("a")      # returns "10"

Example 2: Nested Transactions

db = TransactionalKV()
db.set("a", "1")
db.begin()         # Level 1
db.set("a", "2")
db.begin()         # Level 2
db.set("b", "3")
db.delete("a")
db.get("a")        # returns None
db.rollback()      # Rolls back Level 2
db.get("a")        # returns "2"
db.get("b")        # returns None
db.commit()        # Commits Level 1 to base
db.get("a")        # returns "2"

Constraints & Edge Cases

• Keys and values are non-empty strings.
• Calling commit() or rollback() with no active transaction should return False without raising an error.
• A key deleted inside an inner transaction must not fall back to revealing a value from an outer scope.
• At most 10^5 operations will be called.