Cruxly

Cruxly › Low-level design › LLD Exercises

Text Editor Undo/Redo

every edit must know how to reverse itself, and a new edit must destroy the wrong future

Open the interactive lesson

Prompt: design the undo/redo system for a text editor. Users type, delete, and paste; undo() reverses the last operation, redo() re-applies an undone operation — until the user makes a new edit, after which the redo history for the old future must be gone.

45 minutes. The interesting part is not the text buffer. It's that undo/redo is two patterns working together — Command for "how does one edit reverse itself," and a stack discipline for "what happens to redo history when a new edit arrives"

Applying the five moves: nouns are Edit (an object, not a log line — this is the move-2 decision the exercise hinges on), UndoStack, RedoStack — resist the urge to model Type/Delete/Paste as unrelated classes rather than implementations of one Edit interface. The invariant is "redo history exists only for edits undone since the last new edit; any new edit invalidates it entirely" — say this before touching the stacks, because it's what tells you redo clears on a fresh edit rather than merely not-adding-to. The interface seam is Edit itself (execute()/undo()), a direct instance of Command, because the prompt's variety of operations (type, delete, paste) is the signal that more will come and each needs to know how to reverse itself. Concurrency: a single user typing in one document has no real concurrency story — say so plainly, and name collaborative multi-cursor editing as the genuinely harder, separate problem if that follow-up arrives.

Scope, and why an edit must be an object, not a log line

