How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Onsite rounds at xAI.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at xAI during technical interviews.

In-Memory Key-Value Database with Nested Transactions

Company: xAI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Onsite

# In-Memory Key-Value Database with Nested Transactions Implement an in-memory key-value database that processes a sequence of commands and supports **nested transactions**. Keys and values are strings. **Data commands** - `SET <key> <value>` — set `key` to `value`. - `GET <key>` — output the current value of `key`, or `NULL` if the key is not set. - `DELETE <key>` — remove `key` from the database. Deleting a key that is not set is a no-op. **Transaction commands** - `BEGIN` — open a new transaction block. Transaction blocks **nest**: a `BEGIN` inside an open transaction starts a child transaction layered on top of it. - `ROLLBACK` — undo all data commands issued in the **most recently opened** transaction block that is still open, and close that block. Outer transactions remain open. If no transaction is open, output `NO TRANSACTION`. - `COMMIT` — permanently apply the changes from **all** currently open transaction blocks to the database and close all of them. After a `COMMIT`, nothing that was done inside those blocks can be rolled back. If no transaction is open, output `NO TRANSACTION`. While a transaction is open, `GET` must see the effects of all data commands issued so far in every open transaction block (i.e., reads observe the innermost, most current state). Process the commands from the input in order and produce the output lines generated by `GET`, and by `ROLLBACK`/`COMMIT` when no transaction is open. Implement: ``` process(commands: List[str]) -> List[str] ``` where `commands` is the list of command lines and the result is the list of output lines in order. **Example** ``` Input: Output: SET a 10 GET a 10 BEGIN SET a 20 GET a 20 BEGIN DELETE a GET a NULL ROLLBACK GET a 20 COMMIT GET a 20 ROLLBACK NO TRANSACTION ``` **Constraints** - `1 <= number of commands <= 10^5` - Keys and values are non-empty strings of at most 32 characters with no whitespace - Transaction nesting depth can be up to `10^4` - `GET` and `SET` should run in O(1) average time regardless of how many transactions are open, and `ROLLBACK` should cost time proportional to the number of data commands made in the block being rolled back — a solution that copies the entire database on every `BEGIN` is not acceptable at this scale.

Quick Answer: This question evaluates understanding of in-memory data structures, transactional semantics (including nested transactions), and algorithmic complexity for implementing a key-value store that supports efficient GET/SET and rollback/commit operations.

Implement an in-memory key-value database that processes a sequence of commands and supports **nested transactions**. Keys and values are strings. **Data commands** - `SET <key> <value>` — set `key` to `value`. - `GET <key>` — output the current value of `key`, or `NULL` if the key is not set. - `DELETE <key>` — remove `key` from the database. Deleting a key that is not set is a no-op. **Transaction commands** - `BEGIN` — open a new transaction block. Transaction blocks **nest**: a `BEGIN` inside an open transaction starts a child transaction layered on top of it. - `ROLLBACK` — undo all data commands issued in the **most recently opened** transaction block that is still open, and close that block. Outer transactions remain open. If no transaction is open, output `NO TRANSACTION`. - `COMMIT` — permanently apply the changes from **all** currently open transaction blocks to the database and close all of them. After a `COMMIT`, nothing that was done inside those blocks can be rolled back. If no transaction is open, output `NO TRANSACTION`. While a transaction is open, `GET` must see the effects of all data commands issued so far in every open transaction block (reads observe the innermost, most current state). Process the commands in order and return the list of output lines produced by `GET`, and by `ROLLBACK`/`COMMIT` when no transaction is open. Implement `process(commands)` where `commands` is the list of command lines and the result is the list of output lines in order. **Example** ``` Input: Output: SET a 10 GET a 10 BEGIN SET a 20 GET a 20 BEGIN DELETE a GET a NULL ROLLBACK GET a 20 COMMIT GET a 20 ROLLBACK NO TRANSACTION ```

