Document Layer Data Models

What's being tested

These problems test reversible state mutation over a mutable document, with correct undo/redo semantics for individual edits and transactional batches. You must choose an operation representation, generate reliable inverses, handle overlapping ranges and cursor positions, and keep history operations efficient rather than copying the entire document.

Patterns & templates

• Represent edits as typed operations (`insert`, `delete`, `replace`) with position, payload, and metadata; define `apply` and `invert` as core primitives.
• Maintain two stacks: undo and redo; a new edit clears redo, undo moves the latest command to redo, and redo moves it back.
• Batch edits transactionally by grouping child operations; undo a batch in reverse order and apply inverses in forward document coordinates.
• Prefer operation logs or command objects over full snapshots; snapshots cost O(document size) per edit, while inverses cost proportional to changed content.
• For overlapping edits, transform positions through prior operations or use a piece table/rope; never assume stale offsets remain valid.
• Make batch application atomic: validate all operations first, apply them, and roll back or leave state unchanged on failure.
• Cap history by bytes or operation count; compress adjacent inserts/deletes when safe, while preserving cursor and selection semantics.

Common pitfalls

Pitfall: Storing only deleted ranges without their original text makes deletion irreversible; inverse data must preserve every replaced or removed character.

Pitfall: Undoing a batch in insertion order corrupts positions; inverse operations must run in reverse order, with coordinate transformations when edits overlap.

Pitfall: Treating redo as an independent history after a new edit permits impossible timelines; any divergent mutation must invalidate the redo stack.

Practice these

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