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

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

Input: ([('apply', 'insert', 0, 'abc'), ('beginBatch',), ('apply', 'insert', 3, 'd'), ('apply', 'delete', 10, 1), ('get',), ('undo',), ('get',)],)

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

Explanation: The invalid delete aborts the batch and rolls back the pending insert of 'd'. The earlier committed insert of 'abc' can still be undone.

Input: ([('apply', 'insert', 0, 'x'), ('beginBatch',), ('undo',), ('apply', 'insert', 1, 'y'), ('beginBatch',), ('redo',), ('get',), ('commitBatch',), ('undo',), ('get',), ('redo',), ('get',)],)

Expected Output: ('xy', ['xy', 'x', 'xy'])

Explanation: Undo and redo are ignored while a batch is open, and a nested beginBatch is ignored. After commit, the batch behaves as one undoable unit.

Input: ([('apply', 'insert', 0, 'ab'), ('apply', 'insert', 2, 'c'), ('undo',), ('apply', 'delete', 5, 1), ('redo',), ('get',), ('undo',), ('apply', 'insert', 2, 'd'), ('redo',), ('get',)],)

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

Explanation: The invalid standalone delete does not clear redo, so 'c' can still be redone. After undoing again, the new committed insert of 'd' clears the redo stack.

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

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

Explanation: The batch deletes the space and then 'world'. Undo restores both deletions together, and redo removes them again.

Input: ([('commitBatch',), ('beginBatch',), ('commitBatch',), ('undo',), ('get',)],)

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

Explanation: commitBatch with no open batch is ignored, and committing an empty batch adds no history. Undo then has nothing to do.

Input: ([],)

Expected Output: ('', [])

Explanation: With no commands, the document stays empty and no snapshots are recorded.

Solution

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

Explanation

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)..

Hints

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