Knowledge Guide
Home › Hands-On Builds › LLD Katas

Design a Text Editor with Undo/Redo

Design a Text Editor with Undo/Redo

Every editor -- Word, VS Code, Google Docs, the text box you are reading this in -- promises the same small miracle: press Ctrl+Z and the last thing you did quietly un-happens, press it again for the one before that, and Ctrl+Y brings an undone step back. Interviewers reach for this problem constantly because it is the cleanest possible showcase for the Command pattern: model every action as an object that knows how to replay itself and how to reverse itself, then undo/redo becomes "pop a stack and call a method" instead of a pile of special cases. This kata makes you build that object model -- Insert/Delete/Composite commands, an undo stack, a redo stack, and the one invariant that keeps them honest -- in Java and Go, and then makes you break two real implementations of it: one that quietly corrupts the document, and one that quietly eats all your memory. That gap, from "I can describe the Command pattern" to "I can defend the exact line of code that keeps it correct," is what the interviewer is actually listening for.

The Trap

Say you are asked to add undo to a simple text editor. The "just make it work" instinct is almost always one of two shapes, and both feel reasonable for the first five minutes.

Shape one: remember the previous string. Before every keystroke, save a copy of the whole document into a variable called previousText; Ctrl+Z restores it. This works for exactly one level of undo. The second Ctrl+Z has nothing further back to go to -- there is only ever "now" and "one step ago," because a single variable cannot hold a history, only a single snapshot. Users notice immediately: they expect undo to walk back through everything they did this session, not just the last keystroke.

So the instinct is upgraded: keep an array of full snapshots, one per keystroke, and undo pops the most recent one off. Now multi-level undo genuinely works -- and it quietly becomes a memory time bomb. A document that grows to 20,000 characters through 20,000 keystrokes doesn't cost you a history of 20,000 characters total; it costs you a history of a 0-character snapshot, then a 1-character snapshot, then a 2-character snapshot, all the way up to a 19,999-character snapshot -- roughly 200 million characters retained across the whole session (the sum 0+1+2+...+(n-1) is n(n-1)/2), even though the user only ever typed 20,000 of them. At 2 bytes per character in a JVM string, that is hundreds of megabytes of history sitting in memory for a document that itself is a few tens of KB. This kata measures the exact ratio later -- it is not a rough guess, it is a number you will print yourself: 10,000x more characters retained, for this exact input.

There is a second trap, orthogonal to memory, that is arguably worse because it corrupts data instead of just being slow: once you have both an undo stack and a redo stack, what happens if the user undoes something and then types something new instead of redoing? The redo stack is still sitting there holding "the future that would have happened if you'd pressed redo." If a new keystroke doesn't explicitly throw that stale future away, it is still there, waiting -- and the moment the user later presses redo out of habit, your editor replays an edit that was written for a document that no longer exists. Concretely: type "cat", undo once (back to "ca," with "insert 't' at position 2" sitting in the redo stack), then type "r" instead of redoing (now the document is "car"). Press redo, and a buggy implementation replays "insert 't' at position 2" against today's document -- producing "catr". Nothing crashed. Nothing threw an exception. The document is just silently wrong, merging two timelines that were never supposed to meet. This kata reproduces that exact corruption, byte for byte, later on.

Scope it like a senior

Before writing a class, pin the contract down out loud -- this is the conversation an interviewer wants to hear, not silence while you start typing:

Answer: two primitive operations (Insert/Delete) modeled as reversible Command objects, unbounded-but-flaggable undo depth, coalesced typing with a bounded run length, and the non-negotiable invariant that any new action invalidates the redo stack.

Reason to the design

Simplest thing that could work: remember the whole document, not the edit. Before every mutation, push a full copy of the current text onto a stack; undo pops a copy and restores it wholesale. This is the Memento pattern, and it is a completely legitimate, simpler-to-reason-about design -- the object being edited (the "originator") hands out an opaque snapshot of its own state, and undo is just "install a snapshot you were handed earlier." The trouble, as the Trap section showed, is cost: a snapshot is O(document size), taken on every single keystroke, so total memory for a growing document is O(n2), not O(n). It is simple and it is wrong at scale -- exactly the kind of design that looks fine in a demo and falls over in a real editing session.

The insight that unlocks cheap undo: don't store the document, store the edit. An insert of one character only ever needs to remember "I added this one character at this position" to be reversible -- deleting that same range restores the prior state exactly, without needing a copy of anything else in the document. A delete only needs to remember "I removed this specific substring from this position" -- re-inserting it restores the prior state. Neither operation needs to know or care what the rest of the document looked like. That is the entire idea behind the Command pattern applied to editing: model each action as an object holding just its own delta, with two methods -- execute() to (re)apply it, undo() to reverse it -- and let a stack of these objects stand in for "history," instead of a stack of document copies.

So the design is two stacks of Command objects:

Why any new action must clear the redo stack. The redo stack represents exactly one specific alternate future -- "what would happen if you replayed the steps you just undid, in that exact order, against the document as it existed right after those undos." The instant you take a different action instead, that future no longer applies to reality: the document has diverged onto a new branch, and the old commands' stored deltas (positions, lengths, deleted text) were computed against a document that no longer exists. There is no such thing as "redo, but from a different timeline" -- so the only correct move is to discard the stale branch entirely the moment a new edit happens. Concretely: after undoing "insert 't' at position 2," that command is only valid to redo if position 2 in the current document is still where it was undone from. Type anything before redoing, and that assumption breaks -- so the fix isn't "check if it's still valid," it's "there is only ever one valid future, and a new action makes it a different one." This single line -- clear the redo stack inside apply() -- is the entire correctness lesson of this kata.

