How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Grammarly.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Grammarly during technical interviews.

Implement a Transactional Key-Value Store | Grammarly Coding Question

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.

Process a sequence of operations on an in-memory key-value store that supports nested transactions. Implement solution(operations), where operations is a list of command tuples. Return a list containing the result of every output-producing command in the order they appear. The commands are: set(key, value) to assign or overwrite a key, get(key) to read the current visible value or None if the key does not exist, count(value) to count how many keys are currently mapped to that value, begin() to open a new transaction, rollback() to undo only the most recent open transaction, and commit() to persist the changes from all currently open transactions and close them all. If rollback() or commit() is called when no transaction is open, return False for that command and leave the store unchanged. This problem tests your choice of data structures: you need fast lookups, fast value counts, and efficient undo behavior for nested transactions.

Constraints

0 <= len(operations) <= 2 * 10^5
Keys are strings; values are hashable scalars and will not be None

Examples

Input: [('set', 'a', 10), ('set', 'b', 10), ('count', 10), ('begin',), ('set', 'a', 20), ('get', 'a'), ('count', 10), ('count', 20), ('begin',), ('set', 'b', 20), ('count', 20), ('rollback',), ('get', 'b'), ('count', 20), ('commit',), ('get', 'a'), ('get', 'b')]

Expected Output: [2, 20, 1, 1, 2, True, 10, 1, True, 20, 10]

Explanation: After changing a inside a transaction, counts reflect the visible state. The inner transaction changes b, then rollback restores b to 10. commit persists the remaining open transaction, so a stays 20.

Input: [('get', 'x'), ('count', 5), ('rollback',), ('commit',), ('set', 'x', 5), ('get', 'x'), ('count', 5)]

Expected Output: [None, 0, False, False, 5, 1]

Explanation: Missing keys return None, counting an unseen value returns 0, and commit/rollback with no open transaction return False.

Input: [('set', 'k', 1), ('begin',), ('set', 'k', 2), ('set', 'k', 3), ('count', 1), ('count', 3), ('rollback',), ('get', 'k'), ('begin',), ('set', 'k', 4), ('begin',), ('set', 'k', 5), ('rollback',), ('get', 'k'), ('commit',), ('get', 'k')]

Expected Output: [0, 1, True, 1, True, 4, True, 4]

Explanation: Multiple writes to the same key in one transaction should restore the original value on rollback. Rolling back the inner transaction restores k to 4, and commit then makes that value permanent.

Input: []

Expected Output: []

Explanation: No operations produce no output.

Hints

Use one hash map for the currently visible value of each key, and another hash map to track how many keys currently map to each value.
For nested transactions, keep a stack of undo logs. The first time a key changes inside a transaction, record its previous value so rollback can restore it.

Quick Overview

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.