1. Problem and context
Implement the core buffer for a single-cursor text editor. The logical text is a sequence of characters; the cursor sits between two characters. Support left(), right(), insert(ch), delete(), and text().
Represent storage as an array with an unused interval called the gap. Let gapStart be inclusive and gapEnd exclusive. The visible text is the prefix before gapStart followed by the suffix at and after gapEnd. ETH Zurich's exercise uses this representation and asks candidates to verify both behavior and bounds. A public Google L4 interview report also describes a text-editor/bookkeeping implementation round that emphasized data-structure trade-offs, dry runs, and accurate complexity.
2. What the interviewer evaluates
- State modeling: Can you state what the two indices mean without confusing logical length and array capacity?
- Invariants: Do every operation and resize preserve valid bounds and the same logical text?
- Boundary discipline: Are empty, full, left-edge, right-edge, and one-character buffers explicit?
- Complexity reasoning: Can you explain why nearby edits are cheap and a long cursor jump is linear in distance?
- Design judgment: Can you say when a gap buffer stops fitting large files, multiple cursors, or collaborative editing?
A weak answer writes array moves first and discovers off-by-one errors later. A strong answer derives each move from the representation and tests it against a simple string model.
3. Questions to clarify first
Is the cursor a character index or a boundary?
Use a boundary: cursor equals the number of logical characters to its left. This makes cursor=0 the left edge and cursor=length the right edge, and it defines delete() as removing the character immediately before the cursor.
What does delete mean at the cursor?
Confirm whether Backspace or Delete is intended. This article uses Backspace semantics: move the gap left by one and enlarge it. A forward-delete operation would consume the first character after the gap instead.
What storage and text model are required?
Clarify bytes versus Unicode scalar values, maximum document size, and whether undo, random line lookup, multiple cursors, or concurrent edits are required. Those requirements can change the data structure rather than merely add methods.
4. A 30-second answer framework
“I would store the document in one array with a gap at the cursor. gapStart is the cursor boundary and gapEnd marks the first suffix character; the logical text is the prefix plus suffix. Insertion writes at gapStart and advances it. Backspace moves one character from the prefix across the gap and decrements both indices. Moving right copies one suffix character to the prefix side and advances both indices. If the gap is empty, grow the array and create a larger gap. I would assert bounds and a string-model equivalence after every operation. Nearby edits are amortized constant time; moving the gap is linear in distance, so large files or many cursors may need a piece table or rope.”
5. Step-by-step solution
Step 1: State the representation invariant
For capacity n, require 0 ≤ gapStart ≤ gapEnd ≤ n. The logical length is n - (gapEnd - gapStart). The logical sequence is buffer[0:gapStart] concatenated with buffer[gapEnd:n]. Values inside the gap are ignored and need not be initialized.
Step 2: Move left
If gapStart == 0, the cursor is already at the left edge. Otherwise decrement gapStart and gapEnd, then copy the character that was immediately before the cursor into the new last gap position. The prefix loses one character and the suffix gains none; the copied character is now logically before the gap.
Step 3: Move right
If gapEnd == n, the cursor is at the right edge. Otherwise copy buffer[gapEnd] into buffer[gapStart], then increment both indices. The first suffix character crosses the gap, preserving sequence order. The order of copy and index updates matters when the gap has one slot.
Step 4: Insert
If gapStart == gapEnd, call grow() before writing. Store the character at buffer[gapStart] and increment gapStart. The new character becomes the last item in the prefix, exactly at the cursor's former boundary.
Step 5: Delete backward
If gapStart == 0, there is no character to the left. Otherwise decrement gapStart; the gap now includes the removed character. No array shift is needed. The logical sequence loses its final prefix character.
Step 6: Grow without changing text
Allocate a larger array, copy the prefix to the same indices, and copy the suffix to the end of the new array. Keep gapStart unchanged and set the new gapEnd so the suffix length stays constant. A geometric capacity policy such as doubling gives amortized constant insertion when edits stay near the gap, but memory limits may justify a smaller growth factor.
Step 7: Choose the next structure deliberately
A gap buffer is attractive for one active cursor and local edits because the hot region stays contiguous. A piece table preserves original and append-only buffers and is useful for undo-oriented editors. A rope or tree of chunks handles large documents and edits spread across distant positions. A collaborative editor adds operation transformation or CRDT requirements that a gap buffer does not solve.
6. High-quality sample answer
“I model the cursor as a boundary and keep two indices around an unused gap. The invariant is 0 ≤ gapStart ≤ gapEnd ≤ capacity; the logical text is the prefix before the gap plus the suffix after it. Insertion consumes one gap slot. Backspace decrements gapStart, and right-arrow copies one suffix character to the prefix side while incrementing both indices. Left-arrow does the symmetric copy in the opposite direction. When the gap is empty I grow storage by copying the suffix to the new tail, which preserves the logical sequence.
I would test the operations against a simple string plus cursor model, including an empty buffer, a full gap, both edges, one-character text, repeated reversals, and growth. Local edits are amortized O(1); a cursor move costs O(1) per crossed character, and a resize costs O(n). For large files, multiple cursors, or collaborative edits I would switch to a piece table or rope because the single contiguous gap becomes the bottleneck.”
7. Common mistakes
- Treating
gapEndas inclusive → Copies or bounds checks one cell too far → Define the gap as[gapStart, gapEnd)and test an empty gap. - Moving right after incrementing first → Reads the wrong suffix cell → Copy
buffer[gapEnd]tobuffer[gapStart]before changing either index. - Deleting by clearing an array cell → Leaves logical length and cursor unchanged → Expand the gap by decrementing
gapStart. - Growing by moving only the gap → Reorders or loses the suffix → Copy the suffix as a block to the new array's end.
- Using bytes without a contract → Can split a multi-byte character → Declare byte or scalar semantics before implementing cursor movement.
- Claiming every edit is
O(1)→ Ignores long cursor travel and resize → State amortized local-edit cost and the linear movement/growth cases. - Using a gap buffer for collaboration → Confuses local storage with merge semantics → Choose a piece table, rope, or CRDT architecture based on collaboration requirements.
8. Follow-up questions
How would you implement forward Delete?
If gapEnd == capacity, there is no character after the cursor. Otherwise increment gapEnd; the first suffix character enters the gap and disappears from the logical sequence. This is the mirror of Backspace and preserves the same invariant.
What is the worst case for moving the cursor?
Moving across k characters performs k constant-time copies, so it is O(k). Jumping from one end to the other is O(length). A line index or chunked structure can reduce navigation work when the editor frequently jumps to distant positions.
How would you add undo?
Record edit commands or inverse ranges rather than snapshots of the entire array. A piece table can make inserted text append-only and simplify historical references, while a gap buffer needs an explicit operation log and cursor positions.
How do you verify the implementation?
Run randomized operation traces against a reference pair (string, cursor). After each operation, compare text(), cursor position, and bounds. Add assertions that every array access is within capacity; the ETH Zurich exercise explicitly asks for behavior and bounds verification.