Undo/Redo And Command History

What's being tested

These problems test command history design: representing edits as reversible operations, maintaining undo/redo stacks, and defining exact semantics for new edits after undo. You must reason about batching, overlapping ranges, cursor/bookkeeping updates, failure handling, and performance as document size and history length grow.

Patterns & templates

• Model each edit as a command with apply() and undo(); store deleted text or an inverse operation rather than full document snapshots.

• Maintain undo and redo stacks: successful new edits push undo and clear redo; undo transfers one command to redo, while redo reverses that transfer.

• Use transactional batching to group keystrokes or multi-range changes into one composite command with ordered forward and inverse operations.

• For range edits, record coordinates and original content before mutation; process overlapping ranges consistently, often right-to-left to preserve offsets.

• Prefer a gap buffer, piece table, or rope for large documents; snapshots are simple but cost O(document size) per history entry.

• Compress adjacent compatible inserts/deletes, but preserve command boundaries required by explicit transactions, selection changes, or collaborative operations.

• Make commands atomic: if applying or reversing a batch fails, restore prior state; target O(k log n) for k edited ranges with a rope or interval structure.

Common pitfalls

Pitfall: Clearing redo after every internal operation in a batch, rather than after the completed user-level transaction.

Pitfall: Storing only positions when edits shift offsets; preserve deleted content and transform later ranges or apply them in descending order.

Pitfall: Treating undo as a raw inverse without updating selections, cursors, metadata, and invariants consistently.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.