Design a text editor with undo and redo

“Design a text editor that supports typing, deleting, undo and redo.” Then: “what happens to memory when the file is large?”

Every editor has undo: press it, and your last change disappears. Redo brings it back. It feels simple, but a good undo needs answers to several questions. What does a delete have to remember, so it can be undone? Why should one undo remove a word, not a letter? How much history can we keep, when one paste can be a megabyte? And how do we keep typing fast in a large file?

The core idea is the Command pattern, where every action is an object that can do and undo itself (the Command page shows the basic shape). This problem is about everything around that idea that makes an editor feel right and stay fast.

The framework

1. 01Answer
2. 02Scope
3. 03Build
4. 04Full design
5. 05Stress
6. 06Wrap up

The answer in one minute

If you only have a minute, this is the design. The rest of the page explains how we get here.

1. Each edit is a command that holds only what changed. An insert holds its text and position. A delete holds the text it removed. Undo does the opposite of the edit, and nothing copies the whole document.
2. History is two stacks: undo and redo. A new edit clears redo, because those edits were made to a text that no longer exists.
3. Typing joins into one undo step, until a space, a pause, or a cursor move ends it. A paste is always its own step. History is limited by characters held, not by number of steps.
4. The text lives behind a TextBuffer interface. A gap buffer keeps an empty space at the cursor, so typing and backspace don’t move any other characters.
5. Autosave copies the text under a lock, writes it outside the lock, and saves by version. So text typed during a save is never marked as saved.

We’ll build this in four stages, then add autosave on another thread.

Scope it

Before drawing anything, we ask a few questions. Each answer changes a class. Anything that doesn’t, we assume and move on.

Interviewerminute 0

Design a text editor with undo and redo.

What they are testing

Whether you pin down which operations, and how big the documents are. “Plain text, one cursor, files up to a few megabytes” points the interview at the history and the buffer. Without it, candidates drift into fonts, drawing the screen, and plugins.

Here are the questions that matter:

• Rich text or plain text? Plain text. Rich text adds formatting, and edits that change style.
• One cursor, or selections too? One cursor. Selections come up at the end.
• How big are documents? Up to a few megabytes. Gigabyte logs need a different structure.
• How much undo history? As much as fits in a memory limit, keeping the newest.
• Does it save in the background? Yes, autosave runs on another thread.

These answers give us one promise that matters more than the others: an edit costs the size of the change, not the size of the document, both to make and to remember. Two smaller promises come with it. Undo and redo are exact: undoing everything gives back the original text. And the editor never says text is saved unless that text is on disk.

We leave out the screen, fonts, key bindings, and several people editing at once.

Go deeperThree more questions, and what each changes1 min

Question	We assume	If the answer were different
Several people editing at once?	No	Collaborative editing needs OT or CRDTs: a different design
Undo across a save and reopen?	No, history is in memory	Save the history with the file, as some editors do
Find and replace?	Out of scope	“Replace all” is one compound command holding many edits

Common mistake

Starting with the user interface

Key bindings, menus and drawing text are where an editor’s code spends most of its lines, and none of it is what’s being asked. The interview is about the model underneath: the text, the cursor and the history. Say the screen calls type, backspace, undo and redo, and move on.

Build it

We’ll build the design in four stages. Each stage adds only the classes that a new requirement needs. In each diagram, the new parts are outlined, and the colors show what each class does (the key is under every diagram). Time comes from a clock the editor is given, so the tests can control it.

Stage 1: A snapshot before every edit

Interviewerminute 3

Start simple: typing, backspace and undo. What’s the quickest version that works?

What they are testing

Whether you can build the obvious version fast, and then put numbers on what’s wrong with it. “A copy per keystroke” is easy to say. “A megabyte file and ten thousand keystrokes is ten gigabytes” shows you’ve thought about it.

Start with the smallest thing that works. The text is a string, and the cursor is a position in it. Before every edit, we push a copy of the whole text onto a stack. Undo takes the last copy off the stack and puts it back. Saving a whole copy of the state like this is the Memento pattern.

Stage 1: an editor with snapshots

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation
• New in this step

JEditor.javaPyeditor.pyC#Editor.csGoeditor.goTSeditor.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// The text is a String, and undo keeps a copy of the whole text from before every edit.
class Editor {
    private String text = "";
    private int cursor;
    private final Deque<String> snapshots = new ArrayDeque<>();

    // flaw 1: every keystroke copies the whole text twice, once to build the new String and once
    // onto the undo stack. A 1 MB file and 10,000 keystrokes hold 10 GB of copies.
    // flaw 2: each keystroke is its own undo step, so undoing a sentence takes a press per letter.
    void type(String s) {
        snapshots.push(text);
        text = text.substring(0, cursor) + s + text.substring(cursor);
        cursor += s.length();
    }

    void backspace() {
        if (cursor == 0) return;
        snapshots.push(text);
        text = text.substring(0, cursor - 1) + text.substring(cursor);
        cursor--;
    }

    void moveCursor(int to) { cursor = Math.max(0, Math.min(to, text.length())); }

    // flaw 3: the cursor isn't put back where the edit was, and there is no redo: the text that
    // was undone is gone.
    boolean undo() {
        if (snapshots.isEmpty()) return false;
        text = snapshots.pop();
        cursor = Math.min(cursor, text.length());
        return true;
    }

    String text() { return text; }

    int cursor() { return cursor; }
}

It works, but it has three problems, and we leave them in on purpose. Every keystroke copies the whole text twice: once to build the new string, and once onto the stack. A 1 MB file and 10,000 keystrokes hold 10 GB. Every keystroke is its own undo step, so undoing a sentence takes one press per letter. And undo doesn’t put the cursor back where the edit was, and there’s no redo, because the undone text is thrown away.

Stage 2: Edits as commands, on two stacks

Interviewerminute 6

Make undo cheap, and add redo. What does each undo step store?

What they are testing

Whether you store edits instead of whole states, and know what a delete must keep. The red flag is a delete command that stores only a position and a length: it can’t put back what it removed.

We store what changed, instead of what the text was. An Edit is a command that can apply itself to the text, and revert itself (undo what it did). It also says where the cursor goes after each. There are two kinds:

• Insert(at, text) applies by inserting the text, and reverts by deleting the same number of characters at the same place.
• Delete(at, removed) applies by deleting, and reverts by inserting removed back. It keeps the removed characters, read from the text before the delete, because nothing else will have them afterwards.

An edit holds only its own characters, so typing one letter into a megabyte file costs one letter of history.

History keeps two stacks. Recording an edit pushes it on the undo stack. Undo takes it off, reverts it, and pushes it on the redo stack. Redo takes it off the redo stack, applies it again, and pushes it back on undo.

A new edit clears redo. Why? The edits on the redo stack were made to a version of the text that the new edit has just replaced. Applying them now would put characters in the wrong places.

Sequence: type, undo, redo, then a new edit

Scroll or pinch to zoom, drag to pan

• Color key
• Entity
• Facade

