17 — LLD: In-Memory Text Editor

Understanding the Problem

An in-memory text editor maintains a mutable document with a cursor, supports insert/delete at the cursor, moves the cursor around, tracks a selection, copies/cuts/pastes through a clipboard, and can undo or redo every edit. The whole thing lives in memory — no persistence, no file I/O — so the entire design collapses to two questions: what data structure holds the text? and how do we replay operations in reverse?

What is an In-Memory Text Editor?

Think of the buffer behind an editor component — the thing that backs a <textarea>, a VS Code document, or an Emacs buffer. A naive string works for a demo but falls apart on real edits: inserting one character into a 1 MB string is O(N) because the whole tail has to shift. Real editors use a gap buffer, a piece table, or a rope. We'll design around a gap buffer because it's simple, fast for sequential typing, and makes the tradeoffs explicit.

Requirements

Clarifying Questions

You: What are the primary operations I need to support?

Interviewer: Insert text at the cursor, delete N characters left or right of the cursor, move the cursor by position or by offset, select a range, cut/copy/paste, and undo/redo.

You: Is the document a single flat buffer, or is it line-oriented (rows of strings)?

Interviewer: Flat buffer. Newlines are just characters. You decide the internal representation.

You: For undo — per-keystroke or per-operation call?

Interviewer: Per-operation call. One call to insert("hello") is one undo step, not five.

You: Does a new edit after some undos clear the redo stack?

Interviewer: Yes. Standard desktop editor semantics.

You: Is there a bound on undo history?

Interviewer: Assume unbounded for the core design. Mention how you'd bound it.

You: Concurrency — multiple writers?

Interviewer: Single-user, single-threaded. No collaborative editing.

You: Find/replace?

Interviewer: A simple find(pattern) that returns match positions is enough.

Final Requirements

insert(text) at the cursor; advances the cursor.
deleteLeft(n) / deleteRight(n) — backspace and forward-delete.
moveCursor(pos) and moveBy(delta) — O(k) in gap-buffer terms, O(1) otherwise.
select(start, end) — mark a range; subsequent operations can operate on it.
copy(), cut(), paste() — clipboard is owned by the editor (single slot).
undo() / redo() — restore buffer and cursor state. New edit clears redo.
find(pattern) -> number[] — return all match start indices.
render() -> string — the current document as a flat string.

Out of scope: Persistence, syntax highlighting, multi-cursor, collaborative editing / CRDTs, Unicode grapheme-cluster cursor movement, large-file streaming.

Core Entities and Relationships

Entity	Responsibility
`GapBuffer`	Stores the text. Owns the gap. Exposes `insert`, `deleteLeft`, `deleteRight`, `moveGapTo`, `toString`, `charAt`, `length`.
`Selection`	A value object holding `start`, `end`. Normalized so `start <= end`.
`Clipboard`	A single-slot text holder.
`Command`	Interface — `execute()` and `undo()`. Each command captures enough state to reverse itself.
`InsertCommand` / `DeleteCommand` / `PasteCommand` / `CutCommand`	Concrete commands. Each captures cursor + any removed text.
`TextEditor`	Facade. Owns the buffer, selection, clipboard, and two command stacks.

Why separate GapBuffer from TextEditor? The editor is a facade over user-facing concepts (cursor, selection, clipboard, history). The gap buffer is a low-level storage detail. Keeping them apart means we could later swap in a piece table or rope without touching command or editor code.

Why does every command capture the cursor? Undo isn't just "put the text back." It's "put the editor back in the state the user saw." If I type abc, move cursor to position 0, then undo the type — the cursor should land back at position 3 where it was when the edit happened. Commands that forget cursor state produce a jarring UX.

Class Design

GapBuffer — why this data structure

A gap buffer is a flat array with a movable empty region (the "gap"). The cursor sits at the start of the gap. Inserts fill the gap from the left; deletes extend the gap. Moving the cursor shifts characters across the gap.

"hello world", cursor at 5:
  indices: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
  buffer : h e l l o _ _ _ _ _  _   w  o  r  l  d
                     ^ gap start (cursor)     ^ gap end