In scope: insert, delete, and replace operations; undo; redo; a bounded history (say a number — infinite undo history is a real memory decision, not a free assumption). Out of scope (say it): collaborative multi-user editing (a much harder problem — this track's collaborative-document exercise covers it — name it as a different exercise, not an extension of this one), rich-text formatting operations, file persistence.

The tempting first design is a log of what happened — "inserted 'hello' at position 4" as a string or a simple record — and undo replays the log backward by inferring the reverse action from the description. This is the wrong shape, because inferring "delete 5 characters starting at 4" from a log line is re-deriving information the edit already had at the moment it happened, and that re-derivation is exactly where undo bugs live: an insert that also auto-indented, or a paste that replaced a selection, has a reverse operation that is not simply "delete what I just typed" — it may need to restore text that was overwritten.

The correct shape: every edit is an object that knows how to execute() and undo() itself, computed once, at the moment of the edit, when all the information is available. This is the Command pattern, arrived at because the problem requires the reverse of an action to be captured before the state needed to compute it disappears — not because "Command" was the goal.

The classes — Command with captured state

public interface EditCommand {
    void execute(TextBuffer buffer);
    void undo(TextBuffer buffer);
}

public class InsertCommand implements EditCommand {
    private final int position;
    private final String text;
    InsertCommand(int position, String text) { this.position = position; this.text = text; }
    public void execute(TextBuffer buffer) { buffer.insertAt(position, text); }
    public void undo(TextBuffer buffer)    { buffer.deleteRange(position, position + text.length()); }
}

public class DeleteCommand implements EditCommand {
    private final int start, end;
    private String deletedText;                          // captured at execute time — this is the point
    DeleteCommand(int start, int end) { this.start = start; this.end = end; }
    public void execute(TextBuffer buffer) {
        deletedText = buffer.substring(start, end);       // MUST capture before deleting, or undo has nothing to restore
        buffer.deleteRange(start, end);
    }
    public void undo(TextBuffer buffer) { buffer.insertAt(start, deletedText); }
}

public class ReplaceCommand implements EditCommand {
    private final int start, end;
    private final String newText;
    private String oldText;                               // same capture-before-mutate discipline
    ReplaceCommand(int start, int end, String newText) {
        this.start = start; this.end = end; this.newText = newText;
    }
    public void execute(TextBuffer buffer) {
        oldText = buffer.substring(start, end);
        buffer.deleteRange(start, end);
        buffer.insertAt(start, newText);
    }
    public void undo(TextBuffer buffer) {
        buffer.deleteRange(start, start + newText.length());
        buffer.insertAt(start, oldText);
    }
}

DeleteCommand.deletedText and ReplaceCommand.oldText are captured inside execute(), not passed in from outside — this is the entire reason Command works here. The information needed to undo a delete (what was deleted) only exists at the moment of deletion; capturing it as a side effect of execute() is what makes undo() possible without re-deriving it from a log line after the fact. A design that tries to make commands stateless and infer the reverse from the buffer's current state will discover this is impossible the moment two edits happen in sequence — the buffer no longer contains the information the first undo needs.

The two-stack discipline, and why a new edit must destroy the redo stack

public void perform(EditCommand cmd) {
    cmd.execute(buffer);
    undoStack.push(cmd);
    if (undoStack.size() > maxHistory) undoStack.removeLast();
    // (nothing else here)
}
public class UndoManager {
    private final Deque<EditCommand> undoStack = new ArrayDeque<>();
    private final Deque<EditCommand> redoStack = new ArrayDeque<>();
    private final TextBuffer buffer;
    private final int maxHistory;                          // bounded — infinite undo is a real memory cost

    public void perform(EditCommand cmd) {
        cmd.execute(buffer);
        undoStack.push(cmd);
        if (undoStack.size() > maxHistory) undoStack.removeLast();   // evict oldest, not newest
        redoStack.clear();                                  // THE RULE: any new edit destroys the old future
    }

    public boolean undo() {
        if (undoStack.isEmpty()) return false;
        EditCommand cmd = undoStack.pop();
        cmd.undo(buffer);
        redoStack.push(cmd);
        return true;
    }

    public boolean redo() {
        if (redoStack.isEmpty()) return false;
        EditCommand cmd = redoStack.pop();
        cmd.execute(buffer);
        undoStack.push(cmd);
        return true;
    }
}

redoStack.clear() inside perform() is not a special case handled somewhere else — it is the rule, stated as one line exactly where a new edit is accepted. The scenario it exists for: type "hello", undo it (now on the redo stack), type "world" instead. The undone "hello" is not a future the document can coherently return to anymore — "world" already committed a different timeline. Failing to clear the redo stack here is the single most common undo/redo bug, and it manifests as a redo button that, when pressed after an intervening edit, corrupts the document by replaying an operation against text that has since changed underneath it.

Bounding undoStack at maxHistory and evicting the oldest entry, not the newest, is the correct direction — a user pressing undo repeatedly should walk back through their most recent history first; evicting from the front of that walk would silently shorten how far back undo can go without the user noticing until they hit the wall unexpectedly.

Follow-ups they will ask

"Batch rapid keystrokes into one undo step, so undo doesn't require pressing it once per character." This is a coalescing decision made in perform(), not a new command type — consecutive InsertCommands for single characters, arriving within a short time window and at adjacent positions, merge into one command on the stack (extend the last command's text instead of pushing a new one), while a pause, a cursor move, or a delete breaks the coalescing and starts a new command. Naming the exact trigger for "this is still one edit vs. a new one" is the actual design decision here, not the merging mechanism itself.

"What about memory: text pasted and later undone, does the buffer's old content live forever in the undo stack?" Yes, until evicted by maxHistory or garbage-collected after enough subsequent edits push it out — and naming this explicitly (a large paste's undo entry holds a full copy of the replaced text) is the honest answer, versus implying undo history is free. A production editor bounds history by total captured bytes, not just command count, for exactly this reason.

"Extend this to collaborative editing — two users typing at once." Say directly that this is a different, harder exercise (covered elsewhere in this track), not a natural extension: a single linear undo stack assumes one actor and one timeline, and concurrent edits from multiple users break that assumption at the root — the fix is not a bigger stack, it's a fundamentally different model (operational transform or CRDTs), and recognizing where the current design's foundational assumption stops holding is worth more than attempting to patch it.

How to say it in the interview

"Every edit needs to be able to undo itself, which means every edit is an object with an execute and an undo method, not just a description of what happened — that's Command. Separately, the moment a new edit happens after some undos, the entire redo stack has to be thrown away, and that's not a special case, it's the actual rule."

Checklist

Practice this interactively
Share this lessonWhatsAppLinkedInX

Related lessons