The text now sits behind a TextBuffer interface, with insert, delete, slice and length. For now, a simple buffer wraps a string builder. Stage 4 replaces it without touching anything else.

Go deeperFollowing a short session through both stacks2 min

Let’s follow a few keystrokes, with the text, the undo stack and the redo stack after each. Assume each edit is its own step for now; stage 3 joins them.

1. Type “cat”. One Insert(0, "cat"). Text: cat. Undo: [Insert "cat"]. Redo: empty.
2. Backspace twice. The first backspace removes “t”, so the edit is Delete(2, "t"). The second removes “a”: Delete(1, "a"). Text: c. Undo has three edits. Notice that each delete reads the character before removing it. That’s what lets it be undone.
3. Undo. The top edit, Delete(1, "a"), reverts by inserting “a” at position 1. Text: ca. That edit moves to redo.
4. Undo again. Delete(2, "t") puts “t” back. Text: cat. Redo now holds both deletes.
5. Redo. Delete(2, "t") applies again. Text: ca. It moves back to undo.
6. Type “r”. A new edit, Insert(2, "r"). Text: car. Redo is cleared. Its last edit, Delete(1, "a"), was planned for the text ca, and the text is now car. Applying it would remove the “a” from “car”, which the user never asked for.

At no point did anything copy the whole text. Each step touched one or two characters.

Stage 2: commands, history and a buffer

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation
• New in this step

JEditor.javaPyeditor.pyC#Editor.csGoeditor.goTSeditor.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// What the editor needs from the text, whatever holds it. A faster one can be swapped in
// without touching the editor.
interface TextBuffer {
    void insert(int at, String text);
    void delete(int at, int length);
    String slice(int from, int to);
    int length();
    String text();
}

class SimpleBuffer implements TextBuffer {
    private final StringBuilder chars = new StringBuilder();

    public void insert(int at, String text) { chars.insert(at, text); }
    public void delete(int at, int length) { chars.delete(at, at + length); }
    public String slice(int from, int to) { return chars.substring(from, to); }
    public int length() { return chars.length(); }
    public String text() { return chars.toString(); }
}

// An edit is a command: it can apply itself and undo itself, and it says where the cursor goes
// either way. It holds only what changed, not a copy of the text.
interface Edit {
    void apply(TextBuffer buffer);
    void revert(TextBuffer buffer);
    int cursorAfterApply();
    int cursorAfterRevert();
}

record Insert(int at, String text) implements Edit {
    public void apply(TextBuffer b) { b.insert(at, text); }
    public void revert(TextBuffer b) { b.delete(at, text.length()); }
    public int cursorAfterApply() { return at + text.length(); }
    public int cursorAfterRevert() { return at; }
}

// A delete must remember what it removed, or it couldn't put it back.
record Delete(int at, String removed) implements Edit {
    public void apply(TextBuffer b) { b.delete(at, removed.length()); }
    public void revert(TextBuffer b) { b.insert(at, removed); }
    public int cursorAfterApply() { return at; }
    public int cursorAfterRevert() { return at + removed.length(); }
}

// Two stacks. Undo moves the newest edit to the redo stack; redo moves it back. A new edit
// clears redo, because the edits on it were made to a text that no longer exists.
class History {
    private final Deque<Edit> undo = new ArrayDeque<>();
    private final Deque<Edit> redo = new ArrayDeque<>();

    void record(Edit e) {
        redo.clear();
        undo.push(e);
    }

    Edit undo() {
        Edit e = undo.poll();
        if (e != null) redo.push(e);
        return e;
    }

    Edit redo() {
        Edit e = redo.poll();
        if (e != null) undo.push(e);
        return e;
    }
}

class Editor {
    private final TextBuffer buffer;
    private final History history;
    private int cursor;

    Editor(TextBuffer buffer, History history) {
        this.buffer = buffer;
        this.history = history;
    }

    void type(String text) { run(new Insert(cursor, text)); }

    void backspace() {
        if (cursor > 0) run(new Delete(cursor - 1, buffer.slice(cursor - 1, cursor)));
    }

    void moveCursor(int to) { cursor = Math.max(0, Math.min(to, buffer.length())); }

    boolean undo() {
        Edit e = history.undo();
        if (e == null) return false;
        e.revert(buffer);
        cursor = e.cursorAfterRevert();
        return true;
    }

    boolean redo() {
        Edit e = history.redo();
        if (e == null) return false;
        e.apply(buffer);
        cursor = e.cursorAfterApply();
        return true;
    }

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

    int cursor() { return cursor; }

    private void run(Edit e) {
        e.apply(buffer);
        cursor = e.cursorAfterApply();
        history.record(e);
    }
}

Stage 3: Undo steps a person expects

Interviewerminute 12

A user types a sentence and presses undo. It removes one letter. Then they paste a 50 MB log file, and the editor’s memory doubles. Fix both.

What they are testing

Whether you join edits by a rule you can state, and limit the history by what it holds, not by how many steps. A candidate who caps history at “100 steps” has to explain why 100 pastes of 50 MB is fine.

Joining edits. When an edit is recorded, it may join the edit on top of the undo stack, instead of becoming a new step. This is called merging. Each edit decides whether it can absorb the next one:

• An insert absorbs a one-character insert right after it, unless the text so far ends in a space or a new line. So typing “hello world” gives two steps, “hello “ and “world”, which is how most editors behave.
• A delete absorbs a backspace right before it, so holding backspace down is one step.

The history adds two conditions of its own. The edit must come within a merge window (one second here) of the last one, so a pause ends the step. And the top step must not be sealed. Moving the cursor, pasting and undoing all seal it, because typing after any of them is a new thought. A paste seals before and after itself, so it’s always exactly one step.

The limit. Each edit has a weight: the number of characters it holds. The history keeps a running total. When a new edit pushes it over the limit, the history drops the oldest edits, from the bottom of the undo stack, until it fits. The newest edit always stays, even if it alone is over the limit, so the last thing the user did can always be undone.

Stage 3: typing 'hello world' with a pause, then a cursor move

Scroll or pinch to zoom, drag to pan

• Color key
• Value object

The undo stack becomes a double-ended queue (a list you can add to or remove from at both ends), because the limit removes from the bottom while undo removes from the top.

Stage 3: merging and a bounded history

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation
• New in this step

JHistory.javaPyhistory.pyC#History.csGohistory.goTShistory.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// One change to the text, as an object that can be done and undone (the Command pattern). The
// history stores edits, not copies of the text, so a long history stays small.
interface Edit {
    void apply(TextBuffer buffer);
    void revert(TextBuffer buffer);
    // Where the cursor goes after the edit is done (on redo), and after it is undone.
    int cursorAfterApply();
    int cursorAfterRevert();

    // The edit that does this one and then next, if the two read as one step to a person, or
    // null if they don't.
    Edit mergedWith(Edit next);

    // Characters held, which is what the history's limit counts.
    int weight();
}

