Implement Nested Transactional Key-Value Store
Company: Applied
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
Implement an in-memory key-value store that processes a batch of commands, one command per line. The store must support nested transactions.
Supported commands:
- `SET key value`: Set `key` to `value` in the current context.
- `GET key`: Return the current value for `key`, or `NULL` if the key does not exist.
- `DELETE key`: Remove `key` from the current context.
- `BEGIN`: Start a new transaction. Transactions may be nested.
- `COMMIT`: Commit the current transaction into its parent transaction. If there is no active transaction, return an error such as `NO TRANSACTION`.
- `ROLLBACK`: Discard all changes made in the current transaction. If there is no active transaction, return an error such as `NO TRANSACTION`.
Input is provided as a single string or list containing many command lines. Your program should parse and execute the commands in order, collecting the output from commands that produce output, such as `GET`, invalid `COMMIT`, and invalid `ROLLBACK`.
Transaction semantics:
- Changes inside a transaction should be visible to later commands inside that transaction and any nested transactions.
- `ROLLBACK` only discards changes made in the current transaction level.
- `COMMIT` merges the current transaction's changes into the immediately enclosing transaction if one exists; otherwise, it applies them to the base store.
- Deleted keys must remain deleted after commit unless an outer context changes them again.
Example:
```text
SET a 1
GET a
BEGIN
SET a 2
GET a
BEGIN
DELETE a
GET a
ROLLBACK
GET a
COMMIT
GET a
```
Expected output:
```text
1
2
NULL
2
2
```
Quick Answer: This question evaluates a candidate's ability to implement an in-memory key-value store with nested transaction semantics, focusing on state management, command parsing, and correct scoping for SET/GET/DELETE/BEGIN/COMMIT/ROLLBACK operations.