Implement command-driven in-memory key-value database
Company: Lyft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Quick Answer: This question evaluates a candidate's ability to design efficient in-memory data structures and implement transactional semantics for operations like SET/GET/DELETE/COUNT, including handling nested transactions, rollbacks, and commits.
Constraints
- 0 <= len(commands) <= 100000
- Keys and values are non-empty ASCII strings without whitespace
- The total number of key mutations across all commands is at most 100000
- Operations should be O(1) average/amortized, with ROLLBACK proportional to the number of reverted changes
Examples
Input: ([],)
Expected Output: []
Explanation: No commands produce no output.
Input: (["SET a 10", "SET b 10", "COUNT 10", "GET a", "DELETE a", "GET a", "COUNT 10", "DELETE missing", "COUNT 10"],)
Expected Output: ["2", "10", "NULL", "1", "1"]
Explanation: Two keys initially map to 10. After deleting a, GET a is NULL and only b still maps to 10. Deleting a missing key has no effect.
Input: (["SET a 1", "BEGIN", "SET a 2", "BEGIN", "SET b 2", "COUNT 2", "ROLLBACK", "COUNT 2", "GET b", "ROLLBACK", "GET a"],)
Expected Output: ["2", "1", "NULL", "1"]
Explanation: The inner transaction adds b=2, then it is rolled back. The outer transaction changes a from 1 to 2, then it is rolled back, restoring a=1.
Input: (["BEGIN", "SET a 5", "BEGIN", "SET a 6", "SET b 6", "COMMIT", "GET a", "COUNT 6", "ROLLBACK", "GET b", "COMMIT"],)
Expected Output: ["6", "2", "NO TRANSACTION", "6", "NO TRANSACTION"]
Explanation: COMMIT closes all open transactions and keeps a=6 and b=6. Later ROLLBACK and COMMIT have no open transaction, so both output NO TRANSACTION.
Input: (["DELETE ghost", "BEGIN", "DELETE ghost", "SET ghost x", "DELETE ghost", "ROLLBACK", "GET ghost", "COUNT x"],)
Expected Output: ["NULL", "0"]
Explanation: Deleting a non-existent key has no effect. Inside the transaction ghost is set then deleted; rolling back restores the pre-transaction missing state.
Input: (["SET a 1", "SET a 1", "COUNT 1", "BEGIN", "SET a 2", "SET a 2", "COUNT 1", "COUNT 2", "ROLLBACK", "GET a", "COUNT 2"],)
Expected Output: ["1", "0", "1", "1", "0"]
Explanation: Setting a key to its current value does not change counts. Rolling back restores a from 2 to 1.
Solution
def solution(commands):
db = {}
value_counts = {}
transactions = []
output = []
def add_count(value, delta):
new_count = value_counts.get(value, 0) + delta
if new_count == 0:
value_counts.pop(value, None)
else:
value_counts[value] = new_count
for raw in commands:
parts = raw.strip().split()
command = parts[0]
if command == 'SET':
key, value = parts[1], parts[2]
old_exists = key in db
old_value = db.get(key)
if old_exists and old_value == value:
continue
if transactions:
transactions[-1].append((key, old_exists, old_value))
if old_exists:
add_count(old_value, -1)
db[key] = value
add_count(value, 1)
elif command == 'GET':
key = parts[1]
output.append(db.get(key, 'NULL'))
elif command == 'DELETE':
key = parts[1]
if key in db:
old_value = db[key]
if transactions:
transactions[-1].append((key, True, old_value))
del db[key]
add_count(old_value, -1)
elif command == 'COUNT':
value = parts[1]
output.append(str(value_counts.get(value, 0)))
elif command == 'BEGIN':
transactions.append([])
elif command == 'ROLLBACK':
if not transactions:
output.append('NO TRANSACTION')
else:
log = transactions.pop()
for key, old_exists, old_value in reversed(log):
if key in db:
current_value = db[key]
del db[key]
add_count(current_value, -1)
if old_exists:
db[key] = old_value
add_count(old_value, 1)
elif command == 'COMMIT':
if not transactions:
output.append('NO TRANSACTION')
else:
transactions.clear()
return outputTime complexity: O(n) total for n commands, amortized O(1) per command; each logged mutation is rolled back at most once.. Space complexity: O(k + v + t), where k is the number of current keys, v is the number of distinct current values, and t is the number of mutations stored in open transaction logs..
Hints
- Keep one hash map from key to value, and another hash map from value to the number of keys currently mapped to that value.
- For transactions, apply changes immediately but push the previous state of each changed key onto the current transaction's undo log. Roll back by replaying that log in reverse.