Design a text editor with undo and redo

01The design, in the six-step framework

1. Requirements and use cases

A user types text at a cursor, deletes backwards, moves the cursor, and can undo and redo any number of steps. A redo stack is cleared by a new edit. A group of edits performed between begin_batch and end_batch, such as a find-and-replace, undoes as one step. The editor reports its full text.

Out of scope: rendering, line and column navigation (the reported interview noted that up and down movement makes the structure harder and is a follow-up), selection, and collaborative editing, which is a different problem (Google Docs).

Constraints: insert and delete at the cursor must be fast for documents of millions of characters, which rules out a plain string; undo must be exact, restoring both text and cursor; memory for history should be proportional to what changed, not to document size per edit.

2. Core entities and relationships

• Buffer: the text storage, a gap buffer: an array with an empty gap kept at the cursor, so typing is an array write and deleting is a pointer move.
• TextEditor: the facade the user talks to. It owns the buffer, the cursor and two stacks of commands.
• Command: an edit that knows how to apply and revert itself: Insert, Delete, and Batch, which is a list of commands reverted in reverse order.

The editor composes the buffer and the history; commands are meaningless outside their editor. Batch both implements Command and composes Commands, which is the composite shape and the reason batched undo costs no special case in undo.

3. Interfaces and key methods

class Command(Protocol):
    def apply(self, doc: "Buffer") -> None: ...
    def revert(self, doc: "Buffer") -> None: ...

class TextEditor:
    def insert(self, text: str) -> None:        """Insert at the cursor; cursor moves after the text."""
    def delete(self, n: int) -> str:            """Delete up to n chars before the cursor; returns them."""
    def move(self, delta: int) -> int:          """Move the cursor; returns the clamped position."""
    def undo(self) -> bool: ...                 # False if nothing to undo
    def redo(self) -> bool: ...
    def begin_batch(self) -> None:              """Edits until end_batch() undo as one step."""
    def end_batch(self) -> None: ...
    def text(self) -> str: ...

Invariants: 0 <= cursor <= len(doc); applying a command and then reverting it restores the buffer exactly; the redo stack is empty whenever the last operation was a new edit; a Delete command records what it removed on apply, so revert never guesses.

4. Design patterns and the choices behind them

Command with explicit revert, not snapshots

What varies is the edit. Saving the whole text before each keystroke (memento) is simplest and correct but costs document size per edit; for a one-megabyte file that is a megabyte per keystroke. A command stores only the inserted or deleted characters and its position, so history grows with the size of the change. Memento is still the right answer for operations whose inverse is hard to express, and a hybrid (snapshot every N commands) is the usual production compromise.

Gap buffer for the text

A Python string copies on every edit, O(n) per keystroke. A doubly linked list of characters, the reported candidate's instinct, makes insert O(1) but indexing O(n) and uses many times the memory. A gap buffer keeps O(1) amortised edits at the cursor, which is where edits actually happen, and is what classic editors use. A rope or piece table is the next step when edits jump around; mention, do not build.

Cursor restored by the history, not the command

Commands know positions but not the user's cursor. The history stores the cursor alongside each command so undo lands the cursor where it was before the edit, matching what users expect.

Batch as a composite command

Because Batch is itself a Command, undo and redo are unchanged by batching; only _run decides whether a command goes to the stack or into the open batch. That is open-closed in practice: a new command type, say Replace, needs no change to the editor.

5. Core flow and code

1. insert("hello"): an Insert at position 0 is applied to the buffer, pushed to the undo stack with cursor 0, and the cursor moves to 5.
2. delete(2): a Delete at position 5 removes "lo" and records it; cursor 3; redo cleared.
3. undo(): the Delete is popped and reverted by re-inserting "lo" at 3; cursor returns to 5; the command moves to the redo stack with the cursor it should restore on redo.
4. begin_batch(), two inserts, end_batch(): both inserts are applied immediately but collected in one Batch, which is pushed as a single undo step.
5. undo() reverts the batch's two inserts in reverse order and restores the cursor from before the batch.
6. redo() re-applies the batch in forward order.

from dataclasses import dataclass, field
from typing import Protocol

class Buffer:
    """Gap buffer: insert and delete at the cursor are O(1) amortised."""
    def __init__(self, capacity: int = 64) -> None:
        self._buf: list[str] = [""] * capacity
        self._gap_start, self._gap_end = 0, capacity

    def __len__(self) -> int:
        return len(self._buf) - (self._gap_end - self._gap_start)

    def _move_gap(self, pos: int) -> None:
        while pos < self._gap_start:
            self._gap_start -= 1; self._gap_end -= 1
            self._buf[self._gap_end] = self._buf[self._gap_start]
        while pos > self._gap_start:
            self._buf[self._gap_start] = self._buf[self._gap_end]
            self._gap_start += 1; self._gap_end += 1

    def insert(self, pos: int, s: str) -> None:
        self._move_gap(pos)
        if self._gap_end - self._gap_start < len(s):
            grow = max(len(s), len(self._buf))
            self._buf[self._gap_end:self._gap_end] = [""] * grow
            self._gap_end += grow
        for ch in s:
            self._buf[self._gap_start] = ch; self._gap_start += 1

    def delete(self, pos: int, n: int) -> str:
        """Remove n chars ending at pos (i.e. [pos-n, pos))."""
        self._move_gap(pos)
        removed = "".join(self._buf[pos - n:pos])
        self._gap_start -= n
        return removed

    def text(self) -> str:
        return "".join(self._buf[:self._gap_start] + self._buf[self._gap_end:])

