38 — LLD: Text Editor with Undo/Redo

Understanding the Problem

A text editor with row-based storage and arbitrary insert/delete operations, plus unlimited undo and redo. The trick is not to snapshot the whole document on each edit — that is O(N) memory per operation. Instead, use the Command pattern: every operation knows how to reverse itself.

What is a Text Editor with Undo/Redo?

An in-memory document that supports mutations at arbitrary positions and can replay or reverse those mutations on demand. The editor is the classic Command-pattern example in every design-patterns textbook — for good reason.

Requirements

Clarifying Questions

You: Single-user or multi-user?

Interviewer: Single user. Ignore collaborative editing and CRDTs.

Single thread of edits. No merge conflicts.

You: Undo granularity — per keystroke or per operation call?

Interviewer: Per operation call. Each insert or delete is one undo step.

So the history stores one Command per API call.

You: Redo behavior after a new edit?

Interviewer: A new edit clears the redo stack.

Standard desktop editor semantics. Two stacks, new edit invalidates future history.

Final Requirements

insert(row, col, text) — can span multiple lines (text contains \n).
delete(row, col, length) — may cross line boundaries.
render() — return the full document as a string.
undo() / redo() — reverse or replay the most recent operation. New edit clears redo.
Row-based storage: list of lines.

Out of scope: Persistence to disk, collaborative editing, syntax highlighting, large-file streaming.

Deferred tradeoff: Per-operation undo is coarser than per-keystroke. Real editors often group small keystrokes into a single undo entry with a merge window; out of scope here.

Core Entities and Relationships

Two orthogonal concerns: the document (data) and the history (commands). The editor glues them together.

Entity	Responsibility
`Document`	List of row strings. Owns `insert` and `delete` primitives.
`Command`	Interface: `execute()` and `undo()`.
`InsertCommand`	Knows what was inserted and where.
`DeleteCommand`	Captures what was deleted to restore on undo.
`Editor`	Facade. Exposes the public API. Owns the `Document` and two stacks.

Why not snapshot the whole document on each edit? That is the Memento pattern and it works, but at O(N) memory per edit. For a 1 MB file with 100 edits, that is 100 MB in history. The Command approach stores only the delta.

Why does DeleteCommand capture the removed text? So that undo can re-insert it. DeleteCommand is not purely a spec; it is a record of what happened.

Design is iterative. If we later need transactional multi-command undo, we will introduce a CompositeCommand.

Class Design

Document

State:

rows: List<StringBuilder> — starts as a single empty row.

Methods:

insert(row, col, text).
delete(row, col, length) -> String — returns the removed text so commands can remember it.
render() -> String.

Command (interface)

execute().
undo().

InsertCommand

Fields: doc, row, col, text.
execute → doc.insert(row, col, text).
undo → doc.delete(row, col, text.length()).

DeleteCommand

Fields: doc, row, col, length, removed: String (filled on execute).
execute → removed = doc.delete(...).
undo → doc.insert(row, col, removed).

Editor

State:

doc: Document.
undoStack: Deque<Command>.
redoStack: Deque<Command>.

Methods: insert, delete, undo, redo, render.

JavaC++TypeScript

java

public class Document {
    final List<StringBuilder> rows = new ArrayList<>(List.of(new StringBuilder()));
    public void insert(int row, int col, String text) { /* multi-line handling */ }
    public String delete(int row, int col, int length) { /* returns removed chunk */ }
    public String render() {
        return rows.stream().map(StringBuilder::toString).collect(Collectors.joining("\n"));
    }
}

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

public class InsertCommand implements Command {
    private final Document doc;
    private final int row, col;
    private final String text;
    public InsertCommand(Document d, int r, int c, String t) { this.doc=d; this.row=r; this.col=c; this.text=t; }
    public void execute() { doc.insert(row, col, text); }
    public void undo() { doc.delete(row, col, text.length()); }
}

