Katkat
Back

Text Editor in Four Stages: Buffer, Undo/Redo, Trie Autocomplete, Collaborative OT

OpenAISoftware Engineer · Onsite
HardSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

Build a text editor in four stages: a buffer with insert, delete and read, undo and redo with two stacks, trie-based autocomplete ranked by word frequency, and real-time collaborative editing with operational transformation. It tests data structure choice, reversible operations, top-k retrieval and concurrency correctness.

Build the core of a text editor in four stages. Each stage builds on the previous one, so keep the design extensible. Many candidates run out of time before the last stage, so pace yourself and keep the early stages simple and correct.

Clarifying Questions

  • Are positions measured in characters, and can the document contain newlines and non-ASCII characters?
  • How large can documents get, and how frequent are edits compared with reads?
  • Should consecutive typed characters be undone together as one step, or one character at a time?
  • Where do autocomplete word frequencies come from: the current document, the user's history, or a fixed dictionary?
  • For collaboration, is there a central server, or do clients talk to each other directly?

Part 1 — Buffer operations

Implement a text buffer with insert(pos, text), delete(pos, length) and read(pos, length), with validation of positions.

What This Part Should Cover

  • Correct operations with bounds checking
  • Complexity of the chosen structure
  • Better structures for large documents, and their trade-offs

Part 2 — Undo and redo

Add undo() and redo() using two stacks.

What This Part Should Cover

  • Recording each edit with enough information to invert it
  • When the redo stack must be cleared
  • Grouping several small edits into one undoable step

Part 3 — Autocomplete

Add word suggestions: as the user types a prefix, return the top k completions ranked by how frequently each word has been used, using a trie.

What This Part Should Cover

  • A trie supporting word insertion with frequency counts and prefix lookup
  • A deterministic top-k ranking with a tie-break
  • Query cost compared with update cost, and precomputing top-k at each node

Part 4 — Real-time collaboration

Several users now edit the same document at the same time. Design and implement how concurrent edits are combined so that every user ends up with the same text, using operational transformation (OT).

What This Part Should Cover

  • The transformation rules for insert and delete pairs, including ties at the same position and overlapping deletes
  • The convergence property the rules must satisfy, and how to test it
  • System architecture: a server that orders operations, revision numbers, and acknowledgments
  • How undo interacts with collaboration

Hints

Hint 1

Start simple, then justify: Pick the simplest structure that is obviously correct, and be ready to say which operation becomes expensive as documents grow and what you would switch to.

Hint 2

Remember enough to reverse: Decide what each stack entry must store so that the edit can be reversed exactly, including what a deletion removed.

Hint 3

Where to keep the ranking: Consider whether to find the top words under a prefix at query time, or keep them precomputed in the trie, and what each choice costs when frequencies change.

Hint 4

Two edits, one starting point: Take two edits made concurrently on the same document and ask how each must be rewritten to apply correctly after the other, including when they touch the same position or overlapping ranges.

Follow-up questions

  • How would you support a cursor and selection for each collaborator, and keep them correct as others edit?
  • Compare operational transformation with CRDTs for this editor. When would you choose each?
  • How would you persist the document and its history so a crashed server can recover?
  • How would you add language-model suggestions of whole phrases without blocking typing?