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.
Execute SET, GET, DELETE, BEGIN, COMMIT, and ROLLBACK commands with nested transaction semantics and return command outputs.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: (["SET a 10","GET a","BEGIN","SET a 20","GET a","ROLLBACK","GET a"],)
Expected Output: ['10', '20', '10']
Explanation: Rollback discards the nested value.
Input: (["BEGIN","SET a 1","BEGIN","DELETE a","GET a","COMMIT","GET a","ROLLBACK"],)
Expected Output: ['NULL', 'NULL']
Explanation: Nested commit propagates a deletion to the parent transaction, then rollback discards it.
Hints
- Represent transactions as a stack of change dictionaries.
- Use a tombstone marker so DELETE can hide lower-layer values.