// Text typed or pasted at a position. Undoing it deletes the same characters again.
record Insert(int at, String text) implements Edit {
    public void apply(TextBuffer b) { b.insert(at, text); }
    public void revert(TextBuffer b) { b.delete(at, text.length()); }
    public int cursorAfterApply() { return at + text.length(); }
    public int cursorAfterRevert() { return at; }
    public int weight() { return text.length(); }

    // A keystroke right after the last one joins it, until a space or newline ends the word:
    // "hello world" undoes as "world", then "hello ".
    public Edit mergedWith(Edit next) {
        if (!(next instanceof Insert i) || i.at != at + text.length() || i.text.length() != 1) return null;
        if (Character.isWhitespace(text.charAt(text.length() - 1))) return null;
        return new Insert(at, text + i.text);
    }
}

// Characters removed at a position. It keeps the removed text, so undo can put it back.
record Delete(int at, String removed) implements Edit {
    public void apply(TextBuffer b) { b.delete(at, removed.length()); }
    public void revert(TextBuffer b) { b.insert(at, removed); }
    public int cursorAfterApply() { return at; }
    public int cursorAfterRevert() { return at + removed.length(); }
    public int weight() { return removed.length(); }

    // A backspace right before the last one joins it: holding backspace is one step.
    public Edit mergedWith(Edit next) {
        if (!(next instanceof Delete d) || d.at + d.removed.length() != at) return null;
        return new Delete(d.at, d.removed + removed);
    }
}

// Merges edits that a person thinks of as one, and keeps at most limit characters of history,
// dropping the oldest edits first.
class History {
    private final Deque<Edit> undo = new ArrayDeque<>();
    private final Deque<Edit> redo = new ArrayDeque<>();
    private final LongSupplier clock;
    private final long mergeWindowMillis;
    private final int limit;
    private int weight;          // characters held on the undo stack
    private long lastEditAt;
    private boolean sealed = true;  // the top edit is closed to merging

    History(LongSupplier clock, long mergeWindowMillis, int limit) {
        this.clock = clock;
        this.mergeWindowMillis = mergeWindowMillis;
        this.limit = limit;
    }

    // Typing after a pause starts a new step, and so does typing after anything that sealed the
    // last one.
    void record(Edit e) {
        redo.clear();
        long now = clock.getAsLong();
        Edit top = undo.peek();
        Edit merged = !sealed && top != null && now - lastEditAt <= mergeWindowMillis ? top.mergedWith(e) : null;
        if (merged != null) {
            undo.pop();
            weight -= top.weight();
            e = merged;
        }
        push(e);
        lastEditAt = now;
        sealed = false;
    }

    // Closes the newest step, so the next edit starts a new one. Moving the cursor, pasting and
    // undoing all seal: typing after them is a new thought.
    void seal() { sealed = true; }

    // Moves the newest step to the redo stack. Any new edit clears redo, in record.
    Edit undo() {
        seal();
        Edit e = undo.poll();
        if (e == null) return null;
        weight -= e.weight();
        redo.push(e);
        return e;
    }

    Edit redo() {
        seal();
        Edit e = redo.poll();
        if (e != null) push(e);
        return e;
    }

    // The newest edit always stays, even alone over the limit; older ones go until it fits.
    private void push(Edit e) {
        undo.push(e);
        weight += e.weight();
        while (weight > limit && undo.size() > 1) weight -= undo.removeLast().weight();
    }
}

// What the keyboard calls. Every change goes through run, which applies the edit, moves the
// cursor and records it in the history, all in one place.
class Editor {
    private final TextBuffer buffer;
    private final History history;
    private int cursor;

    Editor(TextBuffer buffer, History history) {
        this.buffer = buffer;
        this.history = history;
    }

    void type(String text) { run(new Insert(cursor, text)); }

    // A paste is one step of its own: it never joins the typing before or after it.
    void paste(String text) {
        history.seal();
        run(new Insert(cursor, text));
        history.seal();
    }

    // Removes the character before the cursor, and keeps it so undo can bring it back.
    void backspace() {
        if (cursor > 0) run(new Delete(cursor - 1, buffer.slice(cursor - 1, cursor)));
    }

    // Kept inside the text. Moving the cursor ends the current undo step.
    void moveCursor(int to) {
        cursor = Math.max(0, Math.min(to, buffer.length()));
        history.seal();
    }

    // Reverts the newest step and puts the cursor back where that step began.
    boolean undo() {
        Edit e = history.undo();
        if (e == null) return false;
        e.revert(buffer);
        cursor = e.cursorAfterRevert();
        return true;
    }

    // Does the step again and puts the cursor after it.
    boolean redo() {
        Edit e = history.redo();
        if (e == null) return false;
        e.apply(buffer);
        cursor = e.cursorAfterApply();
        return true;
    }

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

    int cursor() { return cursor; }

    private void run(Edit e) {
        e.apply(buffer);
        cursor = e.cursorAfterApply();
        history.record(e);
    }
}

Common mistake

Merging in the editor instead of in the edits

Putting “if the last edit was an insert at the cursor and the time is close” in Editor.type works for typing, and then has to be written again for backspace, forward delete, and every new kind of edit. Asking the edit mergedWith(next) keeps each rule next to the data it reads, and the history only decides when merging is allowed at all.

Go deeperLimit by steps, or by characters held1 min

	A number of steps	Characters held (our choice)
Memory limit	None: one step can be huge	Yes, within one edit
Easy for the user to predict	“100 undos”	“about the last N characters of changes”
Cost to track	A count	A running sum, updated on push and drop
What a huge paste does	Takes one of the 100 slots	Pushes older history out

Some editors use both: a step count that’s easy to predict, and a size limit as a safety net.

Stage 4: A buffer that doesn’t copy on every keystroke

Interviewerminute 18

History is cheap now, but each keystroke still inserts into a string builder in the middle of a 4 MB file. What does that cost, and what would you use instead?

What they are testing

Whether you know that inserting into the middle of an array moves everything after it, and can describe one structure that avoids it. A gap buffer is the expected answer for one cursor. Knowing that piece tables and ropes exist, and when they win, is the senior part.

A string builder is an array. Inserting a character in the middle shifts every character after it by one place. So typing near the top of a 4 MB file moves up to 4 MB per keystroke. But people type at one place for a long time, and a gap buffer takes advantage of that.

The text is one array, with an empty gap at the cursor. Typing writes into the gap from the left, and the gap shrinks. Backspace makes the gap wider. Neither moves any other character. Moving the cursor moves the gap, which copies only the characters between the old position and the new one. When the gap runs out, the array doubles in size, so growing is rare.

Stage 4: a gap buffer holding 'hello world' with the cursor after 'hello'

Scroll or pinch to zoom, drag to pan

• Color key
• Implementation

GapBuffer is a second implementation of TextBuffer. So the editor, the edits and the history don’t change, because each edit already talks to the buffer only through insert, delete and slice. Swapping one implementation for another behind an interface is the Strategy pattern, and the interface from stage 2 is what makes it free now.

Go deeperFollowing the gap as you type and move2 min

Say the array has room for 16 characters and holds hello world, with the cursor after hello. The 11 characters are split around a gap of 5 empty slots: hello on the left, then the gap, then world on the right.

