Design document editor with undo/redo and batching

Quick Overview

The question evaluates design of mutable text-editing layers and undo/redo semantics, including transactional batching, performance optimization for very large operation histories, and handling of overlapping range edits and cursor bookkeeping within the Coding & Algorithms domain.

Company: Figma

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Design a document-editing layer that supports applying edits and undo. Implement an API with apply(Operation op), undo(), and getText(). Then add transactional batching: beginBatch(), apply(...), commitBatch(), where undo() reverts an entire committed batch atomically. Explain how to optimize batch undo for very large batches (e.g., millions of small operations) in time and memory. Finally, implement redo() that works with both single edits and committed batches, and clarify how redo is invalidated after new edits. Describe data structures, complexity, and edge cases such as overlapping range edits and cursor bookkeeping.

Overview: The question evaluates design of mutable text-editing layers and undo/redo semantics, including transactional batching, performance optimization for very large operation histories, and handling of overlapping range edits and cursor bookkeeping within the Coding & Algorithms domain.

Part 1: Basic Document Editing with Undo

Implement a small document-editing simulator. The document starts as an empty string. You must support applying one edit operation, undoing the most recent applied operation, and reading the current text. Ranges are half-open: start is inclusive and end is exclusive. All ranges in apply commands are guaranteed to be valid for the current document state. If undo is called when there is no history, it does nothing.

Constraints

0 <= len(commands) <= 10000
0 <= document length after any command <= 100000
For delete and replace, 0 <= start <= end <= current document length
For insert, 0 <= index <= current document length
undo on an empty history is a no-op

Examples

Input: ([] ,)

Expected Output: []

Explanation: No commands produce no output.

Input: ([['apply','insert','0','hello'],['get'],['apply','insert','5',' world'],['get'],['undo'],['get'],['undo'],['get'],['undo'],['get']],)

Expected Output: ['hello', 'hello world', 'hello', '', '']

Explanation: Two inserts are undone in reverse order. The final extra undo has no effect.

Hints

For every applied operation, store the inverse operation needed to undo it.
For a replace, the inverse must remember the exact text that was overwritten.

Part 2: Transactional Batches with Atomic Undo

Extend the document editor with transactional batching. The document starts empty. Edits outside a batch are normal undoable units. Edits between begin and commit form one committed batch, and undo must revert the entire committed batch atomically. Empty batches are allowed but create no undo-history entry. Command sequences are well-formed: there are no nested batches, and undo is not called while a batch is open.

Constraints

0 <= len(commands) <= 10000
0 <= document length after any command <= 100000
Batch nesting is not used
For every edit, the provided range or index is valid for the current document state
undo on an empty history is a no-op

Examples

Input: ([['apply','insert','0','abcdef'],['begin'],['apply','replace','1','4','X'],['apply','insert','2','Y'],['commit'],['get'],['undo'],['get'],['undo'],['get']],)

Expected Output: ['aXYef', 'abcdef', '']

Explanation: The committed batch changes abcdef to aXYef. One undo restores the whole batch, and the next undo removes the initial insert.

Input: ([['apply','insert','0','A'],['begin'],['apply','insert','1','B'],['apply','insert','2','C'],['commit'],['get'],['undo'],['get'],['apply','insert','1','D'],['get'],['undo'],['get']],)

Expected Output: ['ABC', 'A', 'AD', 'A']

Explanation: The BC inserts are undone together, while the later D insert is a separate undoable unit.

Approach

The editor keeps the live document in text and an undo stack history, where each entry is a list of inverse operations — one list per undoable unit. Applying & inverting edits. apply_op mutates text and, crucially, returns the inverse edit that would undo it: - insert(idx, s) → inverse delete(idx, idx+len(s)) - delete(start, end) → inverse insert(start, removed) (it captures the removed substring first) - replace(start, end, s) → inverse replace(start, start+len(s), old) (captures the old substring, and adjusts the end index to the new length so re-running the inverse restores the original) Because each inverse is computed against the document state at apply time and stored, undo is just replaying these inverses. Batching. A normal edit pushes a single-element list [inverse] onto history. begin opens active_batch = []; while open, every edit's inverse is appended to that one list instead of being pushed individually. commit pushes the whole batch as one history entry — so a later undo reverts all of it atomically. Empty batches push nothing, matching the "no undo-history entry" rule. Undo. undo pops the top unit and applies its inverses in reverse order (reversed(unit)). Reversal is essential: edits within a unit were applied left-to-right and depend on prior index shifts, so they must be unwound last-to-first. Undo is ignored while a batch is open or when history is empty. get snapshots the current text into outputs. Correctness follows from each stored inverse exactly canceling its forward edit, and reverse-order replay restoring intermediate states.

Time complexity: O(C * L) worst case, where C is the number of commands and L is the maximum document length. Each insert/delete/replace/undo rebuilds the string via slicing, costing up to O(L); undoing a committed batch costs the total size of its inverse edits.

Space complexity: O(L + H), where L is the document length and H is the total size of inverse-operation data (indices plus captured old/removed substrings) retained across all history entries.

Hints

A history entry can be either one inverse operation or a list of inverse operations.
To undo a batch, apply its inverse operations in reverse order.

Part 3: Compress a Large Batch into One Undo Patch

For very large committed batches, storing one inverse operation per tiny edit can be too expensive. In this problem, you are given the initial document and all edits from one committed batch. Apply the batch, then compute one compact replace patch that represents the net effect of the entire batch. The patch is based on the longest common prefix and suffix between the initial and final documents. Applying the patch to the initial document must produce the final document, and applying its inverse to the final document must restore the initial document.