Why coalescing needs a data-structure decision, not just a rule. If every keystroke pushes its own Command, typing "hello" produces 5 undo stack entries and Ctrl+Z removes it one letter at a time -- technically correct, annoying in practice. The fix is to let a still-open InsertCommand absorb the next keystroke instead of a new command being pushed, as long as three conditions hold: the new character's position is exactly adjacent to what the command has already inserted (no cursor jump happened in between), the run hasn't crossed a word boundary (typing a space after "cat" starts a fresh group -- this is what makes "undo the whole word" feel right instead of "undo the whole sentence"), and the run hasn't hit a bound (so a key held down for 500 repeats can't create one un-undoable mega-edit). Get the boundary condition backwards and the bug is invisible until someone tries to selectively undo just the last word they typed and instead loses the whole paragraph.

Generalizing: a Composite/macro command. "Replace" (select text, type over it) is not a third primitive -- it is a delete followed by an insert, and it should undo as one user-visible action, not two. A CompositeCommand wraps a list of commands: execute() runs them in order, undo() runs them in reverse order (unwind a call stack, not replay it forwards) -- get that direction backwards and undoing a replace inserts the old text on top of the new text instead of swapping them back.

Build it — milestones

Attempt-first: build against the contract above (Insert/Delete as Command objects, two stacks, redo-clears-on-new-action, coalesced typing). Try each milestone yourself before reading the reference implementation below.

Reference implementation — Java

Nine files, all plain (package-private) classes in the default package — javac *.java compiles the whole thing together, no build tooling needed. Document is the dumb receiver; Command/InsertCommand/DeleteCommand/CompositeCommand are the Command-pattern core; Editor is the correct M1–M4 answer.

/** The plain text buffer. It knows nothing about undo/redo -- that is the
 *  whole point of the Command pattern: the receiver stays dumb, the command
 *  objects carry the "how do I reverse this" knowledge. */
final class Document {
    private final StringBuilder buf = new StringBuilder();

    void insert(int pos, String s) { buf.insert(pos, s); }

    /** Deletes [pos, pos+length) and returns the removed text -- callers
     *  (DeleteCommand) need it back so undo can re-insert it. */
    String delete(int pos, int length) {
        String removed = buf.substring(pos, pos + length);
        buf.delete(pos, pos + length);
        return removed;
    }

    String text() { return buf.toString(); }
    int length() { return buf.length(); }
}
/** The core abstraction: every edit is an object that knows how to REPLAY
 *  itself (execute) and how to REVERSE itself (undo). Neither the editor nor
 *  the document ever special-cases "was this an insert or a delete" -- they
 *  just call execute()/undo() on whatever Command is on top of a stack. */
interface Command {
    void execute();
    void undo();

    /** Debug-only hook -- NOT part of the classic Command pattern. It exists
     *  purely so the break-it section can measure "how many characters of
     *  history are we holding onto right now" and compare that against the
     *  Memento approach, which has no way to answer that question cheaply. */
    int charsStored();
}
/** Inserting text at a position. Stores ONLY the inserted delta -- not a copy
 *  of the document -- which is the entire memory argument against Memento. */
final class InsertCommand implements Command {
    private final Document doc;
    private final int pos;
    private final StringBuilder text; // may grow via extend() while still "open"

    /** A single typed keystroke -- the common case, and the one that can
     *  still be coalesced with the next keystroke. */
    InsertCommand(Document doc, int pos, char c) {
        this.doc = doc;
        this.pos = pos;
        this.text = new StringBuilder().append(c);
    }

    /** A whole string inserted atomically (paste, or the insert-half of a
     *  replace) -- never coalesced with anything else. */
    InsertCommand(Document doc, int pos, String text) {
        this.doc = doc;
        this.pos = pos;
        this.text = new StringBuilder(text);
    }

    public void execute() { doc.insert(pos, text.toString()); } // first apply, and redo
    public void undo() { doc.delete(pos, text.length()); }
    public int charsStored() { return text.length(); }

    /** Real editors group a run of typing into ONE undo unit -- one Ctrl+Z
     *  removes the whole word you just typed, not one letter at a time.
     *  Returns true (and performs the physical insert of just the new
     *  character) if {@code c} can be folded into THIS still-open command:
     *  the position must be exactly adjacent to what we've inserted so far,
     *  it must not cross a word/whitespace boundary (typing "cat" then a
     *  space starts a NEW group), and the run must not already be at the
     *  bounded cap -- an unbounded coalesced run would defeat the point of
     *  granular undo (imagine holding a key down for 500 repeats). */
    static final int MAX_COALESCE_RUN = 20;

    boolean extend(Document liveDoc, int insertPos, char c) {
        if (insertPos != pos + text.length()) return false;          // not adjacent
        if (text.length() >= MAX_COALESCE_RUN) return false;          // group is full
        boolean lastIsWord = !Character.isWhitespace(text.charAt(text.length() - 1));
        boolean nextIsWord = !Character.isWhitespace(c);
        if (lastIsWord != nextIsWord) return false;                   // crossing a word boundary
        liveDoc.insert(insertPos, String.valueOf(c));                  // physically apply just the new char
        text.append(c);
        return true;
    }
}
/** Deleting a range. Stores the position/length up front, and captures the
 *  removed TEXT the moment it actually deletes it -- that captured text is
 *  the delta undo() replays back in. */
final class DeleteCommand implements Command {
    private final Document doc;
    private final int pos, length;
    private String deleted; // captured on first execute()

    DeleteCommand(Document doc, int pos, int length) {
        this.doc = doc;
        this.pos = pos;
        this.length = length;
    }

    public void execute() { deleted = doc.delete(pos, length); } // first apply, and redo
    public void undo() { doc.insert(pos, deleted); }
    public int charsStored() { return deleted == null ? 0 : deleted.length(); }
}
import java.util.List;

/** A macro: several commands that must execute/undo as ONE atomic undo unit.
 *  This is how "replace" is built without inventing a new primitive: it is
 *  literally a DeleteCommand followed by an InsertCommand, wrapped so a
 *  single undo() reverses both. The only subtlety is direction: undo() must
 *  run the parts in REVERSE order, mirroring how you'd unwind a call stack. */