Operation	Gap buffer	Flat string	Array of lines	Rope
Insert at cursor	O(1) amortized	O(N)	O(line length)	O(log N)
Delete at cursor	O(1)	O(N)	O(line length)	O(log N)
Move cursor by k	O(k)	O(1)	O(1) within a line	O(log N)
Render full string	O(N)	O(1)	O(N)	O(N)
Code complexity	Low	Trivial	Low	High

Sequential typing is the dominant workload in an editor. The gap buffer wins decisively there because the gap stays where you're typing — no copying. The loss on cursor movement is acceptable because users type far more characters than they jump around.

GapBuffer

State:

buffer: string[] — the raw character slots (gap slots hold sentinel values; we track the gap explicitly, not by contents).
gapStart: number — inclusive index of the first gap slot (equals the cursor position in logical coordinates).
gapEnd: number — exclusive index one past the last gap slot.

Logical document length is buffer.length - (gapEnd - gapStart).

Methods:

insert(text: string) — write characters into gap, advance gapStart. Grow if needed.
deleteLeft(n) — extend gap leftward; returns the removed text so commands can remember it.
deleteRight(n) — extend gap rightward; returns removed text.
moveGapTo(pos) — shift characters across the gap to reposition it.
charAt(i) / length / toString() — read operations that skip the gap.

Selection

typescript

interface Selection {
  readonly start: number;
  readonly end: number; // exclusive
}

Immutable. Store normalized (start <= end). An empty selection (start === end) means no selection; the cursor position alone governs.

Command

typescript

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

TextEditor

State:

buffer: GapBuffer
selection: Selection | null
clipboard: string
undoStack: Command[]
redoStack: Command[]

Methods: insert, deleteLeft, deleteRight, moveCursor, moveBy, select, clearSelection, copy, cut, paste, undo, redo, find, render, cursor (getter).

Invariant after every public mutation: redoStack is cleared unless the mutation is an undo/redo.

Implementation

GapBuffer

typescript

class GapBuffer {
  private buffer: string[];
  private gapStart: number;
  private gapEnd: number;

  private static readonly INITIAL_CAPACITY = 64;
  private static readonly GROWTH_FACTOR = 2;

  constructor(initial: string = "") {
    const capacity = Math.max(GapBuffer.INITIAL_CAPACITY, initial.length * 2);
    this.buffer = new Array(capacity);
    for (let i = 0; i < initial.length; i++) this.buffer[i] = initial[i];
    this.gapStart = initial.length;
    this.gapEnd = capacity;
  }

  get length(): number {
    return this.buffer.length - (this.gapEnd - this.gapStart);
  }

  get cursor(): number {
    return this.gapStart;
  }

  charAt(i: number): string {
    if (i < 0 || i >= this.length) throw new RangeError(`index ${i} out of bounds`);
    const physical = i < this.gapStart ? i : i + (this.gapEnd - this.gapStart);
    return this.buffer[physical];
  }

  toString(): string {
    const left = this.buffer.slice(0, this.gapStart).join("");
    const right = this.buffer.slice(this.gapEnd).join("");
    return left + right;
  }

  moveGapTo(pos: number): void {
    if (pos < 0 || pos > this.length) throw new RangeError(`position ${pos} out of bounds`);
    if (pos < this.gapStart) {
      // Shift characters rightward across the gap
      const shift = this.gapStart - pos;
      for (let i = 0; i < shift; i++) {
        this.buffer[this.gapEnd - 1 - i] = this.buffer[this.gapStart - 1 - i];
      }
      this.gapStart -= shift;
      this.gapEnd -= shift;
    } else if (pos > this.gapStart) {
      // Shift characters leftward across the gap
      const shift = pos - this.gapStart;
      for (let i = 0; i < shift; i++) {
        this.buffer[this.gapStart + i] = this.buffer[this.gapEnd + i];
      }
      this.gapStart += shift;
      this.gapEnd += shift;
    }
  }

  insert(text: string): void {
    this.ensureGap(text.length);
    for (let i = 0; i < text.length; i++) {
      this.buffer[this.gapStart + i] = text[i];
    }
    this.gapStart += text.length;
  }

  deleteLeft(n: number): string {
    const count = Math.min(n, this.gapStart);
    const removed = this.buffer.slice(this.gapStart - count, this.gapStart).join("");
    this.gapStart -= count;
    return removed;
  }

