Design a Text Editor with Undo and Redo

1Clarify the requirements#

Pin down scope before you touch a class. Undo and redo have a lot of hidden corners, and jumping into code is how people end up redesigning with ten minutes left.

Here is how I would open:

Candidate: What operations are in scope? Insert and delete, or do you want replace and formatting too? I would rather nail reversible edits than sprinkle features thin.

Interviewer: Start with insert and delete. Keep the door open for more.

Candidate: Do we store a full document snapshot per change, or just the diff? That one choice drives the whole memory story.

Interviewer: Make the sensible call and defend it. That is exactly what I want to hear.

What those answers tell me:

• This is a modeling problem, not a buffer problem. The interviewer cares how I represent an action, not how fast StringBuilder is.
• Replace falls out for free. It is a delete followed by an insert, so once insert and delete reverse cleanly, replace costs nothing.
• Memory is a scored axis. "Defend the call" on snapshots versus diffs means they are watching whether I notice 100 snapshots of a 1 MB file is 100 MB of history for nothing.

Functional scope

• Insert text, delete a range, read the current text.
• Undo reverses the last action; redo reapplies the last undone action.
• Any new edit after an undo clears the redo history. That matches every editor people actually use, from VS Code to Notepad.

Non-functional scope

• Undo and redo cost O(size of the change), not O(document).
• Bounded memory, capped at the history depth (100 by default, a tunable constant).
• Clean extension points: a new operation type is one new class, not a rewrite.

Scope I name and set aside

• Single document per editor. Multiple docs just means one undo stack per document, so the core design does not move.
• Cursor position is part of the state. Good undo restores the cursor, not just the text. I note it and come back if there is time.
• Single user, single thread. Collaborative editing (operational transforms, CRDTs) is a different animal, and I flag it as a follow-up rather than let it derail the core.

2Identify the core entities#

Name the pieces and justify each one in a sentence. I do not add a class I cannot defend.

• Document holds the actual text. I use a StringBuilder for the demo so inserts and deletes are cheap and the code reads clearly. A serious editor would use a rope or a piece table, but that hides behind the same interface and swaps in later.
• Command is the heart of the design. Every editable action becomes a Command object that knows how to do itself and how to undo itself. Undo is the exact problem this pattern was invented for.
• InsertCommand / DeleteCommand are the concrete actions. Each stores just enough state to reverse itself: an insert remembers what it inserted and where, a delete remembers what it removed.
• History owns two stacks (undo and redo). It is the only thing that decides what undo and redo mean, and the only thing that enforces the depth cap.
• TextEditor is the front door. The client talks to the editor; the editor builds commands, runs them, and hands them to History.

3Class design#

The dependency flow is deliberately simple:

• TextEditor creates Command objects and pushes them into History.
• Each Command holds a reference to the Document it operates on.
• History does not know or care what a command does. It just calls execute() and undo().

That decoupling is the whole point: adding "uppercase selection" means writing one new command class, and History, editor, and document do not change at all. That is the test I apply to any LLD answer: can I add a feature without editing existing code?

4Key implementation#

Start with the document. Nothing clever: it owns the text and does what it is told.

• The one detail worth naming: delete returns what it removed, because the caller needs that slice to undo later.

public class Document {
    private final StringBuilder buffer = new StringBuilder();

    public void insert(int pos, String text) {
        buffer.insert(pos, text);
    }

    // returns what was removed so the caller can undo it
    public String delete(int pos, int length) {
        String removed = buffer.substring(pos, pos + length);
        buffer.delete(pos, pos + length);
        return removed;
    }

    public String getText() {
        return buffer.toString();
    }
}

The command interface is two methods. That smallness is a feature:

public interface Command {
    void execute();
    void undo();
}

The insert command knows its position and payload up front, so undo is just a delete of the same span. No captured state needed, because an insert is fully reversible from what you already know before running it.

public class InsertCommand implements Command {
    private final Document document;
    private final int position;
    private final String text;

    public InsertCommand(Document document, int position, String text) {
        this.document = document;
        this.position = position;
        this.text = text;
    }

    @Override
    public void execute() {
        document.insert(position, text);
    }

    @Override
    public void undo() {
        document.delete(position, text.length());
    }
}

The delete command is the interesting one, and I point this out directly. It captures the removed text during execute() and holds onto it:

public class DeleteCommand implements Command {
    private final Document document;
    private final int position;
    private final int length;
    private String removed;   // captured at execute time

    public DeleteCommand(Document document, int position, int length) {
        this.document = document;
        this.position = position;
        this.length = length;
    }

    @Override
    public void execute() {
        this.removed = document.delete(position, length);
    }

    @Override
    public void undo() {
        document.insert(position, removed);
    }
}

History manages the two stacks and the bounded depth. The one rule people forget: a brand new edit wipes the redo stack.

import java.util.ArrayDeque;
import java.util.Deque;

public class History {
    private final Deque<Command> undoStack = new ArrayDeque<>();
    private final Deque<Command> redoStack = new ArrayDeque<>();
    private final int maxDepth;

    public History(int maxDepth) {
        this.maxDepth = maxDepth;
    }