final class CompositeCommand implements Command {
    private final List<Command> parts;

    CompositeCommand(List<Command> parts) { this.parts = parts; }

    public void execute() {
        for (Command c : parts) c.execute();
    }

    public void undo() {
        for (int i = parts.size() - 1; i >= 0; i--) parts.get(i).undo(); // reverse order
    }

    public int charsStored() {
        int total = 0;
        for (Command c : parts) total += c.charsStored();
        return total;
    }
}
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;

/** The correct editor. Two stacks, one invariant: ANY new action clears the
 *  redo stack. That single line (redoStack.clear() in apply()) is the whole
 *  correctness lesson of this kata -- see the break-it section for what
 *  happens the moment it goes missing. */
final class Editor {
    private final Document doc = new Document();
    private final Deque<Command> undoStack = new ArrayDeque<>();
    private final Deque<Command> redoStack = new ArrayDeque<>();

    String text() { return doc.text(); }

    void insertChar(int pos, char c) {
        if (!undoStack.isEmpty() && undoStack.peek() instanceof InsertCommand) {
            InsertCommand top = (InsertCommand) undoStack.peek();
            if (top.extend(doc, pos, c)) {
                redoStack.clear(); // still a NEW action, even though no new stack entry was pushed
                return;
            }
        }
        apply(new InsertCommand(doc, pos, c));
    }

    void insertText(int pos, String s) { apply(new InsertCommand(doc, pos, s)); } // paste: atomic, no coalescing

    void delete(int pos, int length) { apply(new DeleteCommand(doc, pos, length)); }

    /** replace = delete the old range, then insert the new text, as ONE
     *  undo unit -- a CompositeCommand, not a new primitive. */
    void replace(int pos, int length, String newText) {
        Command del = new DeleteCommand(doc, pos, length);
        Command ins = new InsertCommand(doc, pos, newText);
        apply(new CompositeCommand(List.of(del, ins)));
    }

    private void apply(Command cmd) {
        cmd.execute();
        undoStack.push(cmd);
        redoStack.clear(); // THE INVARIANT: any new action invalidates the redo timeline
    }

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

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

    /** Total characters currently held across BOTH stacks -- the Command
     *  approach's whole memory footprint. Compare against
     *  SnapshotHistory.totalSnapshotChars() in the break-it section. */
    int totalBufferedChars() {
        int total = 0;
        for (Command c : undoStack) total += c.charsStored();
        for (Command c : redoStack) total += c.charsStored();
        return total;
    }

    int undoDepth() { return undoStack.size(); }
    int redoDepth() { return redoStack.size(); }
}

Note the one line in apply() that does all the correctness work: redoStack.clear(). Delete that single line and every test in the break-it section below that checks for stale-redo corruption starts failing — that is the entire point of naming it an invariant instead of an implementation detail.

Reference implementation — Go

Same shape, one package. Save as a module named texteditor (go mod init texteditor).

module texteditor

go 1.21
// Package texteditor is the reference implementation for the "Design a Text
// Editor with Undo/Redo" LLD kata: Command objects (Execute/Undo) driving an
// undo stack and a redo stack, with coalescing and a composite/macro command.
package texteditor

// Document is the plain text buffer. It knows nothing about undo/redo --
// that is the whole point of the Command pattern: the receiver stays dumb,
// the command objects carry the "how do I reverse this" knowledge.
type Document struct {
	buf []rune
}

func (d *Document) Insert(pos int, s string) {
	r := []rune(s)
	d.buf = append(d.buf[:pos], append(append([]rune{}, r...), d.buf[pos:]...)...)
}

// Delete removes [pos, pos+length) and returns the removed text -- callers
// (DeleteCommand) need it back so Undo can re-insert it.
func (d *Document) Delete(pos, length int) string {
	removed := string(d.buf[pos : pos+length])
	d.buf = append(d.buf[:pos], d.buf[pos+length:]...)
	return removed
}

func (d *Document) Text() string { return string(d.buf) }
func (d *Document) Length() int  { return len(d.buf) }
package texteditor

// Command is the core abstraction: every edit is an object that knows how
// to REPLAY itself (Execute) and how to REVERSE itself (Undo). Neither the
// Editor nor the Document ever special-cases "was this an insert or a
// delete" -- they just call Execute/Undo on whatever Command is on top of a
// stack.
type Command interface {
	Execute()
	Undo()

	// CharsStored is a debug-only hook -- NOT part of the classic Command
	// pattern. It exists purely so the break-it section can measure "how
	// many characters of history are we holding onto right now" and compare
	// that against the Memento approach, which has no way to answer that
	// question cheaply.
	CharsStored() int
}
package texteditor

// maxCoalesceRun bounds how many keystrokes one undo group can absorb -- an
// unbounded coalesced run would defeat the point of granular undo (imagine
// holding a key down for 500 repeats and Ctrl+Z erasing all of it at once).
const maxCoalesceRun = 20

// InsertCommand inserts text at a position. It stores ONLY the inserted
// delta -- not a copy of the document -- which is the entire memory argument
// against Memento.
type InsertCommand struct {
	doc  *Document
	pos  int
	text []rune
}

// NewInsertCommand models a single typed keystroke -- the common case, and
// the one that can still be coalesced with the next keystroke.
func NewInsertCommand(doc *Document, pos int, ch rune) *InsertCommand {
	return &InsertCommand{doc: doc, pos: pos, text: []rune{ch}}
}

// NewInsertText models a whole string inserted atomically (paste, or the
// insert-half of a Replace) -- never coalesced with anything else.
func NewInsertText(doc *Document, pos int, text string) *InsertCommand {
	return &InsertCommand{doc: doc, pos: pos, text: []rune(text)}
}

func (c *InsertCommand) Execute()         { c.doc.Insert(c.pos, string(c.text)) } // first apply, and redo
func (c *InsertCommand) Undo()            { c.doc.Delete(c.pos, len(c.text)) }
func (c *InsertCommand) CharsStored() int { return len(c.text) }

