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 Technical Screen rounds at Notion.

What role is this question designed for?

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

Implement text editor with undo/redo | Notion Coding Question

Implement text editor with undo/redo

Company: Notion

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Implement a text document with undo/redo based on this Python skeleton: class Operation: class InsertAtEndOperation(Operation): def __init__(self, chars_to_insert: str): self.chars_to_insert = chars_to_insert class DeleteFromEndOperation(Operation): def __init__(self, num_chars_to_delete: int): self.num_chars_to_delete = num_chars_to_delete class TextDocument: def __init__(self) -> None: def apply_operation(self, op: Operation) -> None: def get_current_content(self) -> str: return self.doc def undo_last(self) -> None: def redo_last(self) -> None: Requirements: - apply_operation must support appending chars_to_insert to the end and deleting up to num_chars_to_delete characters from the end (no error if fewer characters exist). - get_current_content returns the current string; the document starts empty. - undo_last reverts the most recent applied operation; redo_last reapplies the most recent undone operation. - After any successful apply_operation, clear the redo history. - Ensure each operation runs in time proportional to the size of the change (avoid copying the entire document per step). Choose suitable data structures and an approach to store inverse operations. Discuss: data structures used (e.g., stacks/chunked buffer), how inverse operations are computed, time/space complexity of each method, and key edge cases (e.g., deleting more than available, multiple undos/redos).

Quick Answer: This question evaluates implementation-level skills in state management, reversible operation design, and efficient mutable-string handling within the Coding & Algorithms domain.

Implement a text document that supports two edit operations and full undo/redo. You are given a list of commands to replay against an initially empty document. Each command is a list whose first element is the command name: - `["insert", s]` — append the string `s` to the END of the document. - `["delete", k]` — delete up to `k` characters from the END of the document. Deleting more characters than the document holds is NOT an error — it removes everything available (clamps to the current length). - `["undo"]` — revert the most recently APPLIED edit. If there is nothing to undo, it is a no-op. - `["redo"]` — reapply the most recently UNDONE edit. If there is nothing to redo, it is a no-op. - `["read"]` — record the current document content as a single string. Rules: - The document starts empty (`""`). - After any `insert`/`delete` command is applied, the redo history must be cleared (you cannot redo a branch you abandoned by making a fresh edit). - Characters are Unicode codepoints (Python's default string indexing). Return the list of strings recorded by each `["read"]` command, in order. The intended design constraint: each mutating step must run in time proportional to the SIZE OF THE CHANGE, not the size of the whole document — use a mutable buffer for the text and store INVERSE operations (not full snapshots) on the undo/redo stacks. In particular, the inverse of a delete must capture the exact substring that was actually removed, computed at apply time.

Constraints

The document starts empty.
delete clamps to the current length and never raises.
undo on an empty undo history and redo on an empty redo history are no-ops.
Any fresh insert/delete clears the redo history.
Characters are Unicode codepoints (index by codepoint, not byte).
Each mutating step should run in O(size of change), not O(document size) — use a mutable buffer + inverse operations, not full snapshots.

Examples

Input: ([['insert', 'Hello'], ['read'], ['insert', ' World'], ['read'], ['delete', 6], ['read'], ['undo'], ['read'], ['undo'], ['read'], ['redo'], ['read']],)

Expected Output: ['Hello', 'Hello World', 'Hello', 'Hello World', 'Hello', 'Hello World']

Explanation: Spec walkthrough: build 'Hello World', delete ' World' (6 chars), then undo restores ' World', undo again removes ' World', and redo re-deletes it. Inserts and deletes round-trip exactly through the inverse stacks.

Input: ([['insert', 'abc'], ['insert', 'def'], ['read'], ['undo'], ['undo'], ['read'], ['insert', 'X'], ['read'], ['redo'], ['read']],)

Expected Output: ['abcdef', '', 'X', 'X']

Explanation: After two undos the doc is empty; the fresh insert 'X' CLEARS the redo history, so the trailing redo is a no-op — 'X' stays. This is the abandoned-branch rule.

Input: ([['insert', 'hi'], ['delete', 100], ['read'], ['undo'], ['read']],)

Expected Output: ['', 'hi']

Explanation: Over-deletion: delete 100 from a 2-char doc clamps to removing 'hi' (no error). Its inverse records insert('hi'), so undo restores the document.

Input: ([['undo'], ['redo'], ['read']],)

Expected Output: ['']

Explanation: Undo and redo on empty histories are well-defined no-ops; the document stays empty.

Input: ([['read']],)

Expected Output: ['']

Explanation: A read on a brand-new document returns the empty string.

Input: ([['insert', 'café'], ['read'], ['delete', 1], ['read'], ['undo'], ['read']],)

Expected Output: ['café', 'cafe', 'café']

Explanation: Unicode handling: here the accented 'e' is a base 'e' followed by a combining accent codepoint, so deleting 1 codepoint strips the accent ('cafe'); undo re-inserts exactly that removed codepoint, restoring the original.

Input: ([['insert', 'abcd'], ['delete', 2], ['delete', 1], ['read'], ['undo'], ['read'], ['undo'], ['read'], ['undo'], ['read']],)

Expected Output: ['a', 'ab', 'abcd', '']

Explanation: Two deletes leave 'a'; undoing them re-inserts 'c' then 'cd' (each inverse holds the exact removed substring), and a final undo reverses the original insert back to empty.

Hints

Command pattern + two stacks: one stack of inverse operations for undo, one for redo. The hard constraint is the O(change) time bound — let it drive how you store both the document and the history.
Store the document as a mutable list of characters, not an immutable string: appending/truncating at the end is amortized O(change), whereas self.doc + chars copies the whole document O(n) per edit.
Push inverses, not snapshots. The inverse of an insert(s) is delete(len(s)). The inverse of a delete is insert(removed) — but you must capture the actually-removed substring AT APPLY TIME, because the count removed can be smaller than requested when the document is short.
Elegant symmetry: make 'apply an op' return that op's inverse. Then undo and redo are the same two lines — apply something, push its inverse onto the opposite stack — with no insert-vs-delete branching.

Quick Overview

This question evaluates implementation-level skills in state management, reversible operation design, and efficient mutable-string handling within the Coding & Algorithms domain.