Problem Brief

KV Store with Nested Transactions

FULLTIMEPHONE SCREEN

Implement an in-memory key-value store that supports nested transactions. Commands are executed in order, one command per line.

Supported commands are:

SET <key> <value>
GET <key>
DELETE <key>
BEGIN
ROLLBACK
COMMIT

GET returns the current value of a key, or NULL if it does not exist. ROLLBACK and COMMIT print NO TRANSACTION when there is no active transaction.

Return the lines that would be printed while processing the command batch.

Function Description

Complete the function runNestedTransactions in the editor below.

runNestedTransactions has the following parameter:

String[] commands: the command batch, one command per element

Returns

String[]: the output lines produced by the batch in order.

1Example 1

Input

commands = ["SET a 10", "GET a"]

Output

["10"]

Explanation

After setting a to 10, GET a prints that value.

2Example 2

Input

commands = ["SET a 10", "BEGIN", "SET a 20", "BEGIN", "DELETE a", "GET a", "ROLLBACK", "GET a", "COMMIT", "GET a"]

Output

["NULL", "20", "20"]

Explanation

The inner transaction deletes a, so the first GET prints NULL. After rolling back the inner transaction, a becomes 20 again. Committing keeps that value permanent.

Constraints

Limits and guarantees your solution can rely on.

1 <= commands.length <= 200000
Keys and values are non-empty strings without spaces.
Transactions may be nested arbitrarily deeply.
A near-linear total runtime is expected for large command batches.