func isSpace(r rune) bool { return r == ' ' || r == '\t' || r == '\n' }

// Extend folds an adjacent keystroke into this already-open command if:
// the position is exactly adjacent to what's been inserted so far, it does
// not cross a word/whitespace boundary (typing "cat" then a space starts a
// NEW group), and the run has not hit maxCoalesceRun. On success it also
// PHYSICALLY performs the insert of just the new rune.
func (c *InsertCommand) Extend(liveDoc *Document, insertPos int, ch rune) bool {
	if insertPos != c.pos+len(c.text) {
		return false // not adjacent
	}
	if len(c.text) >= maxCoalesceRun {
		return false // group is full
	}
	lastIsWord := !isSpace(c.text[len(c.text)-1])
	nextIsWord := !isSpace(ch)
	if lastIsWord != nextIsWord {
		return false // crossing a word boundary
	}
	liveDoc.Insert(insertPos, string(ch)) // physically apply just the new rune
	c.text = append(c.text, ch)
	return true
}
package texteditor

// DeleteCommand deletes a range. It stores the position/length up front and
// captures the removed TEXT the moment it actually deletes it -- that
// captured text is the delta Undo replays back in.
type DeleteCommand struct {
	doc         *Document
	pos, length int
	deleted     string // captured on first Execute()
}

func NewDeleteCommand(doc *Document, pos, length int) *DeleteCommand {
	return &DeleteCommand{doc: doc, pos: pos, length: length}
}

func (c *DeleteCommand) Execute()         { c.deleted = c.doc.Delete(c.pos, c.length) } // first apply, and redo
func (c *DeleteCommand) Undo()            { c.doc.Insert(c.pos, c.deleted) }
func (c *DeleteCommand) CharsStored() int { return len(c.deleted) }
package texteditor

// CompositeCommand is a macro: several commands that must Execute/Undo as
// ONE atomic undo unit. This is how Replace is built without inventing a new
// primitive: it is literally a DeleteCommand followed by an InsertCommand,
// wrapped so a single Undo reverses both. The only subtlety is direction:
// Undo must run the parts in REVERSE order, mirroring how you'd unwind a
// call stack.
type CompositeCommand struct {
	parts []Command
}

func NewCompositeCommand(parts ...Command) *CompositeCommand {
	return &CompositeCommand{parts: parts}
}

func (c *CompositeCommand) Execute() {
	for _, p := range c.parts {
		p.Execute()
	}
}

func (c *CompositeCommand) Undo() {
	for i := len(c.parts) - 1; i >= 0; i-- { // reverse order
		c.parts[i].Undo()
	}
}

func (c *CompositeCommand) CharsStored() int {
	total := 0
	for _, p := range c.parts {
		total += p.CharsStored()
	}
	return total
}
package texteditor

// Editor is the correct editor. Two stacks, one invariant: ANY new action
// clears the redo stack. That single line (e.redoStack = nil in apply) is
// the whole correctness lesson of this kata -- see the break-it tests for
// what happens the moment it goes missing.
type Editor struct {
	doc       *Document
	undoStack []Command
	redoStack []Command
}

func NewEditor() *Editor { return &Editor{doc: &Document{}} }

func (e *Editor) Text() string { return e.doc.Text() }

func (e *Editor) InsertChar(pos int, ch rune) {
	if n := len(e.undoStack); n > 0 {
		if top, ok := e.undoStack[n-1].(*InsertCommand); ok {
			if top.Extend(e.doc, pos, ch) {
				e.redoStack = nil // still a NEW action, even though no new stack entry was pushed
				return
			}
		}
	}
	e.apply(NewInsertCommand(e.doc, pos, ch))
}

// InsertText is a paste: atomic, never coalesced.
func (e *Editor) InsertText(pos int, s string) { e.apply(NewInsertText(e.doc, pos, s)) }

func (e *Editor) Delete(pos, length int) { e.apply(NewDeleteCommand(e.doc, pos, length)) }

// Replace = delete the old range, then insert the new text, as ONE undo
// unit -- a CompositeCommand, not a new primitive.
func (e *Editor) Replace(pos, length int, newText string) {
	del := NewDeleteCommand(e.doc, pos, length)
	ins := NewInsertText(e.doc, pos, newText)
	e.apply(NewCompositeCommand(del, ins))
}

func (e *Editor) apply(cmd Command) {
	cmd.Execute()
	e.undoStack = append(e.undoStack, cmd)
	e.redoStack = nil // THE INVARIANT: any new action invalidates the redo timeline
}

func (e *Editor) Undo() bool {
	n := len(e.undoStack)
	if n == 0 {
		return false
	}
	cmd := e.undoStack[n-1]
	e.undoStack = e.undoStack[:n-1]
	cmd.Undo()
	e.redoStack = append(e.redoStack, cmd)
	return true
}

func (e *Editor) Redo() bool {
	n := len(e.redoStack)
	if n == 0 {
		return false
	}
	cmd := e.redoStack[n-1]
	e.redoStack = e.redoStack[:n-1]
	cmd.Execute()
	e.undoStack = append(e.undoStack, cmd)
	return true
}

// TotalBufferedChars is the total characters currently held across BOTH
// stacks -- the Command approach's whole memory footprint. Compare against
// SnapshotHistory.TotalSnapshotChars in the break-it section.
func (e *Editor) TotalBufferedChars() int {
	total := 0
	for _, c := range e.undoStack {
		total += c.CharsStored()
	}
	for _, c := range e.redoStack {
		total += c.CharsStored()
	}
	return total
}

func (e *Editor) UndoDepth() int { return len(e.undoStack) }
func (e *Editor) RedoDepth() int { return len(e.redoStack) }

Same invariant, same single line: e.redoStack = nil inside apply. Everything else in Editor is bookkeeping around that one guarantee.

Break it

Two deliberately-wrong pieces reproduce the two failures from the Trap, kept ONLY so the tests below can demonstrate them against the correct Editor on identical input. Never use either in real code.

