Practice/Lyft/Design an in-memory database to handle transactions

Design an in-memory database to handle transactions

CodingMust

Problem

Design and implement an in-memory key-value database that supports ACID-like transactions. Your database should allow storing integer values associated with string keys, and provide transaction capabilities including begin, commit, and rollback operations.

The database must handle nested transactions correctly, where rolling back an inner transaction should restore state to the beginning of that transaction, while committing should merge changes into the parent transaction.

Requirements

1. Implement set(key, value) to store an integer value for a given key
2. Implement get(key) to retrieve the value for a key, returning None if the key doesn't exist
3. Implement delete(key) to remove a key-value pair from the database
4. Implement begin() to start a new transaction
5. Implement commit() to persist all changes made in the current transaction
6. Implement rollback() to discard all changes made in the current transaction
7. Support nested transactions where each level maintains its own change set
8. All operations within a transaction should be isolated from committed state until commit is called

Constraints

• Keys are strings with length 1 to 50 characters
• Values are integers in the range [-10^9, 10^9]
• The database should support up to 10,000 key-value pairs
• Up to 100 nested transaction levels should be supported
• Each operation should run in O(1) average time complexity
• Memory usage should be proportional to the number of modified keys per transaction

Examples

Example 1: Basic Operations

db = TransactionalDB() db.set("user_id", 42) db.set("score", 100) print(db.get("user_id")) # Output: 42 print(db.get("score")) # Output: 100 print(db.get("missing")) # Output: None

Example 2: Simple Transaction

db = TransactionalDB() db.set("balance", 1000) db.begin() db.set("balance", 1500) print(db.get("balance")) # Output: 1500 (sees uncommitted change) db.commit() print(db.get("balance")) # Output: 1500 (change persisted)

Example 3: Transaction Rollback

db = TransactionalDB() db.set("lives", 3) db.begin() db.set("lives", 2) db.rollback() print(db.get("lives")) # Output: 3 (change discarded)

Example 4: Nested Transactions

db = TransactionalDB() db.set("level", 1) db.begin() # Transaction 1 db.set("level", 2) db.begin() # Transaction 2 (nested) db.set("level", 3) db.commit() # Commit Transaction 2 print(db.get("level")) # Output: 3 db.commit() # Commit Transaction 1 print(db.get("level")) # Output: 3 (all changes persisted)