public class DeleteCommand implements Command {
    private final Document doc;
    private final int row, col, length;
    private String removed;
    public DeleteCommand(Document d, int r, int c, int l) { this.doc=d; this.row=r; this.col=c; this.length=l; }
    public void execute() { removed = doc.delete(row, col, length); }
    public void undo() { doc.insert(row, col, removed); }
}

public class Editor {
    private final Document doc = new Document();
    private final Deque<Command> undoStack = new ArrayDeque<>();
    private final Deque<Command> redoStack = new ArrayDeque<>();

    public void insert(int r, int c, String t) { run(new InsertCommand(doc, r, c, t)); }
    public void delete(int r, int c, int l)   { run(new DeleteCommand(doc, r, c, l)); }

    private void run(Command cmd) {
        cmd.execute();
        undoStack.push(cmd);
        redoStack.clear();
    }

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

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

    public String render() { return doc.render(); }
}

cpp

class Document {
public:
    std::vector<std::string> rows{""};
    void insert(int row, int col, const std::string& text);
    std::string erase(int row, int col, int length);
    std::string render() const;
};

struct Command {
    virtual void execute() = 0;
    virtual void undo() = 0;
    virtual ~Command() = default;
};

class Editor {
    Document doc;
    std::vector<std::unique_ptr<Command>> undoStack, redoStack;
public:
    void insert(int r, int c, const std::string& t);
    void remove(int r, int c, int l);
    void undo();
    void redo();
    std::string render() const { return doc.render(); }
};

typescript

export class Document {
  rows: string[] = [""];
  insert(row: number, col: number, text: string): void { /* ... */ }
  remove(row: number, col: number, length: number): string { /* ... */ }
  render(): string { return this.rows.join("\n"); }
}

export interface Command { execute(): void; undo(): void; }

export class InsertCommand implements Command {
  constructor(private doc: Document, private row: number, private col: number, private text: string) {}
  execute() { this.doc.insert(this.row, this.col, this.text); }
  undo() { this.doc.remove(this.row, this.col, this.text.length); }
}

export class DeleteCommand implements Command {
  private removed = "";
  constructor(private doc: Document, private row: number, private col: number, private length: number) {}
  execute() { this.removed = this.doc.remove(this.row, this.col, this.length); }
  undo() { this.doc.insert(this.row, this.col, this.removed); }
}

Design principles at play:

Command pattern: Each mutation is a reversible object. Undo/redo become stack operations.
Single Responsibility: Document owns the text data; Editor owns the history.
Encapsulation: Callers go through Editor; they never touch Document.rows directly.

Implementation

Core Logic: Multi-line Insert

Splitting text on \n and stitching:

Split text by \n. If only one part, a simple row insertion.
Otherwise: take the tail of the current row (from col to end), insert the first part of text at col, then insert middle parts as new rows, then insert the last part concatenated with the tail as a new row.

Core Logic: Multi-line Delete

Walk forward from (row, col) consuming length characters.
If the deletion stays in the current row, trim and return.
If it crosses a boundary, accumulate the removed text (including \n), delete the tail of the current row, merge the next row in, and continue.

Implementations

JavaC++TypeScript

java

public void insert(int row, int col, String text) {
    if (row < 0 || row >= rows.size()) throw new IndexOutOfBoundsException();
    StringBuilder r = rows.get(row);
    if (col < 0 || col > r.length()) throw new IndexOutOfBoundsException();

    String[] parts = text.split("\n", -1);
    if (parts.length == 1) {
        r.insert(col, parts[0]);
        return;
    }
    String tail = r.substring(col);
    r.delete(col, r.length()).append(parts[0]);
    for (int i = 1; i < parts.length - 1; i++) {
        rows.add(row + i, new StringBuilder(parts[i]));
    }
    rows.add(row + parts.length - 1, new StringBuilder(parts[parts.length - 1]).append(tail));
}

