Design transactional in-memory key-value store

Problem

Design and implement an in-memory key–value store that supports basic operations plus transactions.

Core API

Implement the following operations:

• get(key) -> value | null Return the current value for key, or null/None if it does not exist.
• put(key, value) Set key to value.
• delete(key) Remove key if it exists.

Follow-up 1: Transactions (must support nested)

Add transactional operations:

• begin() — starts a new transaction scope (transactions may be nested).
• commit() -> bool — commits the current transaction.
• Returns false (or throws) if there is no active transaction.
• rollback() -> bool — rolls back the current transaction.
• Returns false (or throws) if there is no active transaction.

After commit, changes in the committed transaction become visible in the parent transaction (or globally if committing the outermost transaction). After rollback, all changes made since the last begin() are undone.

Complexity requirement: Each operation should run in O(1) time on average (constant-time hash operations allowed). You may assume keys and values fit in memory.

Follow-up 2: Concurrency

Extend your design to support multi-threaded access:

• Multiple threads may call get/put/delete/begin/commit/rollback concurrently.
• Describe the thread-safety guarantees you provide (e.g., linearizability vs. weaker consistency) and what synchronization approach you would use.

Notes

• Clarify how delete interacts with transactions (e.g., deleting a key inside a transaction should be reversible by rollback).
• Be prepared to discuss edge cases such as committing/rolling back with no active transaction and nested transactions.