Constraints

1 <= number of commands <= 10^5
Keys and values are non-empty strings of at most 32 characters with no whitespace
Transaction nesting depth can be up to 10^4
GET and SET must run in O(1) average time regardless of open-transaction depth
ROLLBACK must cost time proportional to the number of data commands in the block being rolled back (copying the whole DB on BEGIN is not acceptable)

Examples

Input: (['SET a 10', 'GET a', 'BEGIN', 'SET a 20', 'GET a', 'BEGIN', 'DELETE a', 'GET a', 'ROLLBACK', 'GET a', 'COMMIT', 'GET a', 'ROLLBACK'],)

Expected Output: ['10', '20', 'NULL', '20', '20', 'NO TRANSACTION']

Explanation: The spec example. Inner block deletes 'a' then rolls back (restoring 20); COMMIT flattens the outer block so 'a'=20 is permanent; the trailing ROLLBACK has no open transaction, so 'NO TRANSACTION'.

Input: (['GET x'],)

Expected Output: ['NULL']

Explanation: Reading a key that was never set outputs NULL.

Input: (['COMMIT', 'ROLLBACK'],)

Expected Output: ['NO TRANSACTION', 'NO TRANSACTION']

Explanation: Both transaction-close commands run with no open transaction.

Input: (['SET a 1', 'BEGIN', 'SET a 2', 'BEGIN', 'SET a 3', 'ROLLBACK', 'GET a', 'ROLLBACK', 'GET a'],)

Expected Output: ['2', '1']

Explanation: Nested writes: rolling back the inner block restores 'a' to 2, and rolling back the outer block restores it to 1.

Input: (['BEGIN', 'SET k v', 'DELETE k', 'GET k', 'ROLLBACK', 'GET k'],)

Expected Output: ['NULL', 'NULL']

Explanation: Inside the block k is set then deleted (GET -> NULL). ROLLBACK undoes both, and since k did not exist before the block it stays unset (GET -> NULL).

Input: (['SET a 1', 'BEGIN', 'DELETE a', 'GET a', 'BEGIN', 'SET a 5', 'GET a', 'COMMIT', 'GET a'],)

Expected Output: ['NULL', '5', '5']

Explanation: COMMIT applies changes from all open blocks; after it, a=5 is permanent.

Input: ([],)

Expected Output: []

Explanation: No commands produce no output.

Input: (['BEGIN', 'BEGIN', 'BEGIN', 'SET a x', 'ROLLBACK', 'ROLLBACK', 'ROLLBACK', 'ROLLBACK', 'GET a'],)

Expected Output: ['NO TRANSACTION', 'NULL']

Explanation: Three nested blocks are each rolled back; the fourth ROLLBACK finds no open transaction (NO TRANSACTION), and 'a' — set only inside a rolled-back block — is unset.

Input: (['SET a NULL', 'GET a', 'DELETE a', 'GET a'],)

Expected Output: ['NULL', 'NULL']

Explanation: The value can literally be the string 'NULL'; the first GET returns the stored value 'NULL', and after DELETE the second GET returns 'NULL' because the key is absent.

Hints

Apply every SET/DELETE directly to a single dictionary, and give each open transaction block its own undo log recording the previous state of each key it touched. Then GET and SET stay O(1).
For each write inside a transaction, push (key, was_the_key_present, its_old_value) onto the current block's log. ROLLBACK replays that log in reverse, restoring or deleting each key.
COMMIT just discards all undo logs (the writes are already in the main dict). ROLLBACK/COMMIT with an empty transaction stack outputs 'NO TRANSACTION'. Remember a value can itself be the string 'NULL', so decide 'NULL' output by key presence, not by the value.

Quick Overview

This question evaluates understanding of in-memory data structures, transactional semantics (including nested transactions), and algorithmic complexity for implementing a key-value store that supports efficient GET/SET and rollback/commit operations.