Implement a Key-Value Store with Nested Transactions
Company: Lyft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Onsite
## Problem
Implement an in-memory key-value store with nested transactions. Values are strings. The store supports lookup, assignment, deletion, counting keys by value, beginning a transaction, rolling back the innermost transaction, and committing the innermost transaction into its parent or into permanent state.
Implement `runTransactionalStore(operations)` and return one result per operation.
### Operation Contract
- `["set", key, value]`: assign the value and return `null`.
- `["get", key]`: return the visible value or `null`.
- `["unset", key]`: delete the visible key and return `null`.
- `["count", value]`: return the number of visible keys equal to the value.
- `["begin"]`: create a nested transaction and return `null`.
- `["rollback"]`: discard the innermost transaction and return `true`, or `false` when none is open.
- `["commit"]`: merge the innermost transaction into its parent; if it is the outermost transaction, make it permanent. Return `true`, or `false` when none is open.
### Constraints & Assumptions
- At most `200,000` operations are supplied.
- Keys and values are nonempty strings.
- Transaction depth may reach `100,000`.
- Each operation should be close to `O(1)` expected time; copying the full database at every `begin` is not acceptable.
### Clarifying Questions to Ask
- Does an inner commit become permanent immediately? No; it becomes part of its parent and can still be removed by rolling back that parent.
- Does `unset` of a missing key fail? No, it is a no-op.
- Does count reflect uncommitted visible changes? Yes.
- Is concurrent access required? No.
```hint Log the first old value per frame
A transaction frame needs enough information to reverse each key to the state visible when that frame first changed it.
```
```hint Keep counts in sync
Every visible value change decrements the old value's count and increments the new value's count. Rollback applies inverse changes through the same helper.
```
### Example
```text
operations = [
["set", "a", "x"], ["begin"], ["set", "a", "y"],
["begin"], ["unset", "a"], ["rollback"], ["get", "a"],
["commit"], ["get", "a"]
]
output = [null, null, null, null, null, true, "y", true, "y"]
```
### Evaluation Focus
- Preserves nested commit and rollback semantics.
- Records absence distinctly from a stored value.
- Maintains value counts under overwrite, unset, commit, and rollback.
- Avoids whole-store copies at transaction boundaries.
### Extensions to Discuss
1. How would snapshots or multi-version concurrency change the design?
2. How can an inner commit merge undo information without losing the parent's original state?
3. What persistence log would support crash recovery?
Overview: Implement an in-memory string key-value store with lookup, assignment, deletion, value counts, and deeply nested transactions. Define visibility plus exact begin, rollback, and inner or outer commit behavior without copying the entire database per transaction.
Community answers
Answer by landiaokafeiyan
def runTransactionalStore(operations):
# 全局可见状态
store = {} # key -> value
value_counts = {} # value -> count of keys having this value
# 事务栈：每个元素是一个 dict，记录该层事务中被修改 key 的“进入该事务前的初始状态”
# undo_stack[i] = { key: old_value_before_this_transaction }
# 若 key 在进入该事务前不存在，则 old_value 为 None
undo_stack = []
def _update_count(old_val, new_val):
if old_val is not None:
value_counts[old_val] -= 1
if value_counts[old_val] == 0:
del value_counts[old_val]
if new_val is not None:
value_counts[new_val] = value_counts.get(new_val, 0) + 1
def _apply_set(key, new_val):
old_val = store.get(key, None)
if old_val == new_val:
return # 值没有变化，无需做任何变更或记录日志
# 如果处于事务中，且当前事务帧还未记录过该 key 的历史值，则记录之
if undo_stack and key not in undo_stack[-1]:
undo_stack[-1][key] = old_val
store[key] = new_val
_update_count(old_val, new_val)
def _apply_unset(key):
if key not in store:
return # key 不存在，unset 是 no-op
old_val = store[key]
if undo_stack and key not in undo_stack[-1]:
undo_stack[-1][key] = old_val
del store[key]
_update_count(old_val, None)
results = []
for op in operations:
op_type = op[0]
if op_type == "set":
_, k, v = op
_apply_set(k, v)
results.append(None)
elif op_type == "get":
_, k = op
results.append(store.get(k, None))
elif op_type == "unset":
_, k = op
_apply_unset(k)
results.append(None)
elif op_type == "count":
_, v = op
results.append(value_counts.get(v, 0))
elif op_type == "begin":
undo_stack.append({})
results.append(None)
elif op_type == "rollback":
if not undo_stack:
results.append(False)
else:
top
Answer by landiaokafeiyan
def runTransactionalStore(operations):
ABSENT = object()
# Current visible state.
store = {}
# value -> number of keys currently having this value.
counts = {}
# Stack of transaction frames.
# Each frame stores key -> old value/state.
transactions = []
def increment(value):
counts[value] = counts.get(value, 0) + 1
def decrement(value):
counts[value] -= 1
if counts[value] == 0:
del counts[value]
def current_value(key):
return store.get(key, ABSENT)
def log_old_value(key):
"""
Record the first old value of key in the
current transaction frame.
"""
frame = transactions[-1]
if key not in frame:
frame[key] = current_value(key)
def set_value(key, value):
old = current_value(key)
if old == value:
return
if transactions:
log_old_value(key)
if old is not ABSENT:
decrement(old)
store[key] = value
increment(value)
def unset_value(key):
old = current_value(key)
if old is ABSENT:
return
if transactions:
log_old_value(key)
decrement(old)
del store[key]
def rollback():
if not transactions:
return False
frame = transactions.pop()
for key, old in frame.items():
current = current_value(key)
# Remove current contribution.
if current is not ABSENT:
decrement(current)
# Restore old state.
if old is ABSENT:
store.pop(key, None)
else:
store[key] = old
increment(old)
return True
def commit():
if not transactions:
return False
frame = transactions.pop()
# If there is a parent transaction, merge only
# the keys that the parent has not logged yet.
if transactions:
parent = transactions[-1]
for key, old