Quick Overview

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.

Design document layer with undo/redo

Company: Figma

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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.

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

Design a **document layer** for a text document that starts as the empty string `""`. Given a sequence of commands, apply edits to the document while supporting **undo**, **redo**, and **batching**, then return the final document together with a snapshot taken at each `get` command. Implement the function: ```python def solution(commands): ... ``` - `commands` is a list of command tuples (any of the shapes below). - Return a **tuple** `(final_document, snapshots)`, where: - `final_document` is the document string after all commands are processed. - `snapshots` is a list holding the document string at the moment of each `get` command, in the order the `get` commands occur. ## Commands **Edit commands** (the third element is an `index`; the fourth depends on the operation): - `("apply", "insert", index, text)` — insert the string `text` so that it begins at position `index`. - `("apply", "delete", index, length)` — delete `length` characters starting at `index` (here the fourth element is an integer count, **not** a string). **Batch commands:** - `("beginBatch",)` — open a batch. Apply commands issued after this still mutate the document **immediately**, but they are not added to undo history until the batch is committed. - `("commitBatch",)` — commit the currently open batch as **one** undoable unit. Committing an **empty** batch records nothing. **History commands:** - `("undo",)` — undo the most recent committed unit of work. - `("redo",)` — redo the most recently undone committed unit of work. **Read command:** - `("get",)` — append the current document string to `snapshots`. ## Units of work - **Outside a batch**, each successful apply command is its own committed unit and is immediately undoable. - **Inside a batch**, every successful apply command in the batch is grouped together; when `commitBatch` runs, the whole group becomes a single committed unit. - Only **committed** units can be undone or redone. ## Validity of an apply command An apply command is **valid** only against the document's current length: - **insert** at `index` requires `0 <= index <= len(document)`. - **delete** of `length` characters at `index` requires `index >= 0`, `length >= 0`, and `index + length <= len(document)`. Any apply command that does not meet these conditions is **invalid**. ## Rules and edge cases - **Invalid apply outside a batch:** ignore it. The document and all history are unchanged. - **Invalid apply inside a batch:** roll the document back to the state it had at the matching `beginBatch`, discard the open batch entirely, and leave the undo/redo history unchanged. (The batch is aborted, not committed.) - **No nested batches:** if `beginBatch` is called while a batch is already open, ignore it. - **Stray `commitBatch`:** if `commitBatch` is called with no batch open, ignore it. - **`undo` / `redo` while a batch is open:** ignore them. - **After undo,** a subsequent `redo` reapplies the most recently undone committed unit. - **Redo stack clearing:** committing a **new** unit of work (a successful standalone apply, or a non‑empty `commitBatch`) clears the redo stack. An invalid standalone apply and an aborted batch do **not** clear the redo stack, because no new history unit was committed. ## Implementation note For efficiency, prefer storing **inverse operations** rather than whole‑document snapshots, so memory scales with the edited text instead of the document size. Consecutive compatible edits within a single batch may optionally be compressed into one stored operation. This is a performance guideline only and does not change the observable behavior above. ## Constraints - `0 <= len(commands) <= 5000` - The sum of the lengths of all inserted strings is at most `100000`. - Commands are well‑formed tuples of the supported shapes; indexes may be invalid and must be handled per the rules above. ## Example For `[("apply","insert",0,"abc"), ("apply","insert",3,"def"), ("get",), ("undo",), ("get",), ("redo",), ("get",)]` the result is `("abcdef", ["abcdef", "abc", "abcdef"])`.

Constraints

  • 0 <= len(commands) <= 5000
  • The sum of lengths of all inserted strings is at most 100000
  • Commands are well-formed tuples of the supported shapes; indexes may be invalid and must be handled according to the rules

Examples

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

Expected Output: ('abcdef', ['abcdef', 'abc', 'abcdef'])

Explanation: The two inserts are separate committed units. Undo removes only the second insert, and redo restores it.

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

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

Explanation: Both inserts are committed together as one batch. Undo removes the whole batch, and redo reapplies it.

Hints

  1. Use two stacks: one for committed units that can be undone, and one for units that can be redone.
  2. Instead of storing whole document snapshots, store inverse primitive operations. To undo a batch, replay its inverse operations in reverse order.

Loading coding console...

Show the approach

Approach

The solution models the document as a plain string and tracks history with inverse operations instead of full snapshots, which keeps memory proportional to the edited text rather than the document size.

Core state

  • document — the live text.
  • undo_stack / redo_stack — each entry is a committed unit: a pair (ops, inverses) (lists of forward ops and their undo ops).
  • batch_open, batch_ops, batch_inverses — the in-progress batch.

Per-edit machinery

  • build_edit(kind, index, value) validates the edit against the current document length and returns a (forward, inverse) pair, or None if the index/range is bad. An insert's inverse is a delete at the same spot; a delete's inverse re-inserts the exact characters it captured (document[index:index+length]), which is what makes undo exact.
  • execute(op) mutates document via slicing.

Command handling

  • apply outside a batch: execute, push ([forward],[inverse]) onto undo_stack, and clear redo_stack (a new commit invalidates redo).
  • apply inside a batch: execute and append to the batch buffers — not yet undoable. An invalid edit calls abort_batch(), which replays batch_inverses in reverse to restore the begin-batch state and discards the batch, leaving history untouched (so redo is NOT cleared).
  • commitBatch pushes the whole batch as one unit (empty batch → nothing) and clears redo.
  • undo/redo are ignored while a batch is open; otherwise they move a unit between stacks, replaying inverses in reverse (undo) or forwards in order (redo).

Correctness follows because every committed unit carries an exact inverse, so undo/redo are precise reversals, and redo is cleared exactly when new history is committed.

Time complexity:
O(E * L) worst-case, where E is the number of edit ops actually executed (including undo/redo/abort replay) and L is the document length, since each `execute` rebuilds the string via slicing.
Space complexity:
O(H), where H is the total text captured across undo history, redo history, and the open batch (inverses store deleted/inserted substrings, not whole-document snapshots).