Constraints

0 <= len(initial_text) <= 100000
0 <= len(operations) <= 10000
0 <= document length after any operation <= 200000
For every edit, the provided range or index is valid for the current document state
The compressed undo metadata should depend on the size of the net changed region, not directly on the number of operations

Examples

Input: ('abcdef', [['replace','1','4','X'],['insert','2','Y']])

Expected Output: ['aXYef', '1', '4', 'XY', 'bcd', 'abcdef']

Explanation: The net effect is replacing bcd with XY.

Input: ('hello', [])

Expected Output: ['hello', '5', '5', '', '', 'hello']

Explanation: No edits produce an empty patch at the end of the document.

Hints

After computing the final text, skip the equal prefix and equal suffix shared by the initial and final strings.
The inverse of one replace patch only needs the original middle segment and the length of the replacement.

Part 4: Undo and Redo for Single Edits and Batches

Extend the batched editor with redo. The document starts empty. Edits outside a batch are individual history units; edits inside a committed batch are one atomic history unit. undo moves the most recent history unit to the redo stack and reverts it. redo reapplies the most recently undone unit. Any new apply command from the user invalidates all redo history. Command sequences are well-formed: no nested batches, and undo or redo is not called while a batch is open.

Constraints

0 <= len(commands) <= 10000
0 <= document length after any command <= 100000
For every edit, the provided range or index is valid for the current document state
undo and redo on empty stacks are no-ops
Any user apply clears the redo stack, including an apply inside a new batch

Examples

Input: ([['apply','insert','0','abc'],['get'],['undo'],['get'],['redo'],['get'],['redo'],['get']],)

Expected Output: ['abc', '', 'abc', 'abc']

Explanation: The second redo has no effect because there is no remaining redo history.

Input: ([['apply','insert','0','abcdef'],['begin'],['apply','replace','1','4','X'],['apply','insert','2','Y'],['commit'],['get'],['undo'],['get'],['redo'],['get'],['undo'],['get']],)

Expected Output: ['aXYef', 'abcdef', 'aXYef', 'abcdef']

Explanation: The committed batch is undone and redone atomically.

Approach

The editor keeps a single mutable text string plus two stacks: history (applied units available to undo) and redo_stack (undone units available to redo). A history unit is a pair (forward_ops, inverse_ops). Inverse-based undo. apply_op both mutates text and returns the inverse operation that exactly reverses it: - insert(idx, s) → inverse delete(idx, idx+len(s)) - delete(start, end) → inverse insert(start, removed) (captures the removed slice first) - replace(start, end, s) → inverse replace(start, start+len(s), old) (captures the old slice and adjusts the end to the new length). Batching. begin opens an active_forward/active_inverse accumulator. While open, each apply mutates text immediately but appends its op/inverse to these lists instead of history. commit pushes the whole batch as one atomic unit (and skips empty batches). Outside a batch, each apply becomes its own one-op unit. Redo invalidation. Every apply (single or inside a batch) calls redo_stack.clear() first, so any new edit discards redo history — matching the spec. Undo/redo. undo pops the latest history unit and replays its inverses in reversed order (so multi-op batches unwind last-to-first), then pushes the unit to redo_stack. redo pops from redo_stack and replays forward_ops in original order, pushing the unit back onto history. Both are no-ops on empty stacks and are guarded by active_forward is None (never run mid-batch). get snapshots the current text. Correctness holds because each forward op has a precise inverse and units are unwound/reapplied in the proper order.

Time complexity: O(C * L) worst case, where C is the number of commands and L is the maximum document length. Each insert/delete/replace rebuilds the string via slicing (O(L)); undo/redo of a batch costs the sum of its operation sizes, still bounded by O(L) per op.

Space complexity: O(L + H), where L is the current document length and H is the total size of forward/inverse operations retained across the history and redo stacks (each stored op holds index data plus any captured/removed text slice).

Hints

Store each history unit with both its forward operations and inverse operations.
Undo applies inverse operations in reverse order; redo applies forward operations in original order.

Community answers

Answer by andrea.santa

Should batches be nested?

Approach

The solution simulates a text document and supports undo by pushing the inverse of every applied edit onto a stack — so undoing is just applying that inverse.

State: text holds the current document; undo_stack holds inverse operations; outputs collects answers for get.

apply_op mutates text and returns the operation that reverses it:

insert(idx, s): splice s in at idx. Inverse is delete(idx, idx+len(s)) — remove exactly what we inserted.
delete(start, end): capture removed = text[start:end], then cut it out. Inverse is insert(start, removed) — put the captured slice back.
replace(start, end, s): capture old = text[start:end], swap in s. Inverse is replace(start, start+len(s), old) — the new range to overwrite is [start, start+len(s)) (where s now lives), restoring old.

Dispatch loop: parse_op turns string fields into a typed tuple (converting index fields with int). For apply, it applies the op and pushes the returned inverse. For undo, if the stack is non-empty it pops and applies the inverse (a no-op on empty history — covered by tests 2 and 4). For get, it snapshots the current text.

Why it's correct: because each inverse precisely cancels its forward op and ranges are half-open and valid, replaying inverses in LIFO order returns the document to each prior state — verified across insert/delete/replace and repeated undos.

The clever bit is that replace's inverse is again a replace, so all three op types are reversible with the same three-way machinery and no special undo logic.

Time complexity:

O(C * L)

Space complexity:

O(L + H)