1. Type “,” The comma goes into the first slot of the gap. The gap is now 4 slots. Nothing else moved. Text: hello, world.
2. Backspace. The gap simply grows back by one slot. The comma is still in memory, but it’s inside the gap now, so it doesn’t count. Nothing moved.
3. Move the cursor to the end. The gap must move to the end. The 6 characters of world are copied from the right of the gap to its left. That’s 6 characters, not the whole file.
4. Type “!” five times, then once more. The first five fill the gap. The sixth finds no room, so the array doubles to 32 slots and the text is copied once. Then typing carries on, free again.

So the cost of typing is the distance the cursor moved since the last edit, plus a rare copy when the array grows. For a person typing, that’s almost always tiny.

Stage 4: a second buffer behind the same interface

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation
• New in this step

JGapBuffer.javaPygap_buffer.pyC#GapBuffer.csGogap_buffer.goTSgap-buffer.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// A gap buffer: the text in one array with an empty gap at the cursor. Typing fills the gap from
// the left, and backspace widens it, so neither moves any other character. Moving the cursor
// moves the gap, copying only the characters between the old and new position. Editors type at
// one place for a long time, which is why Emacs uses this.
class GapBuffer implements TextBuffer {
    private char[] chars = new char[16];
    private int gapStart;            // first empty slot
    private int gapEnd = chars.length;  // first slot after the gap

    public void insert(int at, String text) {
        moveGap(at);
        if (text.length() > gapEnd - gapStart) grow(text.length());
        text.getChars(0, text.length(), chars, gapStart);
        gapStart += text.length();
    }

    // The deleted characters are left in place and become part of the gap.
    public void delete(int at, int length) {
        moveGap(at);
        gapEnd += length;
    }

    // Positions after the gap are shifted by the gap's width.
    public String slice(int from, int to) {
        StringBuilder out = new StringBuilder(to - from);
        for (int i = from; i < to; i++) out.append(chars[i < gapStart ? i : i + gapEnd - gapStart]);
        return out.toString();
    }

    public int length() { return chars.length - (gapEnd - gapStart); }

    public String text() {
        return new String(chars, 0, gapStart) + new String(chars, gapEnd, chars.length - gapEnd);
    }

    private void moveGap(int at) {
        if (at < gapStart) {  // move the characters between at and the gap to after the gap
            int n = gapStart - at;
            System.arraycopy(chars, at, chars, gapEnd - n, n);
            gapStart -= n;
            gapEnd -= n;
        } else if (at > gapStart) {  // move the characters after the gap to before it
            int n = at - gapStart;
            System.arraycopy(chars, gapEnd, chars, gapStart, n);
            gapStart += n;
            gapEnd += n;
        }
    }

    // Doubling keeps growth rare: typing n characters copies the text O(log n) times in all.
    private void grow(int needed) {
        int tail = chars.length - gapEnd;
        char[] bigger = new char[Math.max(chars.length * 2, length() + needed + 16)];
        System.arraycopy(chars, 0, bigger, 0, gapStart);
        System.arraycopy(chars, gapEnd, bigger, bigger.length - tail, tail);
        gapEnd = bigger.length - tail;
        chars = bigger;
    }
}

Go deeperGap buffer, piece table or rope2 min

Buffer	Type at the cursor	Jump far, then type	Strength	Used by
String or array	O(n)	O(n)	Simplest	Small text fields
Gap buffer	O(1) on average	O(distance moved)	Fast typing at one place, simple code	Emacs
Piece table	O(pieces)	O(pieces)	Original file never copied; undo is cheap	VS Code, Word
Rope	O(log n)	O(log n)	Fast everywhere, many cursors, huge files	Xi, some IDEs

When would you pick a piece table over a gap buffer? When files are large, and opened mostly to read or to make small changes. A piece table never copies the original file. It keeps it read-only, adds new text to the end of a second buffer, and describes the document as a list of pieces pointing into the two. Opening a 1 GB log is instant. And every version of the document is just a different list of pieces, which makes undo cheap too.

A rope is a balanced tree of short strings. Every operation costs O(log n), wherever the cursor is, which suits many cursors and very large files, at the price of more complex code.

This is enough for a mid-level answer. Edits as commands with what they need to undo, two stacks, redo cleared on a new edit, and typing merged into steps. The rest of the page is what makes it a senior answer.

The full design

Here is everything together. Editor is what the screen calls. History decides what one undo step is. Each Edit knows how to do and undo itself, and TextBuffer hides how the text is stored. SharedEditor lets an autosave thread read the editor safely.

Text editor: full class diagram

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation

</>text-editor-undo· read only

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

Explorer

• JAllInOne.java
• src
• JDelete.java
• JEdit.java
• JEditor.java
• JGapBuffer.java
• JHistory.java
• JInsert.java
• JSharedEditor.java
• JSnapshot.java
• JTextBuffer.java

JAllInOne.java

AllInOne.javasrc/Delete.javasrc/Edit.javasrc/Editor.javasrc/GapBuffer.javasrc/History.javasrc/Insert.javasrc/SharedEditor.javasrc/Snapshot.javasrc/TextBuffer.java

AllInOne.java

// The complete design, built from every stage on this page.

import java.util.*;
import java.util.function.*;

// What the keyboard calls. Every change goes through run, which applies the edit, moves the
// cursor and records it in the history, all in one place.
class Editor {
    private final TextBuffer buffer;
    private final History history;
    private int cursor;

    Editor(TextBuffer buffer, History history) {
        this.buffer = buffer;
        this.history = history;
    }

    void type(String text) { run(new Insert(cursor, text)); }

    // A paste is one step of its own: it never joins the typing before or after it.
    void paste(String text) {
        history.seal();
        run(new Insert(cursor, text));
        history.seal();
    }

    // Removes the character before the cursor, and keeps it so undo can bring it back.
    void backspace() {
        if (cursor > 0) run(new Delete(cursor - 1, buffer.slice(cursor - 1, cursor)));
    }

    // Kept inside the text. Moving the cursor ends the current undo step.
    void moveCursor(int to) {
        cursor = Math.max(0, Math.min(to, buffer.length()));
        history.seal();
    }

    // Reverts the newest step and puts the cursor back where that step began.
    boolean undo() {
        Edit e = history.undo();
        if (e == null) return false;
        e.revert(buffer);
        cursor = e.cursorAfterRevert();
        return true;
    }

    // Does the step again and puts the cursor after it.
    boolean redo() {
        Edit e = history.redo();
        if (e == null) return false;
        e.apply(buffer);
        cursor = e.cursorAfterApply();
        return true;
    }

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

    int cursor() { return cursor; }

    private void run(Edit e) {
        e.apply(buffer);
        cursor = e.cursorAfterApply();
        history.record(e);
    }
}

// What the editor needs from the text, whatever holds it. A faster one can be swapped in
// without touching the editor.
interface TextBuffer {
    void insert(int at, String text);
    void delete(int at, int length);
    String slice(int from, int to);
    int length();
    String text();
}

