Implement an In-Memory Key-Value Store With BEGIN, COMMIT and ROLLBACK
Company: Applied Intuition
Role: Software Engineer
Category: Software Engineering Fundamentals
Difficulty: medium
Interview Round: Onsite
Implement an in-memory key-value store that supports these commands:
- `SET key value`: assign the value to the key, overwriting any existing value.
- `GET key`: return the key's current value, or `NULL` if the key does not exist.
- `BEGIN`: start a transaction.
- `COMMIT`: permanently save the transaction's changes.
- `ROLLBACK`: discard the transaction's changes and restore the state from before `BEGIN`.
Write the store and a small driver that executes a list of commands and returns the output of every `GET`. This session must produce the outputs shown:
```text
SET x 10
GET x -> 10
BEGIN
SET x 20
SET y 30
GET x -> 20
GET y -> 30
ROLLBACK
GET x -> 10
GET y -> NULL
BEGIN
SET x 50
COMMIT
GET x -> 50
```
```hint What a rollback needs
Ask what is the least information you must keep while a transaction runs to restore every key exactly, including a key that did not exist before the transaction.
```
```hint Reads inside a transaction
Make sure a GET inside an open transaction sees that transaction's own writes.
```
### Clarifying Questions
- Can transactions be nested, with a BEGIN inside an open transaction? If so, does COMMIT save only the innermost transaction or all open ones, and does ROLLBACK undo only the innermost?
- What should COMMIT or ROLLBACK do when no transaction is open?
- Are values always integers, as in the example, or arbitrary strings?
- Is the store used by a single thread?
### What a Strong Answer Covers
- Correct outputs for the session, including the key that exists only inside the rolled-back transaction
- A rollback mechanism, such as an undo log or a per-transaction write set, with its time and memory cost per command
- Defined behavior for COMMIT and ROLLBACK without a transaction, and for nested transactions
- Command parsing kept separate from the store, and tests for the edge cases
### Follow-up Questions
- Add `DELETE key`. How does a delete inside a transaction interact with ROLLBACK?
- Add `COUNT value`, returning how many keys currently hold that value, in constant time. What must change?
- How would you make committed data survive a process crash?
- Several clients use the store at the same time, each with its own transaction. What isolation would you offer, and how?
Overview: A coding exercise to implement an in-memory key-value store with SET, GET, BEGIN, COMMIT and ROLLBACK, where a rollback restores the state from before the transaction began. It tests the choice of an undo log or write set, handling of keys created inside a transaction, nesting and other edge cases.
Read the full Applied Intuition Software Engineer interview experience this question came from