  deleteRight(n: number): string {
    const available = this.buffer.length - this.gapEnd;
    const count = Math.min(n, available);
    const removed = this.buffer.slice(this.gapEnd, this.gapEnd + count).join("");
    this.gapEnd += count;
    return removed;
  }

  private ensureGap(needed: number): void {
    const gapSize = this.gapEnd - this.gapStart;
    if (gapSize >= needed) return;

    const newCapacity = Math.max(
      this.buffer.length * GapBuffer.GROWTH_FACTOR,
      this.length + needed + GapBuffer.INITIAL_CAPACITY,
    );
    const newBuffer = new Array(newCapacity);
    // Copy left segment
    for (let i = 0; i < this.gapStart; i++) newBuffer[i] = this.buffer[i];
    // Copy right segment to end of new buffer
    const rightLen = this.buffer.length - this.gapEnd;
    for (let i = 0; i < rightLen; i++) {
      newBuffer[newCapacity - rightLen + i] = this.buffer[this.gapEnd + i];
    }
    this.buffer = newBuffer;
    this.gapEnd = newCapacity - rightLen;
  }
}

Why string[] instead of a single string? In JavaScript a string is immutable — any mutation allocates a new string, which defeats the whole point of a gap buffer. A fixed-size mutable array gives us in-place slot assignment. In a language with native mutable char arrays (Java's char[], C's char*), you'd use those directly.

Why amortized O(1) insert? Most inserts just write into the gap. When the gap fills, ensureGap doubles capacity — O(N) work, but it happens O(log N) times over N inserts, so the amortized cost per insert is O(1).

Commands

Each command captures the cursor before the operation and restores both text and cursor on undo.

typescript

class InsertCommand implements Command {
  constructor(
    private readonly editor: EditorInternals,
    private readonly pos: number,
    private readonly text: string,
  ) {}

  execute(): void {
    this.editor.moveCursorTo(this.pos);
    this.editor.buffer.insert(this.text);
  }

  undo(): void {
    this.editor.moveCursorTo(this.pos + this.text.length);
    this.editor.buffer.deleteLeft(this.text.length);
  }
}

class DeleteCommand implements Command {
  private removed = "";

  constructor(
    private readonly editor: EditorInternals,
    private readonly pos: number,
    private readonly count: number,
    private readonly direction: "left" | "right",
  ) {}

  execute(): void {
    this.editor.moveCursorTo(this.pos);
    this.removed =
      this.direction === "left"
        ? this.editor.buffer.deleteLeft(this.count)
        : this.editor.buffer.deleteRight(this.count);
  }

  undo(): void {
    if (this.direction === "left") {
      // Left-delete removed chars [pos - count, pos). Restore by inserting at pos - count.
      this.editor.moveCursorTo(this.pos - this.removed.length);
    } else {
      this.editor.moveCursorTo(this.pos);
    }
    this.editor.buffer.insert(this.removed);
  }
}

EditorInternals is a narrow interface the editor exposes to commands — it decouples commands from the public editor API.

typescript

interface EditorInternals {
  readonly buffer: GapBuffer;
  moveCursorTo(pos: number): void;
}

TextEditor

typescript

class TextEditor implements EditorInternals {
  public readonly buffer: GapBuffer;
  private selection: Selection | null = null;
  private clipboard: string = "";
  private undoStack: Command[] = [];
  private redoStack: Command[] = [];

  constructor(initial: string = "") {
    this.buffer = new GapBuffer(initial);
  }

  get cursor(): number {
    return this.buffer.cursor;
  }

  render(): string {
    return this.buffer.toString();
  }

  moveCursor(pos: number): void {
    this.buffer.moveGapTo(pos);
    this.selection = null;
  }

  moveBy(delta: number): void {
    const target = Math.max(0, Math.min(this.buffer.length, this.cursor + delta));
    this.moveCursor(target);
  }

  moveCursorTo(pos: number): void {
    // EditorInternals hook for commands. Does NOT clear selection or history.
    this.buffer.moveGapTo(pos);
  }