Break-it #1: the Memento approach's memory blowup, measured

SnapshotHistory is a working, correct implementation of undo via the Memento pattern — it just pays for a full copy of the document on every keystroke instead of storing a delta.

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

/** THE MEMENTO APPROACH, kept only for the break-it memory comparison below.
 *  Instead of a delta-object per edit, it snapshots the ENTIRE document
 *  before every mutation. Simple to reason about (undo = "restore the last
 *  full copy") but the memory cost is O(document length) PER KEYSTROKE, not
 *  O(1) -- that is exactly what this page's break-it measurement shows. */
final class SnapshotHistory {
    private final StringBuilder buf = new StringBuilder();
    private final Deque<String> history = new ArrayDeque<>();

    void insertChar(int pos, char c) {
        history.push(buf.toString()); // MEMENTO: capture the WHOLE document, every keystroke
        buf.insert(pos, c);
    }

    boolean undo() {
        if (history.isEmpty()) return false;
        String prev = history.pop();
        buf.setLength(0);
        buf.append(prev);
        return true;
    }

    String text() { return buf.toString(); }

    /** Sum of every full-document snapshot ever held -- grows like a
     *  triangular number (n*(n+1)/2) as the document grows by one char per
     *  keystroke, versus Command's O(n) total. */
    long totalSnapshotChars() {
        long total = 0;
        for (String s : history) total += s.length();
        return total;
    }
}
package texteditor

// SnapshotHistory is THE MEMENTO APPROACH, kept only for the break-it memory
// comparison. Instead of a delta-object per edit, it snapshots the ENTIRE
// document before every mutation. Simple to reason about (undo = "restore
// the last full copy") but the memory cost is O(document length) PER
// KEYSTROKE, not O(1) -- that is exactly what this page's break-it
// measurement shows.
type SnapshotHistory struct {
	buf     []rune
	history []string
}

func (s *SnapshotHistory) InsertChar(pos int, ch rune) {
	s.history = append(s.history, string(s.buf)) // MEMENTO: capture the WHOLE document, every keystroke
	r := append(s.buf[:pos:pos], append([]rune{ch}, s.buf[pos:]...)...)
	s.buf = r
}

func (s *SnapshotHistory) Undo() bool {
	n := len(s.history)
	if n == 0 {
		return false
	}
	prev := s.history[n-1]
	s.history = s.history[:n-1]
	s.buf = []rune(prev)
	return true
}

func (s *SnapshotHistory) Text() string { return string(s.buf) }

// TotalSnapshotChars sums every full-document snapshot ever held -- grows
// like a triangular number as the document grows by one char per keystroke,
// versus Command's O(n) total.
func (s *SnapshotHistory) TotalSnapshotChars() int {
	total := 0
	for _, h := range s.history {
		total += len(h)
	}
	return total
}

Break-it #2: forgetting to clear the redo stack, reproduced

BuggyEditor is byte-for-byte identical to Editor except for one missing line inside apply().

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

/** THE TRAP, reproduced: identical to Editor except apply() is MISSING the
 *  redoStack.clear() call. Kept here ONLY so the break-it section can
 *  demonstrate the stale-redo corruption against the correct Editor above on
 *  identical input. Never use this in real code. */
final class BuggyEditor {
    private final Document doc = new Document();
    private final Deque<Command> undoStack = new ArrayDeque<>();
    private final Deque<Command> redoStack = new ArrayDeque<>();

    String text() { return doc.text(); }

    void insertChar(int pos, char c) { apply(new InsertCommand(doc, pos, c)); } // no coalescing here -- keep the bug isolated

    private void apply(Command cmd) {
        cmd.execute();
        undoStack.push(cmd);
        // BUG: forgot `redoStack.clear();` here. A stale redo entry from a
        // previous, now-abandoned future survives this new action.
    }

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

    boolean redo() {
        if (redoStack.isEmpty()) return false;
        Command cmd = redoStack.pop();
        cmd.execute();
        undoStack.push(cmd);
        return true;
    }
}
package texteditor

// BuggyEditor is THE TRAP, reproduced: identical to Editor except apply is
// MISSING the "clear the redo stack" line. Kept here ONLY so the break-it
// tests can demonstrate the stale-redo corruption against the correct
// Editor on identical input. Never use this in real code.
type BuggyEditor struct {
	doc       *Document
	undoStack []Command
	redoStack []Command
}

func NewBuggyEditor() *BuggyEditor { return &BuggyEditor{doc: &Document{}} }

func (e *BuggyEditor) Text() string { return e.doc.Text() }

// InsertChar has no coalescing here -- keep the bug isolated from M3.
func (e *BuggyEditor) InsertChar(pos int, ch rune) { e.apply(NewInsertCommand(e.doc, pos, ch)) }

func (e *BuggyEditor) apply(cmd Command) {
	cmd.Execute()
	e.undoStack = append(e.undoStack, cmd)
	// BUG: forgot `e.redoStack = nil` here. A stale redo entry from a
	// previous, now-abandoned future survives this new action.
}

func (e *BuggyEditor) Undo() bool {
	n := len(e.undoStack)
	if n == 0 {
		return false
	}
	cmd := e.undoStack[n-1]
	e.undoStack = e.undoStack[:n-1]
	cmd.Undo()
	e.redoStack = append(e.redoStack, cmd)
	return true
}

func (e *BuggyEditor) Redo() bool {
	n := len(e.redoStack)
	if n == 0 {
		return false
	}
	cmd := e.redoStack[n-1]
	e.redoStack = e.redoStack[:n-1]
	cmd.Execute()
	e.undoStack = append(e.undoStack, cmd)
	return true
}

Compile and run all Java files together (javac *.java && java TextEditorTests):

public final class TextEditorTests {

    static int pass = 0, fail = 0;

    static void check(String name, boolean cond) {
        if (cond) { pass++; System.out.println("PASS: " + name); }
        else      { fail++; System.out.println("FAIL: " + name); }
    }