public String delete(int row, int col, int length) {
    StringBuilder sb = new StringBuilder();
    int remaining = length;
    int curRow = row, curCol = col;
    while (remaining > 0 && curRow < rows.size()) {
        StringBuilder r = rows.get(curRow);
        int available = r.length() - curCol;
        if (available >= remaining) {
            sb.append(r, curCol, curCol + remaining);
            r.delete(curCol, curCol + remaining);
            remaining = 0;
        } else {
            sb.append(r, curCol, r.length());
            sb.append('\n');
            r.delete(curCol, r.length());
            remaining -= (available + 1);
            if (curRow + 1 < rows.size()) {
                r.append(rows.remove(curRow + 1));
            } else {
                break;
            }
        }
    }
    return sb.toString();
}

cpp

void Document::insert(int row, int col, const std::string& text) {
    auto& r = rows.at(row);
    size_t pos = 0, nl;
    std::vector<std::string> parts;
    while ((nl = text.find('\n', pos)) != std::string::npos) {
        parts.push_back(text.substr(pos, nl - pos));
        pos = nl + 1;
    }
    parts.push_back(text.substr(pos));

    if (parts.size() == 1) { r.insert(col, parts[0]); return; }
    std::string tail = r.substr(col);
    r.erase(col);
    r += parts[0];
    for (size_t i = 1; i + 1 < parts.size(); ++i) rows.insert(rows.begin() + row + i, parts[i]);
    rows.insert(rows.begin() + row + parts.size() - 1, parts.back() + tail);
}

typescript

insert(row: number, col: number, text: string): void {
  if (row < 0 || row >= this.rows.length) throw new Error("row OOB");
  const r = this.rows[row];
  if (col < 0 || col > r.length) throw new Error("col OOB");
  const parts = text.split("\n");
  if (parts.length === 1) {
    this.rows[row] = r.slice(0, col) + parts[0] + r.slice(col);
    return;
  }
  const tail = r.slice(col);
  this.rows[row] = r.slice(0, col) + parts[0];
  for (let i = 1; i < parts.length - 1; i++) {
    this.rows.splice(row + i, 0, parts[i]);
  }
  this.rows.splice(row + parts.length - 1, 0, parts[parts.length - 1] + tail);
}

remove(row: number, col: number, length: number): string {
  let out = "";
  let rem = length, curRow = row, curCol = col;
  while (rem > 0 && curRow < this.rows.length) {
    const r = this.rows[curRow];
    const avail = r.length - curCol;
    if (avail >= rem) {
      out += r.slice(curCol, curCol + rem);
      this.rows[curRow] = r.slice(0, curCol) + r.slice(curCol + rem);
      rem = 0;
    } else {
      out += r.slice(curCol) + "\n";
      this.rows[curRow] = r.slice(0, curCol);
      rem -= (avail + 1);
      if (curRow + 1 < this.rows.length) {
        this.rows[curRow] += this.rows[curRow + 1];
        this.rows.splice(curRow + 1, 1);
      } else break;
    }
  }
  return out;
}

Thread Safety

Text editors are traditionally single-threaded UI-bound. If you need concurrency, put every operation on an actor or a single-consumer queue (BlockingQueue<Command>) processed by one worker. Do not share the Document across threads with fine-grained locks — races between interleaved insert/delete are vicious and hard to reason about.

Verification

Commands: insert(0,0,"Hello"), insert(0,5," World"), insert(0,5,"\nLine2"), then undo, undo, then insert(0,0,"X"), redo (should be a no-op since the new edit cleared redo).

Step	Document	undo stack	redo stack
insert 1	"Hello"	[I1]	[]
insert 2	"Hello World"	[I1, I2]	[]
insert 3	"Hello\nLine2 World"	[I1, I2, I3]	[]
undo	"Hello World"	[I1, I2]	[I3]
undo	"Hello"	[I1]	[I3, I2]
insert 4	"XHello"	[I1, I4]	[] (cleared)
redo	"XHello"	[I1, I4]	[] (no-op)

The final redo is a no-op because the new edit cleared the redo stack — exactly the behavior the requirements called for.

Complete Code Implementation

JavaC++TypeScript

java

import java.util.*;
import java.util.stream.Collectors;

public class Document {
    final List<StringBuilder> rows = new ArrayList<>(List.of(new StringBuilder()));