// One change to the text, as an object that can be done and undone (the Command pattern). The
// history stores edits, not copies of the text, so a long history stays small.
interface Edit {
    void apply(TextBuffer buffer);
    void revert(TextBuffer buffer);
    // Where the cursor goes after the edit is done (on redo), and after it is undone.
    int cursorAfterApply();
    int cursorAfterRevert();

    // The edit that does this one and then next, if the two read as one step to a person, or
    // null if they don't.
    Edit mergedWith(Edit next);

    // Characters held, which is what the history's limit counts.
    int weight();
}

// Text typed or pasted at a position. Undoing it deletes the same characters again.
record Insert(int at, String text) implements Edit {
    public void apply(TextBuffer b) { b.insert(at, text); }
    public void revert(TextBuffer b) { b.delete(at, text.length()); }
    public int cursorAfterApply() { return at + text.length(); }
    public int cursorAfterRevert() { return at; }
    public int weight() { return text.length(); }

    // A keystroke right after the last one joins it, until a space or newline ends the word:
    // "hello world" undoes as "world", then "hello ".
    public Edit mergedWith(Edit next) {
        if (!(next instanceof Insert i) || i.at != at + text.length() || i.text.length() != 1) return null;
        if (Character.isWhitespace(text.charAt(text.length() - 1))) return null;
        return new Insert(at, text + i.text);
    }
}

// Characters removed at a position. It keeps the removed text, so undo can put it back.
record Delete(int at, String removed) implements Edit {
    public void apply(TextBuffer b) { b.delete(at, removed.length()); }
    public void revert(TextBuffer b) { b.insert(at, removed); }
    public int cursorAfterApply() { return at; }
    public int cursorAfterRevert() { return at + removed.length(); }
    public int weight() { return removed.length(); }

    // A backspace right before the last one joins it: holding backspace is one step.
    public Edit mergedWith(Edit next) {
        if (!(next instanceof Delete d) || d.at + d.removed.length() != at) return null;
        return new Delete(d.at, d.removed + removed);
    }
}

// Merges edits that a person thinks of as one, and keeps at most limit characters of history,
// dropping the oldest edits first.
class History {
    private final Deque<Edit> undo = new ArrayDeque<>();
    private final Deque<Edit> redo = new ArrayDeque<>();
    private final LongSupplier clock;
    private final long mergeWindowMillis;
    private final int limit;
    private int weight;          // characters held on the undo stack
    private long lastEditAt;
    private boolean sealed = true;  // the top edit is closed to merging

    History(LongSupplier clock, long mergeWindowMillis, int limit) {
        this.clock = clock;
        this.mergeWindowMillis = mergeWindowMillis;
        this.limit = limit;
    }

    // Typing after a pause starts a new step, and so does typing after anything that sealed the
    // last one.
    void record(Edit e) {
        redo.clear();
        long now = clock.getAsLong();
        Edit top = undo.peek();
        Edit merged = !sealed && top != null && now - lastEditAt <= mergeWindowMillis ? top.mergedWith(e) : null;
        if (merged != null) {
            undo.pop();
            weight -= top.weight();
            e = merged;
        }
        push(e);
        lastEditAt = now;
        sealed = false;
    }

    // Closes the newest step, so the next edit starts a new one. Moving the cursor, pasting and
    // undoing all seal: typing after them is a new thought.
    void seal() { sealed = true; }

    // Moves the newest step to the redo stack. Any new edit clears redo, in record.
    Edit undo() {
        seal();
        Edit e = undo.poll();
        if (e == null) return null;
        weight -= e.weight();
        redo.push(e);
        return e;
    }

    Edit redo() {
        seal();
        Edit e = redo.poll();
        if (e != null) push(e);
        return e;
    }

    // The newest edit always stays, even alone over the limit; older ones go until it fits.
    private void push(Edit e) {
        undo.push(e);
        weight += e.weight();
        while (weight > limit && undo.size() > 1) weight -= undo.removeLast().weight();
    }
}

// A gap buffer: the text in one array with an empty gap at the cursor. Typing fills the gap from
// the left, and backspace widens it, so neither moves any other character. Moving the cursor
// moves the gap, copying only the characters between the old and new position. Editors type at
// one place for a long time, which is why Emacs uses this.
class GapBuffer implements TextBuffer {
    private char[] chars = new char[16];
    private int gapStart;            // first empty slot
    private int gapEnd = chars.length;  // first slot after the gap

    public void insert(int at, String text) {
        moveGap(at);
        if (text.length() > gapEnd - gapStart) grow(text.length());
        text.getChars(0, text.length(), chars, gapStart);
        gapStart += text.length();
    }

    // The deleted characters are left in place and become part of the gap.
    public void delete(int at, int length) {
        moveGap(at);
        gapEnd += length;
    }

    // Positions after the gap are shifted by the gap's width.
    public String slice(int from, int to) {
        StringBuilder out = new StringBuilder(to - from);
        for (int i = from; i < to; i++) out.append(chars[i < gapStart ? i : i + gapEnd - gapStart]);
        return out.toString();
    }

    public int length() { return chars.length - (gapEnd - gapStart); }

    public String text() {
        return new String(chars, 0, gapStart) + new String(chars, gapEnd, chars.length - gapEnd);
    }

    private void moveGap(int at) {
        if (at < gapStart) {  // move the characters between at and the gap to after the gap
            int n = gapStart - at;
            System.arraycopy(chars, at, chars, gapEnd - n, n);
            gapStart -= n;
            gapEnd -= n;
        } else if (at > gapStart) {  // move the characters after the gap to before it
            int n = at - gapStart;
            System.arraycopy(chars, gapEnd, chars, gapStart, n);
            gapStart += n;
            gapEnd += n;
        }
    }

    // Doubling keeps growth rare: typing n characters copies the text O(log n) times in all.
    private void grow(int needed) {
        int tail = chars.length - gapEnd;
        char[] bigger = new char[Math.max(chars.length * 2, length() + needed + 16)];
        System.arraycopy(chars, 0, bigger, 0, gapStart);
        System.arraycopy(chars, gapEnd, bigger, bigger.length - tail, tail);
        gapEnd = bigger.length - tail;
        chars = bigger;
    }
}

// What autosave took: the text, and the version it was at.
record Snapshot(long version, String text) {}

// The editor shared with background threads. The UI thread edits; an autosave thread takes a
// snapshot, writes it to disk with no lock held, then reports which version it saved. Every
// call holds one lock, so a snapshot never sees a gap buffer halfway through moving its gap.
//
// The version is what makes saving correct. If autosave simply cleared a "dirty" flag when it
// finished, anything typed during the write would be marked saved without being on disk, and
// closing the editor would lose it. Recording the saved version means the editor is clean only
// while the text is still at that version.
class SharedEditor {
    private final Editor editor;
    private long version;
    private long savedVersion;

    SharedEditor(Editor editor) { this.editor = editor; }

    synchronized void type(String text) {
        editor.type(text);
        version++;
    }

    synchronized void paste(String text) {
        editor.paste(text);
        version++;
    }