    public static void main(String[] args) {

        // --- M1: core Command execute/undo, single-level ---
        {
            Editor e = new Editor();
            e.insertText(0, "Hello");
            check("M1: insert lands", e.text().equals("Hello"));
            e.undo();
            check("M1: undo reverts the insert", e.text().equals(""));
            e.redo();
            check("M1: redo replays the insert", e.text().equals("Hello"));

            Editor d = new Editor();
            d.insertText(0, "Hello World");
            d.delete(5, 6); // remove " World"
            check("M1: delete works", d.text().equals("Hello"));
            d.undo();
            check("M1: undo restores the deleted range", d.text().equals("Hello World"));
        }

        // --- M2: redo stack + the invalidation invariant ---
        {
            Editor e = new Editor();
            e.insertText(0, "cat");
            e.undo();
            check("M2: undo empties the doc", e.text().equals(""));
            e.insertText(0, "dog"); // a NEW action while a redo was pending
            check("M2: the new action applied", e.text().equals("dog"));
            check("M2: the new action cleared the stale redo", !e.redo());
            check("M2: doc unchanged after the no-op redo", e.text().equals("dog"));
        }

        // --- M3: coalescing ---
        {
            Editor e = new Editor();
            e.insertChar(0, 'c');
            e.insertChar(1, 'a');
            e.insertChar(2, 't');
            check("M3: three keystrokes produce the right text", e.text().equals("cat"));
            check("M3: three keystrokes coalesce into ONE undo unit", e.undoDepth() == 1);
            e.undo();
            check("M3: one undo removes the whole coalesced word", e.text().equals(""));

            Editor f = new Editor();
            for (char c : "cat dog".toCharArray()) {
                f.insertChar(f.text().length(), c);
            }
            check("M3: word-boundary text is correct", f.text().equals("cat dog"));
            // "cat" | " " | "dog" -- three groups: word boundary splits at the space both times
            check("M3: whitespace boundary starts a new group", f.undoDepth() == 3);

            Editor g = new Editor();
            for (int i = 0; i < 25; i++) g.insertChar(i, 'x'); // 25 identical word-chars, no boundary
            check("M3: 25 chars land correctly", g.text().length() == 25);
            // capped at MAX_COALESCE_RUN=20 -> group1 has 20, group2 has 5
            check("M3: run cap splits at 20 into two groups", g.undoDepth() == 2);
        }

        // --- M4: generalize -- CompositeCommand (replace = delete+insert, one undo unit) ---
        {
            Editor e = new Editor();
            e.insertText(0, "Hello World");
            e.replace(6, 5, "there"); // "World" -> "there"
            check("M4: replace produces the right text", e.text().equals("Hello there"));
            e.undo();
            check("M4: one undo reverts BOTH halves of the replace atomically", e.text().equals("Hello World"));
            e.redo();
            check("M4: one redo re-applies both halves", e.text().equals("Hello there"));
        }

        // --- Break-it #1: Memento's per-keystroke full snapshot vs Command's delta ---
        {
            final int n = 20_000;
            Editor cmdEditor = new Editor();
            for (int i = 0; i < n; i++) cmdEditor.insertChar(i, (char) ('a' + i % 26));
            long cmdChars = cmdEditor.totalBufferedChars();

            SnapshotHistory snap = new SnapshotHistory();
            for (int i = 0; i < n; i++) snap.insertChar(i, (char) ('a' + i % 26));
            long snapChars = snap.totalSnapshotChars();

            double ratio = (double) snapChars / (double) cmdChars;

            System.out.println();
            System.out.printf("       Command approach:  %,d keystrokes -> %,d chars held in undo history%n", n, cmdChars);
            System.out.printf("       Memento approach:   %,d keystrokes -> %,d chars held in undo history%n", n, snapChars);
            System.out.printf("       Memento / Command ratio: %.0fx more characters retained%n", ratio);

            check("break-it: Command history is exactly O(n) -- one char per keystroke", cmdChars == n);
            check("break-it: Memento history is O(n^2) -- a full snapshot every keystroke", snapChars == (long) n * (n - 1) / 2);
            check("break-it: Memento retains at least 1000x more characters than Command on the same input", ratio > 1000.0);
        }

        // --- Break-it #2: forgetting to clear the redo stack corrupts the document ---
        {
            // Correct Editor: same operations, insertText() to isolate this from coalescing (M3).
            Editor good = new Editor();
            good.insertText(0, "c");
            good.insertText(1, "a");
            good.insertText(2, "t");           // "cat"
            good.undo();                        // removes "t" -> "ca"; redo = [insert "t" @2]
            good.insertText(2, "r");            // a NEW action while a redo is pending
            check("break-it: correct Editor clears the stale redo on a new action", !good.redo());
            check("break-it: correct Editor's doc is uncorrupted", good.text().equals("car"));

            // BuggyEditor: identical operations, but apply() forgot redoStack.clear().
            BuggyEditor bad = new BuggyEditor();
            bad.insertChar(0, 'c');
            bad.insertChar(1, 'a');
            bad.insertChar(2, 't');            // "cat"
            bad.undo();                         // removes 't' -> "ca"; redo = [insert 't' @2]
            bad.insertChar(2, 'r');             // BUG: redo NOT cleared here; text is now "car"
            boolean staleRedoStillPending = bad.redo(); // replays the STALE "insert t @2" against "car"
            System.out.println();
            System.out.println("       BuggyEditor after undo -> new action 'r' -> stale redo(): \"" + bad.text() + "\"");
            check("break-it: the bug lets a stale redo fire", staleRedoStillPending);
            check("break-it: stale redo corrupts the document (\"catr\", not \"car\")", bad.text().equals("catr"));
        }

        System.out.println();
        System.out.println(pass + " passed, " + fail + " failed");
        if (fail > 0) System.exit(1);
    }
}

Measured in this session: all 26/26 assertions pass, including both break-its:

