How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview 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

Q: In-Memory Key-Value Database with Nested Transactions

This is a Coding & Algorithms interview question from xAI for Software Engineer roles. View the full question and solution on PracHub.

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.

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.

In-Memory Key-Value Database with Nested Transactions

In-Memory Key-Value Database with Nested Transactions

In-Memory Key-Value Database with Nested Transactions

Submit Your Answer to Earn 20XP

In-Memory Key-Value Database with Nested Transactions

In-Memory Key-Value Database with Nested Transactions

In-Memory Key-Value Database with Nested Transactions

Submit Your Answer to Earn 20XP