How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Figma.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Figma during technical interviews.

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.

Quick Answer: 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.

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.

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.

Quick Overview