    synchronized void backspace() {
        if (editor.cursor() == 0) return;
        editor.backspace();
        version++;
    }

    synchronized void moveCursor(int to) { editor.moveCursor(to); }

    synchronized boolean undo() {
        boolean changed = editor.undo();
        if (changed) version++;
        return changed;
    }

    synchronized boolean redo() {
        boolean changed = editor.redo();
        if (changed) version++;
        return changed;
    }

    // Taken under the lock, so the text and its version always match.
    synchronized Snapshot snapshot() { return new Snapshot(version, editor.text()); }

    // A save that finishes late, after a newer one, mustn't move the saved version backwards.
    synchronized void markSaved(long savedAt) { savedVersion = Math.max(savedVersion, savedAt); }

    // True while the text is at a different version from the last one saved.
    synchronized boolean dirty() { return version != savedVersion; }
}

Read onlyJava 21Every file builds in CI10 files306 lines

Explorer

• Pyall_in_one.py
• text_editor_undo
• Pydelete.py
• Pyedit.py
• Pyeditor.py
• Pygap_buffer.py
• Pyhistory.py
• Pyinsert.py
• Pyshared_editor.py
• Pysnapshot.py
• Pytext_buffer.py

Pyall_in_one.py

all_in_one.pytext_editor_undo/delete.pytext_editor_undo/edit.pytext_editor_undo/editor.pytext_editor_undo/gap_buffer.pytext_editor_undo/history.pytext_editor_undo/insert.pytext_editor_undo/shared_editor.pytext_editor_undo/snapshot.pytext_editor_undo/text_buffer.py

all_in_one.py

Read onlyPython 3.12Every file builds in CI10 files340 lines

Explorer

• C#AllInOne.cs
• src
• C#Delete.cs
• C#Editor.cs
• C#GapBuffer.cs
• C#History.cs
• C#IEdit.cs
• C#Insert.cs
• C#ITextBuffer.cs
• C#SharedEditor.cs
• C#Snapshot.cs

C#AllInOne.cs

AllInOne.cssrc/Delete.cssrc/Editor.cssrc/GapBuffer.cssrc/History.cssrc/IEdit.cssrc/Insert.cssrc/ITextBuffer.cssrc/SharedEditor.cssrc/Snapshot.cs

AllInOne.cs

Read onlyC# · .NET 10Every file builds in CI10 files332 lines

Explorer

• Goall_in_one.go
• Godelete.go
• Goedit.go
• Goeditor.go
• Gogap_buffer.go
• Gohistory.go
• Goinsert.go
• Goshared_editor.go
• Gosnapshot.go
• Gotext_buffer.go

Goall_in_one.go

all_in_one.godelete.goedit.goeditor.gogap_buffer.gohistory.goinsert.goshared_editor.gosnapshot.gotext_buffer.go

all_in_one.go

Read onlyGo 1.24Every file builds in CI10 files392 lines

Explorer

• TSall-in-one.ts
• src
• TSdelete.ts
• TSedit.ts
• TSeditor.ts
• TSgap-buffer.ts
• TShistory.ts
• TSinsert.ts
• TSshared-editor.ts
• TSsnapshot.ts
• TStext-buffer.ts

TSall-in-one.ts

all-in-one.tssrc/delete.tssrc/edit.tssrc/editor.tssrc/gap-buffer.tssrc/history.tssrc/insert.tssrc/shared-editor.tssrc/snapshot.tssrc/text-buffer.ts

all-in-one.ts

Read onlyTypeScript, strictEvery file builds in CI10 files359 lines

Three ideas hold it together:

• Nothing copies the document. Edits hold their own characters (Command), the buffer moves only what it must, and only autosave copies the text, once per save.
• Every change goes through an edit. The editor never touches the buffer directly, so everything the user does can be undone. The screen calls type and undo, never the history or the buffer (Facade).
• Each rule lives in one place. Edits decide whether they merge. The history decides when merging is allowed and what to forget. The buffer decides how text is stored (Strategy).

Stress it

So far, one thread uses the editor. Now autosave runs every few seconds on a second thread.

Typing while autosave writes

Interviewerminute 24

Autosave runs every few seconds on a background thread and writes the text to disk. The title bar shows a dot when there are unsaved changes. What can go wrong?

What they are testing

Two things. Whether you see that the autosave thread reads the buffer while the screen’s thread changes it. And whether you catch the lost update: typing during the write, then autosave clearing “unsaved” for text that never reached the disk.

Two threads touch the editor. The screen’s thread makes edits. The autosave thread reads the text, writes it to disk, and clears the “unsaved” mark. Two things go wrong without care.

A torn read. A gap buffer in the middle of moving its gap, or growing its array, is in a state that no reader should see. Autosave could write half-moved text to disk. The clearly correct fix is that every call to the editor, edits and reads alike, holds one lock. And the slow disk write happens with no lock held, on a snapshot: a copy of the text, taken under the lock.

A lost update. That fix still leaves a gap. Picture this:

1. Autosave takes a snapshot of “draft”.
2. While it writes, the user types “!”.
3. The write finishes, and autosave clears the “unsaved” mark.
4. The title bar now says everything is saved. The user closes the editor, and “!” is gone.

The better fix is a version number. Every edit adds one to it. A snapshot carries the version it was taken at, and autosave reports which version it saved. The editor counts as saved only while its current version still equals the saved one. In our example, the snapshot was version 5, “!” made version 6, so the editor stays unsaved. A save that finishes late, after a newer save, can’t move the saved version backwards.

Sequence: typing while autosave writes

Scroll or pinch to zoom, drag to pan

• Color key
• Database
• Facade

Option	How	Lost update?	Cost
1. Lock, snapshot, save the version (our choice)	Copy under the lock, write outside it	No	One copy of the text per save
2. Lock, and write to disk while holding it	Autosave holds the lock for the whole write	No	Typing freezes for as long as the disk takes
3. An “unsaved” flag cleared after the write	No version	Yes	Unsaved text is reported as saved
4. Text that never changes in place	A persistent rope or piece table; snapshots are free	No	A more complex buffer

JSharedEditor.javaPyshared_editor.pyC#SharedEditor.csGoshared_editor.goTSshared-editor.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// What autosave took: the text, and the version it was at.
record Snapshot(long version, String text) {}

// The editor shared with background threads. The UI thread edits; an autosave thread takes a
// snapshot, writes it to disk with no lock held, then reports which version it saved. Every
// call holds one lock, so a snapshot never sees a gap buffer halfway through moving its gap.
//
// The version is what makes saving correct. If autosave simply cleared a "dirty" flag when it
// finished, anything typed during the write would be marked saved without being on disk, and
// closing the editor would lose it. Recording the saved version means the editor is clean only
// while the text is still at that version.
class SharedEditor {
    private final Editor editor;
    private long version;
    private long savedVersion;

    SharedEditor(Editor editor) { this.editor = editor; }

    synchronized void type(String text) {
        editor.type(text);
        version++;
    }

