Grammarly·Software Engineer·Technical Phone Screen·Senior

Senior

May 2026

Summary

Grammarly software engineering interview that revolved around building a transactional in-memory key-value store from scratch. The problem sounds manageable at first but the nested transaction semantics and keeping the value-count index consistent under rollbacks is where things get genuinely tricky.

Questions Asked (1)

Design and implement an in-memory key-value store supporting set, get, count, begin, commit, and rollback operations, where transactions can be nested.

System DesignAlgorithms & Data StructuresTechnical Trade-offs

Author's notes

The set/get/count part I had no problem with.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then propose a design using a stack of transaction layers, each with its own key-value map and a count map for O(1) count operations. Walk through the implementation of each operation, emphasizing how nested transactions are handled via commit/rollback, and discuss trade-offs between simplicity and performance.

Pro tip: Demonstrate awareness of production concerns by discussing memory management, concurrency, and how you would test nested transactions thoroughly, including edge cases like rollback after commit or nested rollbacks.

1. Clarify Requirements and Constraints

Ask about expected data types, concurrency needs, memory limits, and whether count should reflect the current transaction's view or the global state. Confirm that transactions can be nested arbitrarily deep.

2. Design Data Structures

Propose a stack of transaction layers, where each layer contains a map for key-value pairs and a map for counts (or a single map storing both value and count). The bottom layer represents the committed state.

3. Implement Core Operations

Explain set/get: set writes to the top layer, get searches from top down. For count, maintain a count map per layer or a global count map with transaction-aware updates.

4. Handle Transactions

begin pushes a new empty layer. commit merges the top layer into the layer below (updating values and counts). rollback simply pops the top layer, discarding changes.

5. Discuss Trade-offs and Optimizations

Compare approaches: per-layer count maps vs. global count with undo log. Discuss time/space complexity, concurrency (e.g., locking or copy-on-write), and potential optimizations like lazy merging.

Key Points to Mention

Use a stack of transaction layers to support nesting, with each layer storing its own key-value pairs and count information.
For get, search from the topmost layer downwards to respect transaction isolation.
For count, maintain a count map per layer or a global count map with transaction-aware increments/decrements to achieve O(1) time.
Commit merges the top layer into the parent layer, updating values and counts; rollback discards the top layer.
Time complexity: set/get/count O(1) average, begin O(1), commit O(number of keys in transaction), rollback O(1).
Consider concurrency: use locks or thread-local transactions; discuss memory overhead and potential optimizations like copy-on-write or persistent data structures.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.