Hey r/DarkInterview — sharing a free Rippling coding question from https://darkinterview.com .

---

In-Memory Key-Value Store with Transactions

Design and implement an in-memory key-value datastore that supports basic CRUD operations and transactions. This is a classic interview question that tests your understanding of data structures, state management, and transaction semantics.

---

Part 1: Basic Key-Value Store

Implement an in-memory key-value datastore with set, get, and delete:

python db = Database() db.set("key1", "val1") print(db.get("key1")) # Output: val1 print(db.get("key2")) # Output: None db.delete("key1") print(db.get("key1")) # Output: None

This part is straightforward — a dictionary (hash map) gives O(1) for all operations. The real challenge starts in Part 2.

---

Part 2: Single Transaction Support

Add begin(), commit(), and rollback() methods with the following semantics:

• begin(): Start a new transaction context
• commit(): Persist all changes made in the transaction to the global store
• rollback(): Discard all changes made in the transaction
• Reads inside a transaction should see uncommitted changes made within that transaction

Example: Commit

`python db = Database() db.set("key0", "val0")

db.begin() print(db.get("key0")) # val0 (visible from global store) db.set("key1", "val1") print(db.get("key1")) # val1 (uncommitted, but visible in transaction) db.commit()

print(db.get("key1")) # val1 (persisted after commit) `

Example: Rollback

`python db = Database() db.begin() db.set("key2", "val2") print(db.get("key2")) # val2 (visible in transaction) db.rollback()

print(db.get("key2")) # None (changes discarded) `

Key design decision: Don't copy the entire store on begin(). Instead, maintain a separate "pending changes" map and check it first on reads. For deletes, use a sentinel value to distinguish "deleted in transaction" from "doesn't exist."

---

Part 3: Nested Transactions

Now support nested transactions. Multiple transactions can be active at once, and operations affect the innermost (most recent) transaction.

• A child transaction inherits visible state from its parent
• When a child commits, its changes merge into the parent (not global store)
• When a child rollbacks, its changes are discarded, parent is unaffected
• Only when the outermost transaction commits do changes persist to global store

Example: Nested Commit

`python db = Database() db.begin() # Transaction 1 (parent) db.set("key1", "val1")

db.begin() # Transaction 2 (child) print(db.get("key1")) # val1 (inherited from parent) db.set("key1", "val1_child") db.commit() # Merges into parent

print(db.get("key1")) # val1_child (from committed child) db.commit() # Persists to global store print(db.get("key1")) # val1_child `

Example: Parent Rollback Discards Everything

`python db = Database() db.begin() # Parent db.set("key1", "val1")

db.begin() # Child db.set("key2", "val2") db.commit() # Merges into parent

db.rollback() # Rollback parent -> discards ALL changes print(db.get("key1")) # None print(db.get("key2")) # None (child commit was only to parent) `

Hint: Use a stack of transaction layers. Writes go to the top. Reads search top-down. Commit pops and merges into the layer below. Rollback pops and discards.

---

Edge Cases to Consider

1. Commit/Rollback without Begin — should raise an error
2. Deleting a non-existent key — return False, no error
3. Re-setting a deleted key — set → delete → set should work correctly
4. Deeply nested transactions — 1000+ levels should be handled gracefully
5. Empty transactions — begin() then immediately commit() is valid

---

Follow-up Discussion Topics

The interviewer may ask you to extend the design verbally:

1. Thread safety — how would you make this concurrent? Global lock vs. read-write lock vs. per-transaction isolation?
2. Persistence — how would you add durability? Write-ahead logging (WAL)? Snapshots?
3. Memory limits — what if the dataset is larger than memory? LRU eviction? Disk-backed storage?
4. Transaction timeout — what if a transaction runs forever? How do you detect and abort long-running transactions?

---

Full question + Python solution with transaction stack implementation: https://darkinterview.com/collections/r8p2l5g7/questions/601e6b2b-1b57-46d5-87d3-18576339a0e4