Courses › Low-Level Design › Problem Walkthroughs

Design a Text Editor (Undo/Redo)

The Command pattern, undo/redo stacks, grouping edits and gap buffers vs ropes.

"Design a text editor with undo and redo" is the canonical Command pattern question. Each edit becomes an object that knows how to apply itself and how to reverse itself. Two stacks of those objects give you unlimited undo and redo. Follow-ups test your choice of text data structure and how you group edits together.

Requirements

• Insert text at the cursor, delete characters, and move the cursor.
• undo() reverses the most recent edit. redo() re-applies the most recently undone edit.
• A new edit after an undo clears the redo history.
• Possible extras: select and replace, grouping typed characters into one undo step, a history limit.

Command pattern in one picture

[execute(cmd)] -> (undo stack) -> [undo] -> (redo stack) -> [redo] -> (undo stack)
[execute(cmd)] -> [clear redo stack]

Each command implements execute() and undo(). Crucially, a command records whatever it needs to reverse itself. For a delete, that's the deleted text, which you only know at execution time.

Implementation

from abc import ABC, abstractmethod


class Document:
    """The receiver: plain text plus a cursor, with no history logic."""
    def __init__(self):
        self.text = ""
        self.cursor = 0

    def insert(self, pos, s):
        self.text = self.text[:pos] + s + self.text[pos:]

    def delete(self, pos, length):
        removed = self.text[pos:pos + length]
        self.text = self.text[:pos] + self.text[pos + length:]
        return removed


class Command(ABC):
    @abstractmethod
    def execute(self, doc): ...
    @abstractmethod
    def undo(self, doc): ...


class InsertCommand(Command):
    def __init__(self, s):
        self.s, self.pos = s, None

    def execute(self, doc):
        if self.pos is None:              # first run: capture the position once
            self.pos = doc.cursor
        doc.insert(self.pos, self.s)
        doc.cursor = self.pos + len(self.s)

    def undo(self, doc):
        doc.delete(self.pos, len(self.s))
        doc.cursor = self.pos


class BackspaceCommand(Command):
    def __init__(self, count):
        self.count, self.pos, self.removed = count, None, ""

    def execute(self, doc):
        if self.pos is None:              # first run: work out the range and remember it
            self.pos = max(0, doc.cursor - self.count)
            self.removed = doc.delete(self.pos, doc.cursor - self.pos)
        else:                             # redo: replay exactly the same range
            doc.delete(self.pos, len(self.removed))
        doc.cursor = self.pos

    def undo(self, doc):
        doc.insert(self.pos, self.removed)
        doc.cursor = self.pos + len(self.removed)


class Editor:
    def __init__(self, history_limit=1000):
        self.doc = Document()
        self.undo_stack, self.redo_stack = [], []
        self.history_limit = history_limit

    def _run(self, cmd):
        cmd.execute(self.doc)
        self.undo_stack.append(cmd)
        if len(self.undo_stack) > self.history_limit:
            self.undo_stack.pop(0)
        self.redo_stack.clear()           # a new edit invalidates the redo history

    def type(self, s): self._run(InsertCommand(s))
    def backspace(self, n=1): self._run(BackspaceCommand(n))

    def move_cursor(self, pos):            # navigation is not an undoable edit
        self.doc.cursor = max(0, min(pos, len(self.doc.text)))

    def undo(self):
        if self.undo_stack:
            cmd = self.undo_stack.pop()
            cmd.undo(self.doc)
            self.redo_stack.append(cmd)

    def redo(self):
        if self.redo_stack:
            cmd = self.redo_stack.pop()
            cmd.execute(self.doc)
            self.undo_stack.append(cmd)

e = Editor()
e.type("hello")
e.type(" world")
e.backspace(6)
assert e.doc.text == "hello"
e.undo()
assert e.doc.text == "hello world"
e.undo(); e.redo()
assert e.doc.text == "hello world"

[!WARNING] Redo must replay the same edit, not a new one The user can move the cursor between an undo and a redo. If execute read doc.cursor every time, redo would insert the text somewhere else. So each command captures its position (and, for deletes, the removed text) on its first run and replays exactly that on redo. Point this out. It shows you've thought about redo, not just undo.

Grouping keystrokes

Users expect one undo to remove a whole word, not a single letter. Two common approaches:

• Merge adjacent commands: if a new InsertCommand starts where the previous one ended, and it arrives within a short time window, append its text to the previous command instead of pushing a new one.
• Composite command / transactions: begin_group() … end_group() collects commands into a MacroCommand that executes them in order and undoes them in reverse order. "Replace all" uses this.

Choosing the text structure

Rebuilding a Python string costs O(n) per edit, which is fine for an interview. For large documents, the interviewer may ask about alternatives:

Alternative: snapshots (Memento)

Instead of reversible commands, store a snapshot of the document before each edit. That's simpler, and it works for edits that are hard to reverse. The cost is memory: O(document size) per step. In practice you store the text structure immutably and share unchanged parts, or snapshot only every N commands.

Follow-ups

• Collaborative editing: local undo has to undo *your* edit, not the latest edit from anyone. That leads to operational transformation or CRDTs. See Merging Concurrent Edits.
• Persisting history: serialize commands into an append-only log. Replaying the log rebuilds the document.
• Selection and formatting: formatting becomes another command type (ApplyStyle(range, style)) that stores the previous style so it can be undone.

[!TIP] Practice Text Editor with Undo and Redo · Spreadsheet with Formulas · Design Patterns