    public void insert(int row, int col, String text) {
        if (row < 0 || row >= rows.size()) throw new IndexOutOfBoundsException();
        StringBuilder r = rows.get(row);
        if (col < 0 || col > r.length()) throw new IndexOutOfBoundsException();
        String[] parts = text.split("\n", -1);
        if (parts.length == 1) { r.insert(col, parts[0]); return; }
        String tail = r.substring(col);
        r.delete(col, r.length()).append(parts[0]);
        for (int i = 1; i < parts.length - 1; i++) rows.add(row + i, new StringBuilder(parts[i]));
        rows.add(row + parts.length - 1, new StringBuilder(parts[parts.length - 1]).append(tail));
    }

    public String delete(int row, int col, int length) {
        StringBuilder sb = new StringBuilder();
        int remaining = length, curRow = row, curCol = col;
        while (remaining > 0 && curRow < rows.size()) {
            StringBuilder r = rows.get(curRow);
            int available = r.length() - curCol;
            if (available >= remaining) {
                sb.append(r, curCol, curCol + remaining);
                r.delete(curCol, curCol + remaining);
                remaining = 0;
            } else {
                sb.append(r, curCol, r.length());
                sb.append('\n');
                r.delete(curCol, r.length());
                remaining -= (available + 1);
                if (curRow + 1 < rows.size()) r.append(rows.remove(curRow + 1));
                else break;
            }
        }
        return sb.toString();
    }

    public String render() {
        return rows.stream().map(StringBuilder::toString).collect(Collectors.joining("\n"));
    }
}

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

public class InsertCommand implements Command {
    private final Document doc; private final int row, col; private final String text;
    public InsertCommand(Document d, int r, int c, String t) { doc=d; row=r; col=c; text=t; }
    public void execute() { doc.insert(row, col, text); }
    public void undo() { doc.delete(row, col, text.length()); }
}

public class DeleteCommand implements Command {
    private final Document doc; private final int row, col, length; private String removed;
    public DeleteCommand(Document d, int r, int c, int l) { doc=d; row=r; col=c; length=l; }
    public void execute() { removed = doc.delete(row, col, length); }
    public void undo() { doc.insert(row, col, removed); }
}

public class Editor {
    private final Document doc = new Document();
    private final Deque<Command> undoStack = new ArrayDeque<>();
    private final Deque<Command> redoStack = new ArrayDeque<>();

    public void insert(int r, int c, String t) { run(new InsertCommand(doc, r, c, t)); }
    public void delete(int r, int c, int l)   { run(new DeleteCommand(doc, r, c, l)); }

    private void run(Command cmd) { cmd.execute(); undoStack.push(cmd); redoStack.clear(); }

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

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

    public String render() { return doc.render(); }
}

cpp

#include <memory>
#include <string>
#include <vector>

class Document {
public:
    std::vector<std::string> rows{""};
    void insert(int row, int col, const std::string& text) {
        auto& r = rows.at(row);
        size_t pos = 0, nl;
        std::vector<std::string> parts;
        while ((nl = text.find('\n', pos)) != std::string::npos) {
            parts.push_back(text.substr(pos, nl - pos));
            pos = nl + 1;
        }
        parts.push_back(text.substr(pos));
        if (parts.size() == 1) { r.insert(col, parts[0]); return; }
        std::string tail = r.substr(col);
        r.erase(col);
        r += parts[0];
        for (size_t i = 1; i + 1 < parts.size(); ++i) rows.insert(rows.begin() + row + i, parts[i]);
        rows.insert(rows.begin() + row + parts.size() - 1, parts.back() + tail);
    }

    std::string erase(int row, int col, int length) {
        std::string out;
        int rem = length, curRow = row, curCol = col;
        while (rem > 0 && curRow < (int) rows.size()) {
            auto& r = rows[curRow];
            int avail = (int) r.size() - curCol;
            if (avail >= rem) {
                out += r.substr(curCol, rem);
                r.erase(curCol, rem);
                rem = 0;
            } else {
                out += r.substr(curCol) + "\n";
                r.erase(curCol);
                rem -= (avail + 1);
                if (curRow + 1 < (int) rows.size()) {
                    r += rows[curRow + 1];
                    rows.erase(rows.begin() + curRow + 1);
                } else break;
            }
        }
        return out;
    }

