Text Editor with Undo/Redo

Prompt

"Design a text editor. It supports typing text at a cursor, deleting characters, moving the cursor, and unlimited undo and redo. Show me the classes and then implement undo and redo."

Clarifying questions

• Single cursor, single buffer? Yes. No selections, no multiple cursors. Selections are a follow-up.
• What operations exactly? insert(text) at the cursor, delete(n) removes n characters before the cursor (backspace semantics), move(pos) moves the cursor, undo(), redo().
• Does a cursor move count as an undoable action? No, only edits. But undo must restore the cursor to where it was before the undone edit; that is the detail interviewers watch for.
• What happens to redo history after a new edit following an undo? It is discarded. Linear history, not a tree.
• Is coalescing required (typing "hello" undoes as one step)? Not initially. Design so it can be added.
• Size of the document? Assume up to a few megabytes. Enough that an O(n) insert matters if you do a million of them, not enough to need a rope on day one.

Requirements

Functional

• Insert at the cursor and delete before the cursor, with the cursor updating accordingly.
• Unlimited undo and redo with exact inverse behavior including cursor position.
• A new edit after undo clears the redo history.
• Retrieve the current text and cursor position.

Non-functional

• undo and redo should be O(size of the edit), not O(document).
• The set of edit kinds must be open: adding "replace" or "paste" must not touch the undo machinery.
• Memory for history is proportional to the total size of edits, not to snapshots of the document.

Numbers

• A 5 MB document with 10^5 edits in a session. Snapshotting the document per edit would be 500 GB; storing per-edit deltas is a few MB. That arithmetic is the whole case for the command pattern over mementos, and you should say it in the first five minutes.