  select(start: number, end: number): void {
    const lo = Math.max(0, Math.min(start, end));
    const hi = Math.min(this.buffer.length, Math.max(start, end));
    this.selection = { start: lo, end: hi };
  }

  clearSelection(): void {
    this.selection = null;
  }

  insert(text: string): void {
    // If there's a selection, replace it atomically.
    if (this.selection && this.selection.start < this.selection.end) {
      this.replaceSelection(text);
      return;
    }
    const cmd = new InsertCommand(this, this.cursor, text);
    this.run(cmd);
  }

  deleteLeft(n: number = 1): void {
    if (this.selection && this.selection.start < this.selection.end) {
      this.replaceSelection("");
      return;
    }
    if (this.cursor === 0) return;
    const count = Math.min(n, this.cursor);
    const cmd = new DeleteCommand(this, this.cursor, count, "left");
    this.run(cmd);
  }

  deleteRight(n: number = 1): void {
    if (this.selection && this.selection.start < this.selection.end) {
      this.replaceSelection("");
      return;
    }
    if (this.cursor === this.buffer.length) return;
    const count = Math.min(n, this.buffer.length - this.cursor);
    const cmd = new DeleteCommand(this, this.cursor, count, "right");
    this.run(cmd);
  }

  copy(): void {
    if (!this.selection || this.selection.start === this.selection.end) return;
    this.clipboard = this.readRange(this.selection.start, this.selection.end);
  }

  cut(): void {
    if (!this.selection || this.selection.start === this.selection.end) return;
    this.clipboard = this.readRange(this.selection.start, this.selection.end);
    this.replaceSelection("");
  }

  paste(): void {
    if (this.clipboard.length === 0) return;
    this.insert(this.clipboard);
  }

  undo(): void {
    const cmd = this.undoStack.pop();
    if (!cmd) return;
    cmd.undo();
    this.redoStack.push(cmd);
    this.selection = null;
  }

  redo(): void {
    const cmd = this.redoStack.pop();
    if (!cmd) return;
    cmd.execute();
    this.undoStack.push(cmd);
    this.selection = null;
  }

  find(pattern: string): number[] {
    if (pattern.length === 0) return [];
    const text = this.render();
    const hits: number[] = [];
    let idx = text.indexOf(pattern);
    while (idx !== -1) {
      hits.push(idx);
      idx = text.indexOf(pattern, idx + 1);
    }
    return hits;
  }

  private run(cmd: Command): void {
    cmd.execute();
    this.undoStack.push(cmd);
    this.redoStack = [];
    this.selection = null;
  }

  private replaceSelection(replacement: string): void {
    const { start, end } = this.selection!;
    // Compose as: delete-range + insert. Capture as one CompositeCommand for atomic undo.
    const cmd = new CompositeCommand([
      new DeleteRangeCommand(this, start, end),
      new InsertCommand(this, start, replacement),
    ]);
    this.run(cmd);
  }

  private readRange(start: number, end: number): string {
    let out = "";
    for (let i = start; i < end; i++) out += this.buffer.charAt(i);
    return out;
  }
}

class DeleteRangeCommand implements Command {
  private removed = "";

  constructor(
    private readonly editor: TextEditor,
    private readonly start: number,
    private readonly end: number,
  ) {}

  execute(): void {
    this.editor.moveCursorTo(this.end);
    this.removed = this.editor.buffer.deleteLeft(this.end - this.start);
  }

  undo(): void {
    this.editor.moveCursorTo(this.start);
    this.editor.buffer.insert(this.removed);
  }
}

class CompositeCommand implements Command {
  constructor(private readonly commands: Command[]) {}

  execute(): void {
    for (const c of this.commands) c.execute();
  }

  undo(): void {
    // Reverse order is essential.
    for (let i = this.commands.length - 1; i >= 0; i--) this.commands[i].undo();
  }
}

Why CompositeCommand for replace? Typing over a selection is one user action but two internal operations (delete + insert). If we pushed them as two commands, undo would first undo the insert, then a second undo would undo the delete — the user would have to undo twice to get back. Composing them keeps the undo grain aligned with user intent.

Edge Cases

