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

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. ```hint 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. ``` #### 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. ```hint Remember enough to reverse Decide what each stack entry must store so that the edit can be reversed exactly, including what a deletion removed. ``` #### 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. ```hint 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. ``` #### 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). ```hint 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. ``` #### 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 ### What a Strong Answer Covers - Correct, tested code for the first three parts, delivered quickly - Clean interfaces so that each part extends the previous ones rather than rewriting them - A precise treatment of concurrency in Part 4, with the tricky cases handled - Awareness of alternatives, such as ropes or piece tables for the buffer and CRDTs for collaboration ### 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?