class Command(Protocol):
    def apply(self, doc: Buffer) -> None: ...
    def revert(self, doc: Buffer) -> None: ...

@dataclass
class Insert:
    pos: int
    s: str
    def apply(self, doc: Buffer) -> None: doc.insert(self.pos, self.s)
    def revert(self, doc: Buffer) -> None: doc.delete(self.pos + len(self.s), len(self.s))

@dataclass
class Delete:
    pos: int                      # cursor position before deleting
    s: str                        # what was removed, filled on apply
    def apply(self, doc: Buffer) -> None: self.s = doc.delete(self.pos, len(self.s))
    def revert(self, doc: Buffer) -> None: doc.insert(self.pos - len(self.s), self.s)

@dataclass
class Batch:
    steps: list[Command] = field(default_factory=list)
    def apply(self, doc: Buffer) -> None:
        for c in self.steps: c.apply(doc)
    def revert(self, doc: Buffer) -> None:
        for c in reversed(self.steps): c.revert(doc)

class TextEditor:
    def __init__(self) -> None:
        self._doc = Buffer()
        self._cursor = 0
        self._undo: list[tuple[Command, int]] = []     # (command, cursor before it)
        self._redo: list[tuple[Command, int]] = []
        self._batch: Batch | None = None
        self._batch_cursor = 0

    def _run(self, cmd: Command) -> None:
        before = self._cursor
        cmd.apply(self._doc)
        if self._batch is not None:
            self._batch.steps.append(cmd)
        else:
            self._undo.append((cmd, before)); self._redo.clear()

    def insert(self, text: str) -> None:
        self._run(Insert(self._cursor, text)); self._cursor += len(text)

    def delete(self, n: int) -> str:
        n = min(n, self._cursor)
        if n == 0: return ""
        cmd = Delete(self._cursor, " " * n); self._run(cmd); self._cursor -= n
        return cmd.s

    def move(self, delta: int) -> int:
        self._cursor = max(0, min(len(self._doc), self._cursor + delta)); return self._cursor

    def begin_batch(self) -> None:
        if self._batch is None:
            self._batch, self._batch_cursor = Batch(), self._cursor

    def end_batch(self) -> None:
        if self._batch is not None and self._batch.steps:
            self._undo.append((self._batch, self._batch_cursor)); self._redo.clear()
        self._batch = None

    def undo(self) -> bool:
        if not self._undo: return False
        cmd, before = self._undo.pop(); cmd.revert(self._doc)
        self._redo.append((cmd, self._cursor)); self._cursor = before
        return True

    def redo(self) -> bool:
        if not self._redo: return False
        cmd, after = self._redo.pop(); cmd.apply(self._doc)
        self._undo.append((cmd, self._cursor)); self._cursor = after
        return True

    def text(self) -> str:
        return self._doc.text()

6. Extensions, concurrency and what interviewers probe

• Up and down movement: needs line starts. Keep a sorted list of newline offsets updated by each command, or move to a piece table with a line index; this is the follow-up the reported interviewer used to separate candidates.
• Coalescing keystrokes: typing "hello" should undo as one word. Merge an Insert into the previous Insert when it is adjacent and within a short time, using an injected clock.
• Bounded history: cap the undo stack and drop the oldest; with commands this is cheap, with snapshots it was the whole memory budget.
• Threads: an editor is single-threaded by nature; if a background spell-checker reads, hand it an immutable copy of text() rather than sharing the buffer.
• Test first: insert, delete, undo, redo on a short string asserting text and cursor after each step; a batch of three edits undone in one call; redo cleared after a fresh edit.
• Common mistake: storing a Delete command without capturing the deleted text, so undo cannot restore it, and forgetting to clear the redo stack on a new edit.

02Where this question was reported

• LeetCode Discuss · LeetCode 2296 (Hard), Google-tagged (freq 26.5)
• Codemia · Codemia Hard; also 'Code Editor' (Advanced)
• Exponent / Aced · Aced/Exponent: 'Design a collaborative text editor' (OT vs CRDT)
• GitHub · Machine coding 'Design Google Doc' (all companies)
• LeetCode Discuss · Cursor movement, insert, delete, undo; which data structures (doubly linked list; up/down movement makes it harder); working code expected, not system design
• Land the Lab · 'Design layer document with undo, redo and batches'
• Medium · 60-min round: Google-Docs-style toolbar with bold/italic/underline and undo/redo
• lldcoding.blogspot.com · 'Asked in' list includes Google; two-stack undo/redo, Version snapshots, collaboration-ready