    synchronized void paste(String text) {
        editor.paste(text);
        version++;
    }

    synchronized void backspace() {
        if (editor.cursor() == 0) return;
        editor.backspace();
        version++;
    }

    synchronized void moveCursor(int to) { editor.moveCursor(to); }

    synchronized boolean undo() {
        boolean changed = editor.undo();
        if (changed) version++;
        return changed;
    }

    synchronized boolean redo() {
        boolean changed = editor.redo();
        if (changed) version++;
        return changed;
    }

    // Taken under the lock, so the text and its version always match.
    synchronized Snapshot snapshot() { return new Snapshot(version, editor.text()); }

    // A save that finishes late, after a newer one, mustn't move the saved version backwards.
    synchronized void markSaved(long savedAt) { savedVersion = Math.max(savedVersion, savedAt); }

    // True while the text is at a different version from the last one saved.
    synchronized boolean dirty() { return version != savedVersion; }
}

Why is this correct? The snapshot’s text and its version are read under the same lock, so they always match. Any edit after the snapshot raises the version above the saved one, so the editor can only look saved when the text on screen is exactly the text that was written.

What does it cost? One copy of the text per save. Copying a few megabytes in memory takes about a millisecond, so typing never notices.

Common mistake

Writing to disk while holding the lock

It’s the easy way to make autosave consistent, and it freezes typing for as long as the disk takes, which on a network drive can be seconds. Copy under the lock, then write without it.

Go deeperHow each language handles it1 min

In Java, Python, C# and Go, autosave runs on another thread, so the lock is needed. TypeScript runs on one thread, and nothing can interrupt an edit, so it needs no lock. But its write to disk still waits with await, and typing during that wait is the same lost update. So the version check is the same in all five languages.

How you’d prove it works

The history reads time from a clock the test controls. So a test “types” one character every 100 ms by moving its clock, and makes a pause by moving it five seconds. No test waits in real time. The tests that matter:

• Typing and backspace happen at the cursor, wherever it is.
• Undo and redo put back both the text and the cursor. A new edit clears redo.
• “hello world” undoes in two steps: “world”, then “hello “.
• A pause, a cursor move and a paste each start a new step.
• Three backspaces undo as one step, with the cursor back where it was.
• With a 10-character limit, three 5-character pastes leave two steps that can be undone.
• A gap buffer and a plain string agree after 5,000 random inserts and deletes.
• Undo, redo and backspace with nothing to act on change nothing.
• A save of version 5 doesn’t mark the editor saved after version 6 was typed.
• Snapshots taken while another thread types always hold the start of the typing, and their version always matches their length.

Go deeperThe tests in five languages2 min

The last test fails within a few runs in Java if the lock is removed: a snapshot comes back with a version that doesn’t match its text.

JMain.javaPyworld.pyC#Program.csGoworld.goTSexample.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

long now = 0;  // the test's clock, in milliseconds
Editor editor;

@BeforeEach
void setUp() { editor = new Editor(new GapBuffer(), new History(() -> now, 1000, 1_000_000)); }

// Types one character at a time, 100 ms apart, as a person does.
void typeSlowly(String s) {
    for (char c : s.toCharArray()) {
        now += 100;
        editor.type(String.valueOf(c));
    }
}

@Test
void editsHappenAtTheCursor() {
    typeSlowly("helo");
    editor.moveCursor(3);
    editor.type("l");
    assertEquals("hello", editor.text());
    assertEquals(4, editor.cursor());
    editor.moveCursor(99);
    editor.backspace();
    assertEquals("hell", editor.text());
}

@Test
void undoAndRedoRestoreTextAndCursor() {
    typeSlowly("abc");
    editor.moveCursor(1);
    editor.type("X");
    assertTrue(editor.undo());
    assertEquals("abc", editor.text());
    assertEquals(1, editor.cursor());
    assertTrue(editor.redo());
    assertEquals("aXbc", editor.text());
    assertEquals(2, editor.cursor());
    editor.undo();
    editor.type("Y");                 // a new edit
    assertFalse(editor.redo());       // clears what could be redone
    assertEquals("aYbc", editor.text());
}

@Test
void typingAWordIsOneUndoStep() {
    typeSlowly("hello world");
    editor.undo();
    assertEquals("hello ", editor.text());
    editor.undo();
    assertEquals("", editor.text());
}

@Test
void aPauseACursorMoveOrAPasteStartsANewStep() {
    typeSlowly("ab");
    now += 5000;                      // a pause
    typeSlowly("c");
    editor.moveCursor(0);
    typeSlowly("d");
    editor.moveCursor(4);
    editor.paste("e");
    typeSlowly("f");
    for (String expected : List.of("dabce", "dabc", "abc", "ab", "")) {
        editor.undo();
        assertEquals(expected, editor.text());
    }
}

@Test
void backspacesMergeIntoOneStep() {
    typeSlowly("hello");
    editor.moveCursor(5);             // seal the typing
    for (int i = 0; i < 3; i++) {
        now += 100;
        editor.backspace();
    }
    assertEquals("he", editor.text());
    editor.undo();
    assertEquals("hello", editor.text());
    assertEquals(5, editor.cursor());
}

@Test
void historyKeepsTheNewestEditsWithinItsLimit() {
    editor = new Editor(new GapBuffer(), new History(() -> now, 1000, 10));
    editor.paste("aaaaa");
    editor.paste("bbbbb");
    editor.paste("ccccc");            // 15 characters of history; the limit is 10
    assertTrue(editor.undo());
    assertTrue(editor.undo());
    assertFalse(editor.undo());       // the first paste was dropped
    assertEquals("aaaaa", editor.text());
}

@Test
void gapBufferAgreesWithAStringUnderRandomEdits() {
    Random random = new Random(42);
    GapBuffer gap = new GapBuffer();
    StringBuilder expected = new StringBuilder();
    for (int i = 0; i < 5000; i++) {
        int at = random.nextInt(expected.length() + 1);
        if (random.nextInt(3) > 0 || expected.length() == at) {
            String s = "xyz".substring(0, 1 + random.nextInt(3));
            gap.insert(at, s);
            expected.insert(at, s);
        } else {
            int n = 1 + random.nextInt(Math.min(3, expected.length() - at));
            assertEquals(expected.substring(at, at + n), gap.slice(at, at + n));
            gap.delete(at, n);
            expected.delete(at, at + n);
        }
    }
    assertEquals(expected.toString(), gap.text());
    assertEquals(expected.length(), gap.length());
}

@Test
void nothingToUndoOrDeleteChangesNothing() {
    assertFalse(editor.undo());
    assertFalse(editor.redo());
    editor.backspace();
    assertFalse(editor.undo());       // a backspace at the start recorded nothing
    assertEquals("", editor.text());
}

@Test
void savingMarksOnlyTheVersionThatWasSaved() {
    SharedEditor shared = new SharedEditor(editor);
    shared.type("draft");
    Snapshot s = shared.snapshot();   // autosave starts writing "draft"
    shared.type("!");                 // typed while the write is in progress
    shared.markSaved(s.version());
    assertTrue(shared.dirty());       // "!" isn't on disk yet
    shared.markSaved(shared.snapshot().version());
    assertFalse(shared.dirty());
}

