Katkat
Back

In-Memory Key-Value Database with Nested Transactions

xAISoftware Engineer · Onsite
EasySoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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.