PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

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.

  • Medium
  • Notion
  • Coding & Algorithms
  • Software Engineer

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.

Input: ('abc', ['delete:10'])

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

Explanation: A too-large delete is clamped to the current document length.

Input: ('hi', ['insert:', 'delete:0'])

Expected Output: ['hi', 'hi', 'delete:0', 'insert:']

Explanation: Empty inserts and zero deletes produce no content change but still have well-defined inverses in this operation-only model.

Input: ('abc', ['insert:xyz', 'delete:4'])

Expected Output: ['ab', 'abc', 'delete:3', 'insert:cxyz']

Explanation: The delete removes part of the old text and all inserted text, so the exact suffix must be captured.

Hints

  1. The inverse of inserting n characters is deleting n characters.
  2. 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.

Input: ['insert:a', 'insert:b', 'undo', 'insert:c', 'redo']

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

Explanation: The new effective insert clears the redo branch, so redo does nothing.

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

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

Explanation: The zero-delete is ineffective, so it does not clear the pending redo.

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

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

Explanation: A large delete is clamped and remains exactly undoable and redoable.

Hints

  1. Undo and redo are last-in-first-out, so stacks match the required access pattern.
  2. 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.

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

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

Explanation: A large delete removes exactly the existing content and can be undone/redone.

Input: ['insert:abc', 'delete:2', 'undo', 'delete:0', 'redo']

Expected Output: ['abc|1|0', 'a|2|0', 'abc|1|1', 'abc|1|1', 'a|2|0']

Explanation: The zero-delete does not clear the redo stack.

Input: ['undo', 'delete:1', 'redo', 'delete:0']

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

Explanation: A sequence with no insertions remains safe and empty.

Hints

  1. Track stack sizes after every command, not just the final document.
  2. 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.

Input: ['insert:a', 'insert:bc', 'undo', 'insert:d']

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

Explanation: The final insert clears the redo payload before recording its own payload.

Input: ['insert:abcd', 'delete:10', 'undo']

Expected Output: [[4, 4, 4], [4, 0, 8], [4, 4, 8]]

Explanation: The large delete records four removed characters.

Input: ['get']

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

Explanation: Reading an empty document has zero modeled cost.

Hints

  1. You do not need the actual text for this ledger; lengths and operation payload sizes are enough.
  2. 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.

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

Expected Output: [-1]

Explanation: Repeated redo and delete from empty are idempotent no-ops.

Input: [[['insert:abc', 'abc'], ['delete:10', ''], ['undo', 'abc'], ['delete:0', 'abc'], ['redo', '']]]

Expected Output: [-1]

Explanation: The zero-delete preserves the pending redo after undo.

Input: [[]]

Expected Output: [-1]

Explanation: An empty test suite has no failing assertion.

Hints

  1. Reset the editor state, undo stack, and redo stack for each suite.
  2. A no-op edit between undo and redo should not clear redo; include that behavior in the reference runner.
Last updated: Jun 26, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • AI Coding Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Find Top Errors in Time Window - Notion (medium)
  • Implement a DAG task graph - Notion (medium)
  • Implement Table Aggregation - Notion (easy)
  • Implement text editor with undo/redo - Notion (Medium)