Design document layer with undo/redo

Q: Design document layer with undo/redo

This question evaluates a candidate's understanding of reversible state mutation and undo/redo semantics, covering batching, inverse operation representation, operation compression, failure handling, and choice of data structures for edit history.

Q: 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.

Q: What difficulty level is this coding question?

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

Q: What role is this question designed for?

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

Question

Design a document layer that supports applying edits and undo/redo. Implement apply(op) to mutate the document, undo() to revert the most recent committed unit of work, and redo() to reapply undone work. Add batching: beginBatch(), multiple apply(op) calls, then commitBatch() so the batch undoes in one step. Propose how to optimize batch undo (time and space), including how to store inverse operations, compress consecutive operations, and handle partial failures. Explain redo semantics after an undo and after new edits are applied. Discuss data structures, edge cases (empty stacks, nested/overlapping batches), and time/space complexity.

PracHub · Accepted Answer

def solution(commands): document = '' snapshots = [] undo_stack = [] redo_stack = [] batch_open = False batch_ops = [] batch_inverses = [] def execute(op): nonlocal document kind, index, text = op if kind == 'insert': document = document[:index] + text + document[index:] else: # delete document = document[:index] + document[index + len(text):] def build_edit(kind, index, value): if kind == 'insert': if not isinstance(index, int) or index < 0 or index > len(document): return None if not isinstance(value, str): return None text = value return ('insert', index, text), ('delete', index, text) if kind == 'delete': if not isinstance(index, int) or not isinstance(value, int): return None length = value if index < 0 or length < 0 or index + length > len(document): return None deleted = document[index:index + length] return ('delete', index, deleted), ('insert', index, deleted) return None def abort_batch(): nonlocal batch_open, batch_ops, batch_inverses for inverse in reversed(batch_inverses): execute(inverse) batch_open = False batch_ops = [] batch_inverses = [] for command in commands: if not command: continue action = command[0] if action == 'apply': if len(command) != 4: if batch_open: abort_batch() continue built = build_edit(command[1], command[2], command[3]) if built is None: if batch_open: abort_batch() continue forward, inverse = built execute(forward) if batch_open: batch_ops.append(forward) batch_inverses.append(inverse) else: undo_stack.append(([forward], [inverse])) redo_stack.clear() elif action == 'beginBatch': if not batch_open: batch_open = True batch_ops = [] batch_inverses = [] elif action == 'commitBatch': if batch_open: if batch_ops: undo_stack.append((batch_ops[:], batch_inverses[:])) redo_stack.clear() batch_open = False batch_ops = [] batch_inverses = [] elif action == 'undo': if batch_open: continue if undo_stack: ops, inverses = undo_stack.pop() for inverse in reversed(inverses): execute(inverse) redo_stack.append((ops, inverses)) elif action == 'redo': if batch_open: continue if redo_stack: ops, inverses = redo_stack.pop() for op in ops: execute(op) undo_stack.append((ops, inverses)) elif action == 'get': snapshots.append(document) return document, snapshots

Quick Overview

Constraints

Examples

Solution

Hints