    std::string render() const {
        std::string out;
        for (size_t i = 0; i < rows.size(); ++i) {
            if (i) out += "\n";
            out += rows[i];
        }
        return out;
    }
};

struct Command {
    virtual void execute() = 0;
    virtual void undo() = 0;
    virtual ~Command() = default;
};

class InsertCommand : public Command {
    Document& doc; int row, col; std::string text;
public:
    InsertCommand(Document& d, int r, int c, std::string t) : doc(d), row(r), col(c), text(std::move(t)) {}
    void execute() override { doc.insert(row, col, text); }
    void undo() override { doc.erase(row, col, (int) text.size()); }
};

class DeleteCommand : public Command {
    Document& doc; int row, col, length; std::string removed;
public:
    DeleteCommand(Document& d, int r, int c, int l) : doc(d), row(r), col(c), length(l) {}
    void execute() override { removed = doc.erase(row, col, length); }
    void undo() override { doc.insert(row, col, removed); }
};

class Editor {
    Document doc;
    std::vector<std::unique_ptr<Command>> undoStack, redoStack;
    void run(std::unique_ptr<Command> c) {
        c->execute();
        undoStack.push_back(std::move(c));
        redoStack.clear();
    }
public:
    void insert(int r, int c, const std::string& t) { run(std::make_unique<InsertCommand>(doc, r, c, t)); }
    void remove(int r, int c, int l) { run(std::make_unique<DeleteCommand>(doc, r, c, l)); }
    void undo() {
        if (undoStack.empty()) return;
        auto c = std::move(undoStack.back()); undoStack.pop_back();
        c->undo(); redoStack.push_back(std::move(c));
    }
    void redo() {
        if (redoStack.empty()) return;
        auto c = std::move(redoStack.back()); redoStack.pop_back();
        c->execute(); undoStack.push_back(std::move(c));
    }
    std::string render() const { return doc.render(); }
};

typescript

export class Document {
  rows: string[] = [""];

  insert(row: number, col: number, text: string): void {
    if (row < 0 || row >= this.rows.length) throw new Error("row OOB");
    const r = this.rows[row];
    if (col < 0 || col > r.length) throw new Error("col OOB");
    const parts = text.split("\n");
    if (parts.length === 1) {
      this.rows[row] = r.slice(0, col) + parts[0] + r.slice(col);
      return;
    }
    const tail = r.slice(col);
    this.rows[row] = r.slice(0, col) + parts[0];
    for (let i = 1; i < parts.length - 1; i++) this.rows.splice(row + i, 0, parts[i]);
    this.rows.splice(row + parts.length - 1, 0, parts[parts.length - 1] + tail);
  }

  remove(row: number, col: number, length: number): string {
    let out = "", rem = length, curRow = row, curCol = col;
    while (rem > 0 && curRow < this.rows.length) {
      const r = this.rows[curRow];
      const avail = r.length - curCol;
      if (avail >= rem) {
        out += r.slice(curCol, curCol + rem);
        this.rows[curRow] = r.slice(0, curCol) + r.slice(curCol + rem);
        rem = 0;
      } else {
        out += r.slice(curCol) + "\n";
        this.rows[curRow] = r.slice(0, curCol);
        rem -= (avail + 1);
        if (curRow + 1 < this.rows.length) {
          this.rows[curRow] += this.rows[curRow + 1];
          this.rows.splice(curRow + 1, 1);
        } else break;
      }
    }
    return out;
  }

  render(): string { return this.rows.join("\n"); }
}

export interface Command { execute(): void; undo(): void; }

export class InsertCommand implements Command {
  constructor(private doc: Document, private row: number, private col: number, private text: string) {}
  execute() { this.doc.insert(this.row, this.col, this.text); }
  undo() { this.doc.remove(this.row, this.col, this.text.length); }
}