Add this test file next to the Go sources (package texteditor) and run go test -race ./...:

package texteditor

import "testing"

func TestM1_CoreExecuteUndo(t *testing.T) {
	e := NewEditor()
	e.InsertText(0, "Hello")
	if e.Text() != "Hello" {
		t.Fatalf("insert lands: got %q", e.Text())
	}
	e.Undo()
	if e.Text() != "" {
		t.Fatalf("undo reverts insert: got %q", e.Text())
	}
	e.Redo()
	if e.Text() != "Hello" {
		t.Fatalf("redo replays insert: got %q", e.Text())
	}

	d := NewEditor()
	d.InsertText(0, "Hello World")
	d.Delete(5, 6) // remove " World"
	if d.Text() != "Hello" {
		t.Fatalf("delete works: got %q", d.Text())
	}
	d.Undo()
	if d.Text() != "Hello World" {
		t.Fatalf("undo restores deleted range: got %q", d.Text())
	}
}

func TestM2_RedoInvalidationInvariant(t *testing.T) {
	e := NewEditor()
	e.InsertText(0, "cat")
	e.Undo()
	if e.Text() != "" {
		t.Fatalf("undo empties doc: got %q", e.Text())
	}
	e.InsertText(0, "dog") // a NEW action while a redo was pending
	if e.Text() != "dog" {
		t.Fatalf("new action applied: got %q", e.Text())
	}
	if e.Redo() {
		t.Fatalf("new action should have cleared the stale redo")
	}
	if e.Text() != "dog" {
		t.Fatalf("doc unchanged after the no-op redo: got %q", e.Text())
	}
}

func TestM3_Coalescing(t *testing.T) {
	e := NewEditor()
	e.InsertChar(0, 'c')
	e.InsertChar(1, 'a')
	e.InsertChar(2, 't')
	if e.Text() != "cat" {
		t.Fatalf("three keystrokes produce the right text: got %q", e.Text())
	}
	if e.UndoDepth() != 1 {
		t.Fatalf("three keystrokes should coalesce into ONE undo unit, got depth %d", e.UndoDepth())
	}
	e.Undo()
	if e.Text() != "" {
		t.Fatalf("one undo should remove the whole coalesced word: got %q", e.Text())
	}

	f := NewEditor()
	for _, c := range "cat dog" {
		f.InsertChar(len(f.Text()), c)
	}
	if f.Text() != "cat dog" {
		t.Fatalf("word-boundary text: got %q", f.Text())
	}
	if f.UndoDepth() != 3 { // "cat" | " " | "dog"
		t.Fatalf("whitespace boundary should start a new group, got depth %d", f.UndoDepth())
	}

	g := NewEditor()
	for i := 0; i < 25; i++ {
		g.InsertChar(i, 'x') // 25 identical word-chars, no boundary
	}
	if len(g.Text()) != 25 {
		t.Fatalf("25 chars should land, got %d", len(g.Text()))
	}
	if g.UndoDepth() != 2 { // capped at 20 -> group1=20, group2=5
		t.Fatalf("run cap should split at 20 into two groups, got depth %d", g.UndoDepth())
	}
}

func TestM4_CompositeReplace(t *testing.T) {
	e := NewEditor()
	e.InsertText(0, "Hello World")
	e.Replace(6, 5, "there") // "World" -> "there"
	if e.Text() != "Hello there" {
		t.Fatalf("replace produces right text: got %q", e.Text())
	}
	e.Undo()
	if e.Text() != "Hello World" {
		t.Fatalf("one undo should revert both halves atomically: got %q", e.Text())
	}
	e.Redo()
	if e.Text() != "Hello there" {
		t.Fatalf("one redo should re-apply both halves: got %q", e.Text())
	}
}

// TestBreakIt_MementoVsCommandMemory reproduces failure (a): a full-snapshot-
// per-keystroke undo history (Memento) uses O(n^2) characters of memory for
// n sequential keystrokes, versus Command's O(n).
func TestBreakIt_MementoVsCommandMemory(t *testing.T) {
	const n = 20000

	cmdEditor := NewEditor()
	for i := 0; i < n; i++ {
		cmdEditor.InsertChar(i, rune('a'+i%26))
	}
	cmdChars := cmdEditor.TotalBufferedChars()

	snap := &SnapshotHistory{}
	for i := 0; i < n; i++ {
		snap.InsertChar(i, rune('a'+i%26))
	}
	snapChars := snap.TotalSnapshotChars()

	ratio := float64(snapChars) / float64(cmdChars)
	t.Logf("Command approach: %d keystrokes -> %d chars held", n, cmdChars)
	t.Logf("Memento approach: %d keystrokes -> %d chars held", n, snapChars)
	t.Logf("Memento/Command ratio: %.0fx more characters retained", ratio)

	if cmdChars != n {
		t.Errorf("Command history should be exactly O(n): got %d, want %d", cmdChars, n)
	}
	wantSnap := n * (n - 1) / 2
	if snapChars != wantSnap {
		t.Errorf("Memento history should be the triangular number: got %d, want %d", snapChars, wantSnap)
	}
	if ratio <= 1000.0 {
		t.Errorf("Memento should retain at least 1000x more characters than Command, got %.1fx", ratio)
	}
}

