A strong answer
Undo reverses edits in the opposite order to the one they were made in, so the history is a stack. I would represent each edit as a command object that knows how to apply itself and how to reverse itself, for example "insert 'abc' at position 10", whose reverse is "delete 3 characters at position 10".
Two stacks hold the history. Performing an edit applies the command and pushes it onto the undo stack. Undo pops the top command, reverses it and pushes it onto the redo stack. Redo pops from the redo stack, reapplies the command and pushes it back onto the undo stack. A brand-new edit clears the redo stack, because the redone commands assumed a document state that no longer exists after the new edit. All operations are O(1) apart from the work of applying the command itself.
Practical details: store small commands rather than full snapshots of the document, which would cost O(document size) per edit; cap the undo stack, for example at a few thousand steps, by dropping the oldest entries, which a ring buffer or a deque handles in O(1); and group fine-grained changes into one step, such as all keystrokes of a word or everything done in one operation, by pushing a composite command. Collaborative editors need more, such as operational transforms or CRDTs, because another user's edit can change what reversing my command means.
What the interviewer is listening for
- Two stacks and the exact behavior of each operation, including clearing redo on a new edit.
- Command objects with an inverse, instead of snapshots.
- Memory limits and grouping of steps.
Common mistakes
- Keeping a single list with an index but forgetting to truncate it on a new edit.
- Storing a full copy of the document for every keystroke.
- Treating undo as "go back in time" without saying what each step stores.