Delete at boundaries — deleteLeft(5) when the cursor is at position 2 clamps to 2. Commands capture the actual count removed, not the requested count.
Paste with empty clipboard — No-op, no command pushed. Keeps undo history clean.
Undo with empty stack — No-op. Same for redo.
New edit mid-undo — run() clears redoStack. The undone history is permanently lost, matching desktop-editor semantics.
Selection bounds outside document — select(start, end) clamps into [0, length].
Find with empty pattern — Returns [] rather than every position, because every position "matches" an empty string and that's rarely what the caller wants.
Cursor restoration on undo — Every command restores the cursor to where the user's view would expect it. Crucial for UX.
Growing the buffer — ensureGap preserves the gap position logically (it lands at gapStart) while physically relocating the right segment to the end of the new buffer.

Verification

Setup: new TextEditor("hello"). Initial state: buffer="hello", cursor=5, no selection, empty clipboard, empty history.

Step 1: insert(" world").

Command: InsertCommand(pos=5, text=" world").
After execute: buffer="hello world", cursor=11.
undoStack: [Insert_1].

Step 2: moveCursor(5) then deleteLeft(5).

moveCursor is not a command — history unchanged. Cursor=5.
deleteLeft(5): command Delete(pos=5, count=5, left). After execute: buffer=" world", cursor=0. removed="hello".
undoStack: [Insert_1, Delete_2].

Step 3: undo().

Pops Delete_2. Undo moves cursor to pos - removed.length = 0, inserts "hello" → buffer="hello world", cursor=5.
redoStack: [Delete_2].

Step 4: undo().

Pops Insert_1. Undo moves cursor to pos + text.length = 11, deletes left 6 → buffer="hello", cursor=5.
redoStack: [Delete_2, Insert_1].

Step 5: redo().

Pops Insert_1. Execute: cursor=5, insert " world" → buffer="hello world", cursor=11.
undoStack: [Insert_1]; redoStack: [Delete_2].

Step 6: insert("!") (a new edit after redo).

run() clears redoStack. Delete_2 is permanently discarded.
Buffer="hello world!", cursor=12. undoStack: [Insert_1, Insert_3]; redoStack: [].

Step 7: select(0, 5); cut().

cut reads the range ("hello"), stores in clipboard, composes DeleteRange(0,5)+Insert(0,"") and runs.
Buffer=" world!", cursor=0, clipboard="hello".

Step 8: moveCursor(7); paste().

paste() calls insert("hello"). Cursor=7 before insert, =12 after. Buffer=" world!hello".

Step 9: undo().

Undoes the paste (InsertCommand). Buffer=" world!", cursor=7.

Step 10: find("o").

Linear scan of " world!" → [2]. (Only one o.)

Complete Code Implementation

typescript

interface Selection {
  readonly start: number;
  readonly end: number;
}

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

interface EditorInternals {
  readonly buffer: GapBuffer;
  moveCursorTo(pos: number): void;
}

class GapBuffer {
  private buffer: string[];
  private gapStart: number;
  private gapEnd: number;
  private static readonly INITIAL_CAPACITY = 64;
  private static readonly GROWTH_FACTOR = 2;

  constructor(initial: string = "") {
    const capacity = Math.max(GapBuffer.INITIAL_CAPACITY, initial.length * 2);
    this.buffer = new Array(capacity);
    for (let i = 0; i < initial.length; i++) this.buffer[i] = initial[i];
    this.gapStart = initial.length;
    this.gapEnd = capacity;
  }

  get length(): number {
    return this.buffer.length - (this.gapEnd - this.gapStart);
  }

  get cursor(): number {
    return this.gapStart;
  }

  charAt(i: number): string {
    if (i < 0 || i >= this.length) throw new RangeError(`index ${i} out of bounds`);
    const physical = i < this.gapStart ? i : i + (this.gapEnd - this.gapStart);
    return this.buffer[physical];
  }

  toString(): string {
    return this.buffer.slice(0, this.gapStart).join("") + this.buffer.slice(this.gapEnd).join("");
  }