    public void push(Command command) {
        undoStack.push(command);
        redoStack.clear();                 // new edit kills the redo future
        if (undoStack.size() > maxDepth) {
            undoStack.removeLast();        // drop the oldest action
        }
    }

    public void undo() {
        if (undoStack.isEmpty()) return;
        Command c = undoStack.pop();
        c.undo();
        redoStack.push(c);
    }

    public void redo() {
        if (redoStack.isEmpty()) return;
        Command c = redoStack.pop();
        c.execute();
        undoStack.push(c);
    }
}

The editor ties it together. Notice it never touches the document except through a command, which is the discipline from section 2 made concrete:

public class TextEditor {
    private final Document document = new Document();
    private final History history = new History(100);

    public void insert(int pos, String text) {
        Command c = new InsertCommand(document, pos, text);
        c.execute();
        history.push(c);
    }

    public void delete(int pos, int length) {
        Command c = new DeleteCommand(document, pos, length);
        c.execute();
        history.push(c);
    }

    public void undo() { history.undo(); }
    public void redo() { history.redo(); }

    public String getText() {
        return document.getText();
    }
}

Here is the runtime flow for a typical insert then undo:

5Design decisions and patterns used#

Command pattern is the backbone.

• Turning each action into an object that knows execute() and undo() makes undo "pop a command and call undo."
• No giant switch statement, no if (lastAction == INSERT) branching.
• New operations plug in without touching History.
• If you take one thing from this problem into your next interview, take this.

Memento, in a small dose.

• The delete command captures the removed text, a tiny memento of the state it needs to restore.
• I do not snapshot the whole document, just the slice that changed.
• Memory stays proportional to the size of edits, not the size of the file: a one-character delete in a 1 MB document stores one character, not a megabyte.

Two stacks, not one pointer into a list.

• You can implement undo and redo as a single list plus a cursor index. Both are correct.
• Two stacks are easier to reason about and harder to get wrong under a whiteboard clock.
• I name the tradeoff and move on rather than burn time defending a style choice.

The editor executes, not History.

• Separation of concerns: the editor owns "do this action now," History owns "remember the past."
• Keeping them apart means I can test History with fake commands and never spin up a real document.
• That testability is worth pointing out; interviewers like candidates who design for it.

Programming to the interface.

• Everything downstream depends on Command, not InsertCommand.
• That is Open/Closed paying off: open to new commands, closed to modifying the engine.

Undo is not a feature you add. It is what you get for free once every edit is an object that can reverse itself.

6Handling edge cases and concurrency#

Empty stacks.

• Undo with nothing to undo, or redo with nothing to redo, is a quiet no-op, not a crash.
• Handled above with the isEmpty() guards.

Redo invalidation (the single most common bug).

• The moment the user types after an undo, the redo stack is gone.
• Skip this and redo reapplies a command that no longer makes sense against the current text, corrupting the document.
• Interviewers probe for it specifically, so call it out before they ask.

Out-of-range positions.

• Insert at position 50 in a 10-character buffer should fail loudly with a clear exception, validated before the command is even pushed.
• A half-executed command sitting in the undo stack is poison: undo will try to reverse an action that only partly happened.

Bounded history.

• Cap the undo stack at maxDepth (100 by default) and drop the oldest action on overflow.
• The trap: once the oldest commands are dropped, their captured state is gone and you can never undo back that far.
• That is the accepted cost of bounded memory, and it matches how real editors behave.

Grouping edits.

• Typing "hello" is five insert commands. One undo should delete the whole word, not one letter, because that is what users expect.
• Introduce a CompositeCommand that holds a list of child commands and undoes them in reverse order.
• The editor decides when to open and close a group: on a pause, a space, or a cursor jump.

Concurrency.

• For a single-user editor I keep everything single-threaded, usually on the UI thread, and do not pretend otherwise.
• Background work (a linter, autosave) that mutates the document must go through the same command pipeline.
• Guard History with a lock or funnel all edits through a single-threaded executor. Two threads pushing without coordination will scramble both stacks, because push, undo, and redo all mutate shared state without atomicity.
• True multi-user collaboration is not a locking problem. It needs operational transforms or CRDTs, a whole separate design and a fair follow-up to name.

7Extensions and follow-ups#

• CompositeCommand for grouped edits and macros. Same interface, so History does not change. The cleanest proof the Command pattern earned its keep.
• Persistent history. Serialize the command stack so undo survives a restart. That nudges you toward storing plain data (position, text) rather than live object references to the document.
• Piece table or rope behind the Document interface for large files, so inserts in the middle of a megabyte-long file stay fast instead of shifting the whole buffer.
• Diff compression. For huge pastes, store a reference to a blob instead of inlining the text, so a 10 MB paste does not sit twice in memory.
• Collaborative editing. Swap the single history for a CRDT or OT engine. The command idea still helps, but conflict resolution becomes the hard part.
• Transaction boundaries and autosave hooks using an Observer, so the UI, word count, and save indicator all react to each committed command.

If you liked this, try the related problems: Design an In-Memory File System, Design a Spreadsheet, or revisit the Command and Memento patterns on their own.