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.

Design a text editor with undo/redo | Notion Coding Question

Design a text editor with undo/redo

Company: Notion

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement a text document editor that supports the following operations: insert(chars) appends characters to the end; delete(k) removes up to k characters from the end (if k exceeds the current length, delete whatever exists); undo_last() undoes the most recent effective operation; redo_last() re-applies the last undone operation. Define an Operation interface with apply(doc) -> doc and rollback_operation() -> Operation to produce the inverse operation for undo/redo. Maintain undo and redo stacks; applying any new operation clears the redo stack. Provide get_current_content() -> str. Handle edge cases such as consecutive deletes, deleting from an empty document, attempting undo/redo when their stacks are empty, and ensuring only effective deletes are recorded for undo. Analyze time and space complexity for each operation and justify your data structure choices. Write unit tests covering: simple undo/redo flows, multiple consecutive deletions, very large deletions that exceed current length, sequences with no insertions, and idempotent redo when no redo is possible.

Quick Answer: This question evaluates understanding of stateful data structures, operation/command semantics for reversible actions, undo/redo stack management, interface design, complexity analysis, and test coverage for mutable editors.

Part 1: Reversible End Operations

Implement reversible end-of-document operations. Given an initial string and a sequence of encoded operations, apply each operation while producing the exact inverse operation needed to roll it back later. Then apply the produced inverses in reverse order and report both the final edited document and the restored document.

Constraints

0 <= len(initial) <= 100000
0 <= len(operations) <= 10000
inserted text contains no ':' character
delete k is a non-negative integer
delete(k) removes min(k, current_length) characters

Examples

Input: ('abc', ['insert:de'])

Expected Output: ['abcde', 'abc', 'delete:2']

Explanation: Appending two characters is undone by deleting two characters.

Input: ('hello', ['delete:2'])

Expected Output: ['hel', 'hello', 'insert:lo']

Explanation: The deleted suffix 'lo' must be remembered so it can be inserted back.

Hints

The inverse of inserting n characters is deleting n characters.
Deleting is lossy: you must capture the exact removed suffix at apply time.

Part 2: Linear Undo and Redo Bookkeeping

Build a flat text editor simulator with undo and redo stacks. The editor starts empty. It supports appending text, deleting from the end, undoing the most recent effective edit, redoing the most recently undone edit, and reading the current content. After every command, return the current content.

Constraints

0 <= len(commands) <= 10000
inserted text contains no ':' character
delete k is a non-negative integer
undo and redo on empty stacks are safe no-ops
Only effective edits are recorded; empty inserts and deletes that remove zero characters do not clear redo

Examples

Input: ['insert:abc', 'insert:de', 'undo', 'redo']

Expected Output: ['abc', 'abcde', 'abc', 'abcde']

Explanation: The second insertion is undone, then redone.

Input: ['undo', 'redo']

Expected Output: ['', '']

Explanation: Undo and redo on empty stacks do nothing.

Hints

Undo and redo are last-in-first-out, so stacks match the required access pattern.
Store enough information in each recorded delete to redo and undo it exactly.

Part 3: Edge-Case Audit for Undo and Redo

Simulate a text editor and expose its internal history sizes after each command. The editor starts empty. This problem focuses on edge cases: consecutive deletes, deletes from an empty document, clamped large deletes, empty undo/redo stacks, and ineffective edits that must not disturb history.

Constraints

0 <= len(commands) <= 10000
inserted text contains no ':' or '|' character
delete k is a non-negative integer
A delete from an empty document removes zero characters and is not recorded
An ineffective edit must not clear redo

Examples

Input: ['insert:abcd', 'delete:1', 'delete:1', 'undo', 'undo', 'redo']

Expected Output: ['abcd|1|0', 'abc|2|0', 'ab|3|0', 'abc|2|1', 'abcd|1|2', 'abc|2|1']

Explanation: Consecutive deletes are independently undoable.

Input: ['delete:5', 'undo', 'redo']

Expected Output: ['|0|0', '|0|0', '|0|0']

Explanation: Deleting from an empty document is ineffective and does not create history.

Hints

Track stack sizes after every command, not just the final document.
Try placing a zero-delete between an undo and a redo; the redo should still be available.

Part 4: Complexity Ledger for an Immutable Text Editor

Instead of returning document contents, compute a cost ledger for an immutable-string text editor. For each command, report the modeled time cost, current document length, and total history payload length after the command.

Constraints

0 <= len(commands) <= 100000
inserted text contains no ':' character
delete k is a non-negative integer
Effective insert of p characters from length n costs n + p
Effective delete from length n costs n and records the removed length; get costs current length
Undo/redo of an append of p costs n + p; undo/redo of a truncate of p costs n - p under this model

Examples

Input: ['insert:abc', 'get', 'delete:1', 'undo', 'redo']

Expected Output: [[3, 3, 3], [3, 3, 3], [3, 2, 4], [3, 3, 4], [2, 2, 4]]

Explanation: The ledger tracks immutable-string edit costs and retained history payload.

Input: ['delete:5', 'undo', 'redo', 'insert:']

Expected Output: [[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]

Explanation: All commands are ineffective or empty-stack no-ops.

Hints

You do not need the actual text for this ledger; lengths and operation payload sizes are enough.
Keep separate payload totals for undo and redo so clearing redo is O(1).

Part 5: Step-by-Step Unit Test Runner for a Text Editor

Create a reference test runner for the text editor. Each test suite contains commands paired with the expected document content after that command. Execute each suite from a fresh empty editor and return the first failing step index, or -1 if every assertion passes.

Constraints

0 <= number of suites <= 1000
0 <= total number of steps <= 100000
inserted text contains no ':' character
Each suite starts with a fresh empty editor
Assertions are checked immediately after every command

Examples

Input: [[['insert:abc', 'abc'], ['undo', ''], ['redo', 'abc']]]

Expected Output: [-1]

Explanation: A simple undo/redo flow passes.

Input: [[['insert:abcd', 'abcd'], ['delete:1', 'abc'], ['delete:1', 'ab'], ['undo', 'abc'], ['redo', 'ab']], [['insert:x', 'x'], ['redo', '']]]

Expected Output: [-1, 1]

Explanation: The first suite passes; the second fails because redo with nothing to redo should leave 'x' unchanged.

Hints

Reset the editor state, undo stack, and redo stack for each suite.
A no-op edit between undo and redo should not clear redo; include that behavior in the reference runner.

Quick Overview

This question evaluates understanding of stateful data structures, operation/command semantics for reversible actions, undo/redo stack management, interface design, complexity analysis, and test coverage for mutable editors.