Notion·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jul 2026Remote

Summary

Notion SWE interview with a coding problem centered on building a text document class with undo/redo support. The skeleton was provided upfront which was nice, but the real pressure came from the follow-up discussion about data structures and complexity.

Questions Asked (1)

Implement a TextDocument class in Python that supports inserting characters at the end, deleting characters from the end, and undo/redo functionality. A skeleton with the class structure is provided. After any new operation is applied, the redo history should be cleared. Operations should run in time proportional to the size of the change, not the full document size.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

The skeleton made it feel approachable at first but I got tripped up on the undo storage.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then design a solution using a list for the document and two stacks for undo/redo. Implement operations to run in O(k) time by only touching the affected characters, and ensure redo history is cleared on new operations.

Pro tip: Mention that using a list for the document and stacks for history ensures O(k) time for operations, and explicitly state that redo is cleared to maintain correct undo/redo semantics.

1. Clarify requirements and constraints

Ask about expected document size, operation frequency, and whether undo/redo should be unlimited. Confirm that operations should be O(k) and that redo is cleared after new operations.

2. Design data structures

Choose a list (or dynamic array) to store characters for efficient append and pop. Use two stacks (undo and redo) to store operations or document states for undo/redo.

3. Implement core operations

Implement insert and delete by modifying the end of the list and recording the inverse operation in the undo stack. Clear the redo stack after each new operation.

4. Implement undo/redo

Undo pops from the undo stack, applies the inverse operation, and pushes the original operation onto the redo stack. Redo does the opposite.

5. Analyze complexity and edge cases

Discuss time and space complexity, and handle edge cases like undo/redo when stacks are empty or operations on empty document.

Key Points to Mention

Use a list for O(1) amortized append and pop, ensuring O(k) time for operations.
Maintain two stacks for undo and redo, storing operations or document states.
Clear redo stack after any new operation to maintain correct undo/redo semantics.
For insert, push a delete operation to undo stack; for delete, push an insert operation.
Undo/redo operations should also be O(k) by only modifying the affected part.
Consider memory trade-offs: storing operations vs. full document snapshots.

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