  moveGapTo(pos: number): void {
    if (pos < 0 || pos > this.length) throw new RangeError(`position ${pos} out of bounds`);
    if (pos < this.gapStart) {
      const shift = this.gapStart - pos;
      for (let i = 0; i < shift; i++) {
        this.buffer[this.gapEnd - 1 - i] = this.buffer[this.gapStart - 1 - i];
      }
      this.gapStart -= shift;
      this.gapEnd -= shift;
    } else if (pos > this.gapStart) {
      const shift = pos - this.gapStart;
      for (let i = 0; i < shift; i++) {
        this.buffer[this.gapStart + i] = this.buffer[this.gapEnd + i];
      }
      this.gapStart += shift;
      this.gapEnd += shift;
    }
  }

  insert(text: string): void {
    this.ensureGap(text.length);
    for (let i = 0; i < text.length; i++) this.buffer[this.gapStart + i] = text[i];
    this.gapStart += text.length;
  }

  deleteLeft(n: number): string {
    const count = Math.min(n, this.gapStart);
    const removed = this.buffer.slice(this.gapStart - count, this.gapStart).join("");
    this.gapStart -= count;
    return removed;
  }

  deleteRight(n: number): string {
    const available = this.buffer.length - this.gapEnd;
    const count = Math.min(n, available);
    const removed = this.buffer.slice(this.gapEnd, this.gapEnd + count).join("");
    this.gapEnd += count;
    return removed;
  }

  private ensureGap(needed: number): void {
    const gapSize = this.gapEnd - this.gapStart;
    if (gapSize >= needed) return;
    const newCapacity = Math.max(
      this.buffer.length * GapBuffer.GROWTH_FACTOR,
      this.length + needed + GapBuffer.INITIAL_CAPACITY,
    );
    const newBuffer = new Array(newCapacity);
    for (let i = 0; i < this.gapStart; i++) newBuffer[i] = this.buffer[i];
    const rightLen = this.buffer.length - this.gapEnd;
    for (let i = 0; i < rightLen; i++) {
      newBuffer[newCapacity - rightLen + i] = this.buffer[this.gapEnd + i];
    }
    this.buffer = newBuffer;
    this.gapEnd = newCapacity - rightLen;
  }
}

class InsertCommand implements Command {
  constructor(
    private readonly editor: EditorInternals,
    private readonly pos: number,
    private readonly text: string,
  ) {}
  execute(): void {
    this.editor.moveCursorTo(this.pos);
    this.editor.buffer.insert(this.text);
  }
  undo(): void {
    this.editor.moveCursorTo(this.pos + this.text.length);
    this.editor.buffer.deleteLeft(this.text.length);
  }
}

class DeleteCommand implements Command {
  private removed = "";
  constructor(
    private readonly editor: EditorInternals,
    private readonly pos: number,
    private readonly count: number,
    private readonly direction: "left" | "right",
  ) {}
  execute(): void {
    this.editor.moveCursorTo(this.pos);
    this.removed =
      this.direction === "left"
        ? this.editor.buffer.deleteLeft(this.count)
        : this.editor.buffer.deleteRight(this.count);
  }
  undo(): void {
    if (this.direction === "left") {
      this.editor.moveCursorTo(this.pos - this.removed.length);
    } else {
      this.editor.moveCursorTo(this.pos);
    }
    this.editor.buffer.insert(this.removed);
  }
}

class DeleteRangeCommand implements Command {
  private removed = "";
  constructor(
    private readonly editor: EditorInternals,
    private readonly start: number,
    private readonly end: number,
  ) {}
  execute(): void {
    this.editor.moveCursorTo(this.end);
    this.removed = this.editor.buffer.deleteLeft(this.end - this.start);
  }
  undo(): void {
    this.editor.moveCursorTo(this.start);
    this.editor.buffer.insert(this.removed);
  }
}

class CompositeCommand implements Command {
  constructor(private readonly commands: Command[]) {}
  execute(): void {
    for (const c of this.commands) c.execute();
  }
  undo(): void {
    for (let i = this.commands.length - 1; i >= 0; i--) this.commands[i].undo();
  }
}

class TextEditor implements EditorInternals {
  public readonly buffer: GapBuffer;
  private selection: Selection | null = null;
  private clipboard: string = "";
  private undoStack: Command[] = [];
  private redoStack: Command[] = [];

  constructor(initial: string = "") {
    this.buffer = new GapBuffer(initial);
  }

