Implement a Transactional Key-Value Store
Company: Grammarly
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Design an in-memory key-value store that supports transactions.
Required operations:
- `set(key, value)`: assign or overwrite the value for a key.
- `get(key)`: return the current value for the key, or `null` if it does not exist.
- `count(value)`: return how many keys are currently mapped to this value.
- `begin()`: start a new transaction.
- `commit()`: persist the changes from all currently open transactions.
- `rollback()`: undo the changes from the most recent open transaction.
Assumptions:
- Keys are unique strings.
- Values can be any hashable scalar.
- Multiple transactions may be nested.
- `count(value)` must reflect the currently visible state, including uncommitted changes inside the active transaction.
- If `rollback()` or `commit()` is called with no open transaction, define and handle the behavior clearly.
Discuss the data structures you would use and implement the core API.
Quick Answer: This question evaluates understanding of transactional state management, data structure design, and consistency/visibility semantics in an in-memory key-value store that supports nested transactions.