export class DeleteCommand implements Command {
  private removed = "";
  constructor(private doc: Document, private row: number, private col: number, private length: number) {}
  execute() { this.removed = this.doc.remove(this.row, this.col, this.length); }
  undo() { this.doc.insert(this.row, this.col, this.removed); }
}

export class Editor {
  private doc = new Document();
  private undoStack: Command[] = [];
  private redoStack: Command[] = [];

  insert(r: number, c: number, t: string) { this.run(new InsertCommand(this.doc, r, c, t)); }
  delete(r: number, c: number, l: number) { this.run(new DeleteCommand(this.doc, r, c, l)); }

  private run(cmd: Command) { cmd.execute(); this.undoStack.push(cmd); this.redoStack.length = 0; }

  undo() {
    const c = this.undoStack.pop();
    if (!c) return;
    c.undo();
    this.redoStack.push(c);
  }

  redo() {
    const c = this.redoStack.pop();
    if (!c) return;
    c.execute();
    this.undoStack.push(c);
  }

  render(): string { return this.doc.render(); }
}

Extensibility

1. "Group-undo — transactional multi-command operations?"

Introduce a CompositeCommand:

java

public class CompositeCommand implements Command {
    private final List<Command> cmds;
    public void execute() { for (Command c : cmds) c.execute(); }
    public void undo() {
        for (int i = cmds.size() - 1; i >= 0; i--) cmds.get(i).undo();
    }
}

Editor.beginTransaction / endTransaction wrap a sequence of commands into one composite before pushing to the undo stack. Undo reverses them in LIFO order.

2. "Persist the command history to disk?"

Serialize each command to a log file on execute. On startup, replay the log to rebuild state. This is the same idea as an append-only journal.

Tradeoff: The log grows forever. Compact periodically by snapshotting the document and truncating older commands.

3. "Collaborative editing across users?"

Explicit scope change. Single-user Command does not compose across users with concurrent edits. You need CRDTs (Yjs, Automerge) or Operational Transformation. Mention it, explicitly decline to solve it in a 45-minute LLD.

What is Expected at Each Level

Level	Expectations
Junior (L4)	Snapshot the whole document per edit (O(N) memory) and store full snapshots in the undo stack. Correct for small inputs.
Mid (L5)	Command pattern with reversible operations. Correct single-line handling; may stumble on multi-line inserts.
Senior (L5A)	Multi-line insert and delete done right, clean `Command` interface, clear history semantics (new edit clears redo), extension story for CompositeCommand.
Staff (L6)	Rope data structure for O(log N) edits on large files, Operational Transformation discussion, persistent history with compaction, IDE-grade performance considerations.

38 — LLD: Text Editor with Undo/Redo ​

Understanding the Problem ​

Requirements ​

Clarifying Questions ​

Final Requirements ​

Core Entities and Relationships ​

Class Design ​

Document ​

Command (interface) ​

InsertCommand ​

DeleteCommand ​

Editor ​

Implementation ​

Core Logic: Multi-line Insert ​

Core Logic: Multi-line Delete ​

Implementations ​

Thread Safety ​

Verification ​

Complete Code Implementation ​

Extensibility ​

1. "Group-undo — transactional multi-command operations?" ​

2. "Persist the command history to disk?" ​

3. "Collaborative editing across users?" ​

What is Expected at Each Level ​

38 — LLD: Text Editor with Undo/Redo

Understanding the Problem

Requirements

Clarifying Questions

Final Requirements

Core Entities and Relationships

Class Design

Document

Command (interface)

InsertCommand

DeleteCommand

Editor

Implementation

Core Logic: Multi-line Insert

Core Logic: Multi-line Delete

Implementations

Thread Safety

Verification

Complete Code Implementation

Extensibility

1. "Group-undo — transactional multi-command operations?"

2. "Persist the command history to disk?"

3. "Collaborative editing across users?"

What is Expected at Each Level