Design an in-memory database to handle transactions
Asked at:
Lyft
Coinbase
Uber
DESCRIPTION
Design an in-memory database that supports basic key-value operations (get, set, unset) with transaction management. Transactions allow grouping operations into blocks that can be committed (persisted) or aborted (rolled back). For example, changes made within a begin()/commit() block should only become permanent after commit() is called.
Input:
set('x', 10); begin(); set('x', 20); get('x'); abort(); get('x')
Output:
Returns 20 during transaction, then 10 after abort
Explanation: Transaction changes are visible within the block but discarded on abort
Constraints:
- Operations must be O(1) average time complexity
- Support nested transactions (transaction within transaction)
- Memory usage should scale with active transactions
- Abort must restore all previous values correctly
Understanding the Problem
The core challenge is maintaining transaction isolation while preserving performance. Each transaction needs its own view of data changes without affecting the committed state. When transactions nest, inner transactions must be able to roll back independently. The system must track which values belong to which transaction level and efficiently merge or discard changes based on commit/abort decisions.
Building Intuition
A naive approach copies the entire database at each begin(), making rollback simple but memory-intensive with O(n) space per transaction. A better approach uses a transaction stack where each level stores only the changes (deltas) made within that transaction, achieving O(k) space where k is the number of modified keys. For example, if only 3 keys change in a transaction, we store just those 3 changes rather than copying all data.
Transactional databases are fundamental to data consistency in systems like banking, inventory management, and distributed applications. The ability to group operations and roll back on errors prevents partial updates that could corrupt data. Efficient transaction handling enables high-throughput systems to maintain ACID properties without excessive memory overhead.
Common Pitfalls
Implementation
Core Data Storage and Basic Operations
Implement the main storage using a dict for O(1) key-value access and handle get, set, and unset operations. The get method must check if a key exists and raise an error if not found. The set operation stores values (including None) while unset removes keys entirely. For example, set('x', None) creates a key with null value, different from unset('x') which removes the key.
class InMemoryDB:def __init__(self):self.store = {}def get(self, key: str):if key not in self.store:raise KeyError(f"Key '{key}' not found")return self.store[key]def set(self, key: str, val):self.store[key] = valdef unset(self, key: str):if key in self.store:del self.store[key]
Transaction Stack Management
Use a stack of dictionaries to track transaction levels, where each level stores modifications made during that transaction. On begin(), push a new empty dict onto the stack. Each operation checks if we're in a transaction (stack not empty) and records changes in the top-level dict before modifying main storage. Store both the new value and previous value to enable rollback. For example, changing x from 10 to 20 stores {x: (20, 10)} in the transaction dict.
class TransactionManager:def __init__(self):self.data = {}self.transaction_stack = []def begin(self):self.transaction_stack.append({})def _in_transaction(self):return len(self.transaction_stack) > 0def _record_change(self, key, new_value):if self._in_transaction():current_tx = self.transaction_stack[-1]if key not in current_tx:prev_value = self.data.get(key, None)current_tx[key] = (new_value, prev_value)
Commit and Abort Logic
For abort(), pop the top transaction dict and restore all previous values by iterating through recorded changes. Handle three cases: restoring old values, re-deleting keys that were created, and re-creating keys that were deleted. For commit(), merge the top transaction's changes into the parent transaction (if nested) or discard the tracking dict (if top-level), since changes are already in main storage. For example, committing a nested transaction moves its change log up one level rather than applying to main storage.
def abort(self):if not self.transactions:raise Exception("No transaction to abort")changes = self.transactions.pop()for key, old_val in changes.items():if old_val is None:del self.store[key]else:self.store[key] = old_valdef commit(self):if not self.transactions:raise Exception("No transaction to commit")changes = self.transactions.pop()if self.transactions:self.transactions[-1].update(changes)# else: changes already in main storage
What We've Learned
- Pattern: Transaction stack with delta tracking enables O(1) operations while supporting nested transactions and efficient rollback
- Use Case: Apply this pattern to undo/redo systems, database isolation levels, and any system requiring atomic operation groups
- Optimization: Store only modified keys per transaction rather than copying entire state, reducing memory from O(n*t) to O(k*t) where k << n
- Design Principle: Separate committed state from transaction state to maintain consistency and enable concurrent transaction views
Problems to Practice
medium
Both problems involve designing and implementing data structure methods with specific operations. The Trie implementation requires managing insert, search, and prefix operations similar to how the database needs get, set, unset operations with proper state management.
medium
This problem uses stacks to manage nested state and restore previous contexts, which directly parallels how transaction blocks need to maintain and restore database state. The pattern of pushing state, processing operations, and popping to restore is identical to transaction management.
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Late October, 2025
Lyft
Mid-level
Late October, 2025
Lyft
Senior
Few functions of In-Memory Database
Late September, 2025
Uber
Staff
# get(key: str) gets the value associated with key, or raise error if key doesn’t exist # set(key: str, val: obj) sets the value associated with key. Values can be null # unset(key: str) removes the value associated with the key # begin(): start a new transaction block. # abort(): blow away the changes from the transaction block # commit(): persist the changes
Comments
Hello Interview Premium
Your account is free and you can post anonymously if you choose.