@Test
void snapshotsTakenWhileTypingAreAlwaysConsistent() throws Exception {
    SharedEditor shared = new SharedEditor(editor);
    String alphabet = "abcdefghijklmnopqrstuvwxyz";
    StringBuilder all = new StringBuilder();
    for (int i = 0; i < 400; i++) all.append(alphabet);
    String expected = all.toString();
    Thread typist = new Thread(() -> {
        for (char c : expected.toCharArray()) shared.type(String.valueOf(c));
    });
    typist.start();
    while (typist.isAlive()) {
        Snapshot seen = shared.snapshot();
        assertTrue(expected.startsWith(seen.text()));        // never a torn or half-moved buffer
        assertEquals(seen.version(), seen.text().length());  // the version matches the text it labels
    }
    typist.join();
    assertEquals(expected, shared.snapshot().text());
}

Go deeperEvery edge case, and where it is handled2 min

Case	What happens	Where
Backspace at the start	Nothing, and nothing recorded	Editor.backspace
Undo or redo with nothing to do	Returns false	History
Cursor moved past the end	Kept inside the text	Editor.moveCursor
A new edit after undo	Redo is cleared	History.record
Typing after a pause, cursor move or paste	A new undo step	History.record, seal
A space while typing	The next character starts a new step	Insert.mergedWith
One paste larger than the history limit	Kept alone; everything older dropped	History.push
Undo the oldest dropped step	Not possible: it was forgotten	History.push
Autosave during typing	Writes a consistent snapshot; stays unsaved if typing continued	SharedEditor
Two saves finishing out of order	The saved version never goes backwards	markSaved
Characters made of several bytes	Positions count characters, not bytes (runes in Go)	TextBuffer

Wrap up

The decisions, and what each one costs

Decision	We chose	We gave up
What undo stores	Edits holding only what changed	Undo that can’t get an inverse wrong
Redo	A second stack, cleared by any new edit	Branches of history (an undo tree)
Undo steps	Typing merged by word, pause, cursor move; a paste alone	Letter-by-letter control
History size	A limit on characters held; the newest step always kept	A simple step count
Text storage	A gap buffer behind a TextBuffer interface	Fast jumps across huge files (a piece table)
Autosave	Snapshot under a lock, write outside it, save by version	One text copy per save

Go deeperGenuinely different designs, and when to pick them2 min

Snapshots that share almost everything. If the text is a rope or piece table that never changes in place, each version shares almost everything with the last. A “snapshot” is then just a pointer. Undo is keeping old versions, and autosave reads one without a lock. The Memento pattern from stage 1 becomes cheap. Many editors written in functional languages work this way, at the cost of a more complex buffer.

An undo tree. Instead of clearing redo, keep the branch. Undoing and then typing starts a new branch, and the old one stays reachable. Vim and Emacs’s undo-tree do this. Nothing is ever lost, but the user needs a way to see and choose branches.

Operational transformation or CRDTs. When several people edit one document, an edit made against an old version must be adjusted to apply to the current one (OT, as in Google Docs). Or the text must be a structure that gives the same result whatever order edits arrive in (CRDTs, as in Figma and many local-first apps). Undo becomes “undo my last edit”, in a document others have changed since.

How to spend 45 minutes

• 0 to 3. Plain text, one cursor, file sizes, saving in the background.
• 3 to 5. The promises. Name “an edit costs the size of the change” as the hard one.
• 5 to 23. Snapshots and their cost, edits as commands on two stacks, merging and the character limit, then the gap buffer. Code Delete, History.record and moveGap.
• 23 to 25. Walk through the full diagram: nothing copies the document, every change is an edit.
• 25 to 30. Autosave: the lock, the snapshot, and the version.
• 30 to 45. Compound edits, then your own questions.

If time is short, skip the gap buffer and spend it on merging and the history limit. Those decide this question for most interviewers.

Follow-up questions

Interviewerminute 30

Users want to select a word and type over it, and “replace all” in a long file. How do those fit the history?

What they are testing

Whether you reach for a compound command: one undo step made of several edits, applied in order and reverted in reverse order.

Most extensions fit into one place:

Extension	What changes	Touches the history?
Selections	A selection range; typing over it is a compound delete-then-insert	No
Replace all	One compound edit of many parts	No
Several cursors	Each keystroke is a compound edit, one part per cursor, back to front	No
Undo history saved with the file	Edits saved next to the file, loaded on open	Yes
Collaborative editing	Edits adjusted against other people’s edits (OT), or a CRDT	Yes: undo is per user
Huge files	A piece table, and loading the file a part at a time	No

Go deeperAdding compound edits, step by step2 min

Typing over a selection is a delete followed by an insert, and the user expects one undo to bring the selection back. “Replace all” is hundreds of deletes and inserts, also one step. Both are a compound edit. This is the Composite pattern applied to commands.

1. Add CompoundEdit, an Edit that holds a list of edits. To the history, it’s just one more edit.
2. Apply the parts in order. For typing over “cat” with “dog”: delete “cat”, then insert “dog”.
3. Revert the parts in reverse order. First remove “dog”, then put “cat” back. Reverse order matters: each part’s undo must run against the text that part produced. Undoing the delete first would put “cat” back in front of “dog”.
4. Its weight is the sum of its parts, so the history limit still works.
5. It never merges with typing, so it’s always its own undo step.

For “replace all”, there’s one more detail: apply the replacements from the end of the file backwards. Then each replacement doesn’t shift the positions of the ones still to come.

The history doesn’t change at all. That’s the payoff of making every change an Edit.

Go deeperFour more follow-up questions2 min

Interviewer asksWhy not store the cursor position on the undo stack too?

Each edit already knows where the cursor belongs after it’s applied or reverted, from its own position and length. Storing the cursor separately would repeat that, and it would be wrong as soon as a merge changed the edit.

Interviewer asksShould moving the cursor be undoable?

Usually not: users expect undo to change the text, and stepping back through cursor moves feels broken. Some editors put the cursor and selection back with each text undo, which this design does through cursorAfterRevert, and a few have a separate “go back” command for moving around.

Interviewer asksHow do you show 'unsaved' correctly after undoing back to the saved text?

With versions alone, undoing back to the saved text still shows unsaved. To fix it, record the history’s position at the last save, and compare positions. If undo returns to exactly that point, the text matches the disk, which is how most editors behave.

Interviewer asksWhat if an edit fails halfway, say running out of memory while growing?

Apply the edit to the buffer first, and record it only after it succeeds, as run does. A failed apply leaves the history untouched, so undo never tries to undo something that didn’t happen.

Further reading

• Command pattern, the shape this design is built on
• Design an in-memory file system, another design where the data structure decides the cost of every operation
• Text Buffer Reimplementation, VS Code blog, why VS Code moved to a piece table
• Data Structures for Text Sequences, Charles Crowley, the classic comparison of gap buffers, piece tables and more