// TestBreakIt_StaleRedoCorruption reproduces failure (b): forgetting to
// clear the redo stack on a new action lets a stale future replay against a
// document it was never designed for, corrupting it.
func TestBreakIt_StaleRedoCorruption(t *testing.T) {
	// Correct Editor: InsertText isolates this from the M3 coalescing feature.
	good := NewEditor()
	good.InsertText(0, "c")
	good.InsertText(1, "a")
	good.InsertText(2, "t") // "cat"
	good.Undo()             // removes "t" -> "ca"; redo = [insert "t" @2]
	good.InsertText(2, "r") // a NEW action while a redo is pending
	if good.Redo() {
		t.Errorf("correct Editor should have cleared the stale redo on the new action")
	}
	if good.Text() != "car" {
		t.Errorf("correct Editor's doc should be uncorrupted, got %q", good.Text())
	}

	// BuggyEditor: identical shape of operations, but apply() forgot to clear redo.
	bad := NewBuggyEditor()
	bad.InsertChar(0, 'c')
	bad.InsertChar(1, 'a')
	bad.InsertChar(2, 't') // "cat"
	bad.Undo()             // removes 't' -> "ca"; redo = [insert 't' @2]
	bad.InsertChar(2, 'r') // BUG: redo NOT cleared; text is now "car"
	staleRedoFired := bad.Redo()
	t.Logf("BuggyEditor after undo -> new action 'r' -> stale redo(): %q", bad.Text())
	if !staleRedoFired {
		t.Errorf("expected the bug to let a stale redo fire")
	}
	if bad.Text() != "catr" {
		t.Errorf("expected the stale redo to corrupt the document into \"catr\", got %q", bad.Text())
	}
}

Measured in this session: gofmt -l . is clean, go build ./... and go vet ./... are clean, and go test -race ./... reports 6/6 tests pass, zero races — including TestBreakIt_MementoVsCommandMemory (logs the identical 20,000-char vs 199,990,000-char, 10,000× result as Java) and TestBreakIt_StaleRedoCorruption (logs the identical "catr" corruption as Java).

Optimise — with trade-offs

DecisionOption AOption BWhen A winsWhen B wins
History representationCommand (delta) — store only what changed, replay/reverse itMemento (full snapshot) — store a complete copy of the object's state before each changeEdits are small relative to the object's size (a text edit vs. a whole document) — the common case for editors, and the only design that stays O(1) per edit instead of O(size). Requires knowing how to compute and apply a reverse delta, which is genuine design work per operation typeThe object's internal structure is complex/opaque and you don't want the history mechanism to know how to reverse individual operations (e.g. a deeply nested game-state object) — Memento only needs the originator to produce/consume an opaque blob, no per-operation undo logic to get right. Pay for it in memory, exactly as measured above (10,000× more characters retained on identical input)
Coalescing typed runsCoalesce into word-bounded, capped groups (this kata's InsertCommand.extend)One Command per keystroke, no coalescingInteractive typing — users expect Ctrl+Z to remove "the word I just typed," not one letter. Costs a small amount of extra logic (adjacency + boundary + cap checks) in exchange for a dramatically smaller undo stack (one entry per word instead of one per keystroke) and a UX match to real editorsProgrammatic/scripted edits (find-and-replace across a file, an API applying a patch) where each edit is already a deliberate, discrete unit that should be independently undoable — coalescing would incorrectly merge unrelated edits into one undo step
Undo history depthUnbounded (grow forever within the session)Bounded (a ring buffer / max-N-entries cap, e.g. VS Code's default undo limit)Short-to-medium editing sessions where memory for the delta-based history is already small (this kata's whole argument: Command history is O(edits), not O(document size²)) — unbounded is simplest and the cost is genuinely lowVery long-running sessions (a document open for days, a REPL history) where even O(edits) eventually adds up — a bounded ring buffer caps worst-case memory at a known constant, at the cost of a hard "can't undo past this point" ceiling users occasionally hit
Single-document, single-user vs. collaborativeCommand pattern with local undo/redo stacks (this kata)Operational Transformation (OT) or CRDTs for concurrent multi-user editingOne user, one document, no concurrent writers — the two-stack design is simple, correct, and exactly matches the problem. This is the right default and the right interview answer unless collaboration is explicitly asked forMultiple users edit the SAME document concurrently (Google Docs, Figma-style collab) — a local undo stack has no idea what a remote peer just inserted three characters to your left, so "undo my last edit" needs to be transformed against every concurrent remote edit to still land in the right place. OT computes that transform against a central sequence of operations (Google Docs' original approach); CRDTs sidestep the transform by making every operation commutative/mergeable by construction (better for peer-to-peer, no central server required, at the cost of more complex per-character metadata — e.g. Logoot/RGA-style unique stable IDs per character)

Why Memento is still worth knowing, not just a strictly-worse option: it earns its keep the moment the operations you'd need to reverse are hard to invert cleanly — a spreadsheet recalculation cascading through hundreds of dependent cells, or a graphics transform pipeline with lossy intermediate steps. Command asks "can you cheaply describe the reverse of this operation?" and for a text editor the answer is a trivial yes (insert↔delete). For a system where that answer is "not really, or only by re-deriving expensive state," a snapshot is often less code and less risk than getting dozens of bespoke undo() implementations exactly right. The two patterns are not competitors so much as a decision that follows directly from how cheap your deltas are to compute.

Defend under drilling

You can now defend

Re-authored/Deepened for this guide. Related theory: Command Pattern and Memento Pattern. Reference implementations (Java + Go) compiled and tested in-session: javac clean (JDK 9+ toolchain), 26/26 assertions pass including both break-its (the measured 10,000× Memento-vs-Command memory ratio on 20,000 keystrokes, and the reproduced "catr" stale-redo corruption); gofmt/go build/go vet clean, go test -race passes 6/6 with zero races, logging the identical measured results.

🤖 Don't fully get this? Learn it with Claude

Stuck on Design a Text Editor with Undo/Redo? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🎨 Explain it visually

Build the mental picture, not memorization.

I just read a lesson on **Design a Text Editor with Undo/Redo** (Hands-On Builds) and want to truly understand it. Explain Design a Text Editor with Undo/Redo from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🤔 Walk me through it (interactive)

Socratic — adapts to where you're stuck.

Teach me **Design a Text Editor with Undo/Redo** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧪 Quiz me & fix my gaps

Active recall exposes what you missed.

Quiz me on **Design a Text Editor with Undo/Redo** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧠 Make it stick

Intuition + hook + flashcards for long-term memory.

Help me remember **Design a Text Editor with Undo/Redo** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Design the Snake Game