  get cursor(): number {
    return this.buffer.cursor;
  }

  render(): string {
    return this.buffer.toString();
  }

  moveCursor(pos: number): void {
    this.buffer.moveGapTo(pos);
    this.selection = null;
  }

  moveBy(delta: number): void {
    const target = Math.max(0, Math.min(this.buffer.length, this.cursor + delta));
    this.moveCursor(target);
  }

  moveCursorTo(pos: number): void {
    this.buffer.moveGapTo(pos);
  }

  select(start: number, end: number): void {
    const lo = Math.max(0, Math.min(start, end));
    const hi = Math.min(this.buffer.length, Math.max(start, end));
    this.selection = { start: lo, end: hi };
  }

  clearSelection(): void {
    this.selection = null;
  }

  insert(text: string): void {
    if (text.length === 0) return;
    if (this.selection && this.selection.start < this.selection.end) {
      this.replaceSelection(text);
      return;
    }
    this.run(new InsertCommand(this, this.cursor, text));
  }

  deleteLeft(n: number = 1): void {
    if (this.selection && this.selection.start < this.selection.end) {
      this.replaceSelection("");
      return;
    }
    if (this.cursor === 0 || n <= 0) return;
    const count = Math.min(n, this.cursor);
    this.run(new DeleteCommand(this, this.cursor, count, "left"));
  }

  deleteRight(n: number = 1): void {
    if (this.selection && this.selection.start < this.selection.end) {
      this.replaceSelection("");
      return;
    }
    if (this.cursor === this.buffer.length || n <= 0) return;
    const count = Math.min(n, this.buffer.length - this.cursor);
    this.run(new DeleteCommand(this, this.cursor, count, "right"));
  }

  copy(): void {
    if (!this.selection || this.selection.start === this.selection.end) return;
    this.clipboard = this.readRange(this.selection.start, this.selection.end);
  }

  cut(): void {
    if (!this.selection || this.selection.start === this.selection.end) return;
    this.clipboard = this.readRange(this.selection.start, this.selection.end);
    this.replaceSelection("");
  }

  paste(): void {
    if (this.clipboard.length === 0) return;
    this.insert(this.clipboard);
  }

  undo(): void {
    const cmd = this.undoStack.pop();
    if (!cmd) return;
    cmd.undo();
    this.redoStack.push(cmd);
    this.selection = null;
  }

  redo(): void {
    const cmd = this.redoStack.pop();
    if (!cmd) return;
    cmd.execute();
    this.undoStack.push(cmd);
    this.selection = null;
  }

  find(pattern: string): number[] {
    if (pattern.length === 0) return [];
    const text = this.render();
    const hits: number[] = [];
    let idx = text.indexOf(pattern);
    while (idx !== -1) {
      hits.push(idx);
      idx = text.indexOf(pattern, idx + 1);
    }
    return hits;
  }

  private run(cmd: Command): void {
    cmd.execute();
    this.undoStack.push(cmd);
    this.redoStack = [];
    this.selection = null;
  }

  private replaceSelection(replacement: string): void {
    const { start, end } = this.selection!;
    const ops: Command[] = [new DeleteRangeCommand(this, start, end)];
    if (replacement.length > 0) ops.push(new InsertCommand(this, start, replacement));
    this.run(new CompositeCommand(ops));
  }

  private readRange(start: number, end: number): string {
    let out = "";
    for (let i = start; i < end; i++) out += this.buffer.charAt(i);
    return out;
  }
}

// ---- Demo ----

const ed = new TextEditor("hello");
ed.insert(" world");
console.log(ed.render()); // "hello world"
ed.moveCursor(5);
ed.deleteLeft(5);
console.log(ed.render()); // " world"
ed.undo();
console.log(ed.render()); // "hello world"
ed.undo();
console.log(ed.render()); // "hello"
ed.redo();
console.log(ed.render()); // "hello world"
ed.select(0, 5);
ed.cut();
console.log(ed.render()); // " world"
ed.moveCursor(6);
ed.paste();
console.log(ed.render()); // " worldhello"
console.log(ed.find("o")); // [2, 8]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332

Extensibility

1. Bounded undo history

