Katkat
Back

Implement a Key-Value Store with Nested Transactions

LyftSoftware Engineer · Onsite
EasySoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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.

Example

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?

Hints

Hint 1

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 2

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.