Unbounded history leaks memory on long sessions. Add a cap:

typescript

class TextEditor {
  private static readonly MAX_HISTORY = 500;

  private run(cmd: Command): void {
    cmd.execute();
    this.undoStack.push(cmd);
    if (this.undoStack.length > TextEditor.MAX_HISTORY) this.undoStack.shift();
    this.redoStack = [];
    this.selection = null;
  }
}

Tradeoff: shift() on a JS array is O(n). For large caps, use a circular buffer or a Deque. The cap itself is a product call — too small and power users lose work; too large and long-running documents balloon in memory.

2. Per-keystroke coalescing

Real editors group consecutive single-character inserts into one undo step until the user pauses, deletes, or moves the cursor. Implement by checking the top of undoStack in insert(): if it's a recent InsertCommand that ends at the current cursor, extend its text instead of pushing a new command.

Tradeoff: "Recent" needs a time window (say 500 ms). Adds a clock dependency and a coalescing heuristic — more code to get wrong. Worth it for UX.

3. Piece table or rope swap

Swap GapBuffer for a PieceTable (what VS Code uses) or a Rope. The EditorInternals interface deliberately exposes only buffer.insert, buffer.delete*, and cursor operations — a minimal seam.

When to swap	Why
Loading large read-only files	Piece table keeps the original buffer immutable; edits are small "pieces" stitched on top. Opening a 1 GB file is instant.
Frequent non-local edits	Rope handles scattered edits across the document better than gap buffer (gap buffer pays O(k) to move the gap).

4. Line-indexed view

For row/column reporting, maintain a side structure mapping line number to offset. Update on insert/delete by scanning the affected region for newlines. Many real editors use a line-array + gap buffer hybrid.

5. Observer hooks

Expose onChange(listener) so UI components can re-render on buffer changes. Commands would invoke the listener after mutation.

Tradeoff: Synchronous callbacks in commands make undo/redo fire listeners too — usually what you want. Async listeners risk ordering bugs.

6. Collaborative editing

Single-threaded in-memory editor → collaborative is a rewrite, not an extension. You'd need CRDTs (Yjs, Automerge) or Operational Transform. Flag this early in the interview to avoid scope creep.

What is Expected at Each Level

Level	Expectations
Junior	Implement using a single string or `string[]`. Insert/delete/move work correctly. Naive undo by snapshotting the whole string. Explain at least one weakness of the design.
Mid-level	Pick a real editor data structure (gap buffer, piece table) and justify the choice against alternatives. Command pattern for undo/redo with cursor restoration. Selection + clipboard. Composite command for replace. Handle edge cases (boundary deletes, empty clipboard, empty pattern).
Senior	Everything above plus: amortized complexity analysis of the gap buffer, discussion of bounded history + coalescing, a clean `EditorInternals` seam that allows swapping storage, per-keystroke vs per-operation undo tradeoff, scope boundary for collaborative editing (CRDT/OT is a different system), observer hooks for UI integration.

17 — LLD: In-Memory Text Editor ​

Understanding the Problem ​

Requirements ​

Clarifying Questions ​

Final Requirements ​

Core Entities and Relationships ​

Class Design ​

GapBuffer — why this data structure ​

GapBuffer ​

Selection ​

Command ​

TextEditor ​

Implementation ​

GapBuffer ​

Commands ​

TextEditor ​

Edge Cases ​

Verification ​

Complete Code Implementation ​

Extensibility ​

1. Bounded undo history ​

2. Per-keystroke coalescing ​

3. Piece table or rope swap ​

4. Line-indexed view ​

5. Observer hooks ​

6. Collaborative editing ​

What is Expected at Each Level ​

17 — LLD: In-Memory Text Editor

Understanding the Problem

Requirements

Clarifying Questions

Final Requirements

Core Entities and Relationships

Class Design

GapBuffer — why this data structure

GapBuffer

Selection

Command

TextEditor

Implementation

GapBuffer

Commands

TextEditor

Edge Cases

Verification

Complete Code Implementation

Extensibility

1. Bounded undo history

2. Per-keystroke coalescing

3. Piece table or rope swap

4. Line-indexed view

5. Observer hooks

6. Collaborative editing

What is Expected at Each Level