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

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.

Input: ([['apply','insert','0','abcdef'],['apply','delete','2','4'],['get'],['undo'],['get'],['apply','replace','1','5','Z'],['get'],['undo'],['get']],)

Expected Output: ['abef', 'abcdef', 'aZf', 'abcdef']

Explanation: The delete removes cd. The replace changes bcde to Z, and undo restores the overwritten text.

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

Expected Output: ['']

Explanation: Undo with an empty history is a no-op.

Solution

def solution(commands):
    text = ''
    undo_stack = []
    outputs = []

    def apply_op(op):
        nonlocal text
        kind = op[0]
        if kind == 'insert':
            idx = op[1]
            s = op[2]
            text = text[:idx] + s + text[idx:]
            return ('delete', idx, idx + len(s))
        if kind == 'delete':
            start = op[1]
            end = op[2]
            removed = text[start:end]
            text = text[:start] + text[end:]
            return ('insert', start, removed)
        start = op[1]
        end = op[2]
        s = op[3]
        old = text[start:end]
        text = text[:start] + s + text[end:]
        return ('replace', start, start + len(s), old)

    def parse_op(fields):
        kind = fields[0]
        if kind == 'insert':
            return ('insert', int(fields[1]), fields[2])
        if kind == 'delete':
            return ('delete', int(fields[1]), int(fields[2]))
        return ('replace', int(fields[1]), int(fields[2]), fields[3])

    for cmd in commands:
        action = cmd[0]
        if action == 'apply':
            undo_stack.append(apply_op(parse_op(cmd[1:])))
        elif action == 'undo':
            if undo_stack:
                apply_op(undo_stack.pop())
        elif action == 'get':
            outputs.append(text)

    return outputs

Explanation

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

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.

Input: ([['begin'],['commit'],['undo'],['get']],)

Expected Output: ['']

Explanation: An empty batch creates no history entry, so undo has no effect.

Input: ([['apply','insert','0','abcdef'],['begin'],['apply','delete','1','5'],['apply','insert','1','XYZ'],['apply','replace','2','4','Q'],['commit'],['get'],['undo'],['get']],)

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

Explanation: Overlapping edits inside the batch are still undone correctly by replaying inverses in reverse.

Solution

def solution(commands):
    text = ''
    history = []
    active_batch = None
    outputs = []

    def apply_op(op):
        nonlocal text
        kind = op[0]
        if kind == 'insert':
            idx = op[1]
            s = op[2]
            text = text[:idx] + s + text[idx:]
            return ('delete', idx, idx + len(s))
        if kind == 'delete':
            start = op[1]
            end = op[2]
            removed = text[start:end]
            text = text[:start] + text[end:]
            return ('insert', start, removed)
        start = op[1]
        end = op[2]
        s = op[3]
        old = text[start:end]
        text = text[:start] + s + text[end:]
        return ('replace', start, start + len(s), old)

    def parse_op(fields):
        kind = fields[0]
        if kind == 'insert':
            return ('insert', int(fields[1]), fields[2])
        if kind == 'delete':
            return ('delete', int(fields[1]), int(fields[2]))
        return ('replace', int(fields[1]), int(fields[2]), fields[3])

    for cmd in commands:
        action = cmd[0]
        if action == 'begin':
            active_batch = []
        elif action == 'commit':
            if active_batch is not None and active_batch:
                history.append(active_batch)
            active_batch = None
        elif action == 'apply':
            inverse = apply_op(parse_op(cmd[1:]))
            if active_batch is None:
                history.append([inverse])
            else:
                active_batch.append(inverse)
        elif action == 'undo':
            if active_batch is None and history:
                unit = history.pop()
                for inverse in reversed(unit):
                    apply_op(inverse)
        elif action == 'get':
            outputs.append(text)

    return outputs

Explanation

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.

Input: ('abc', [['insert','1','X'],['delete','1','2']])

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

Explanation: The insert and delete cancel out, so the net patch is empty.

Input: ('abc', [['delete','0','3'],['insert','0','XYZ']])

Expected Output: ['XYZ', '0', '3', 'XYZ', 'abc', 'abc']

Explanation: The entire original document is replaced.

Input: ('', [['insert','0','hi']])

Expected Output: ['hi', '0', '0', 'hi', '', '']

Explanation: Insertion into an empty document is represented as replacing an empty range.

Solution

def solution(initial_text, operations):
    chars = list(initial_text)

    for op in operations:
        kind = op[0]
        if kind == 'insert':
            idx = int(op[1])
            chars[idx:idx] = list(op[2])
        elif kind == 'delete':
            start = int(op[1])
            end = int(op[2])
            del chars[start:end]
        else:
            start = int(op[1])
            end = int(op[2])
            chars[start:end] = list(op[3])

    final_text = ''.join(chars)
    n = len(initial_text)
    m = len(final_text)

    prefix = 0
    while prefix < n and prefix < m and initial_text[prefix] == final_text[prefix]:
        prefix += 1

    suffix = 0
    while suffix < n - prefix and suffix < m - prefix and initial_text[n - 1 - suffix] == final_text[m - 1 - suffix]:
        suffix += 1

    start = prefix
    end = n - suffix
    replacement = final_text[start:m - suffix]
    original_segment = initial_text[start:end]

    restored_text = final_text[:start] + original_segment + final_text[start + len(replacement):]
    return [final_text, str(start), str(end), replacement, original_segment, restored_text]

Explanation

The solution runs in two phases: **replay the batch**, then **compress the net change into one replace patch**. **Phase 1 — apply the batch.** `initial_text` is turned into a mutable list `chars`, and each operation is replayed in order: - `insert idx s` → splice `s` in at `idx` via `chars[idx:idx] = list(s)` - `delete start end` → `del chars[start:end]` - `replace start end s` → `chars[start:end] = list(s)` Joining gives `final_text`, the true result of the whole committed batch. **Phase 2 — compute the compact patch.** Instead of storing one inverse per edit, we diff only the *net* effect of `initial_text` vs `final_text`: - Grow `prefix` while leading characters match. - Grow `suffix` while trailing characters match, bounded by `suffix < n - prefix` and `suffix < m - prefix` so the suffix never overlaps the prefix on either string (avoids double-counting on short strings). The changed region in `initial_text` is `[start, end)` with `start = prefix`, `end = n - suffix`. The new content is `replacement = final_text[start : m - suffix]`. The original content there is `original_segment = initial_text[start:end]`. **Why it's correct.** Applying the patch — replace `initial_text[start:end]` with `replacement` — reconstructs `final_text`, because everything outside `[start, end)` is exactly the shared prefix/suffix. The inverse (`restored_text`) replaces the same region of `final_text` back with `original_segment`, recovering `initial_text`. The function returns `[final_text, str(start), str(end), replacement, original_segment, restored_text]`. Crucially, the stored patch size depends only on the changed region, not on the number of edits in the batch.

Time complexity: O(Q * L + N), where Q is the number of operations and L the max document length (each insert/delete/replace is a list splice costing up to O(L)); compression adds O(N) for the prefix/suffix scans, N = len(initial_text)+len(final_text).. Space complexity: O(L + D): O(L) for the char list and result strings of length up to the final document size L, plus O(D) for the stored changed region (replacement + original_segment), which is independent of the number of edits Q..

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.

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

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

Explanation: After undoing d, the new X edit clears redo, so redo cannot bring d back.

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

Expected Output: ['', 'A']

Explanation: Empty undo and redo are no-ops. An extra undo after history is empty does not clear redo.

Solution

def solution(commands):
    text = ''
    history = []
    redo_stack = []
    active_forward = None
    active_inverse = None
    outputs = []

    def apply_op(op):
        nonlocal text
        kind = op[0]
        if kind == 'insert':
            idx = op[1]
            s = op[2]
            text = text[:idx] + s + text[idx:]
            return ('delete', idx, idx + len(s))
        if kind == 'delete':
            start = op[1]
            end = op[2]
            removed = text[start:end]
            text = text[:start] + text[end:]
            return ('insert', start, removed)
        start = op[1]
        end = op[2]
        s = op[3]
        old = text[start:end]
        text = text[:start] + s + text[end:]
        return ('replace', start, start + len(s), old)

    def parse_op(fields):
        kind = fields[0]
        if kind == 'insert':
            return ('insert', int(fields[1]), fields[2])
        if kind == 'delete':
            return ('delete', int(fields[1]), int(fields[2]))
        return ('replace', int(fields[1]), int(fields[2]), fields[3])

    for cmd in commands:
        action = cmd[0]

        if action == 'begin':
            active_forward = []
            active_inverse = []

        elif action == 'commit':
            if active_forward is not None and active_forward:
                history.append((active_forward, active_inverse))
            active_forward = None
            active_inverse = None

        elif action == 'apply':
            redo_stack.clear()
            op = parse_op(cmd[1:])
            inverse = apply_op(op)
            if active_forward is None:
                history.append(([op], [inverse]))
            else:
                active_forward.append(op)
                active_inverse.append(inverse)

        elif action == 'undo':
            if active_forward is None and history:
                unit = history.pop()
                forward_ops, inverse_ops = unit
                for inverse in reversed(inverse_ops):
                    apply_op(inverse)
                redo_stack.append(unit)

        elif action == 'redo':
            if active_forward is None and redo_stack:
                unit = redo_stack.pop()
                forward_ops, inverse_ops = unit
                for op in forward_ops:
                    apply_op(op)
                history.append(unit)

        elif action == 'get':
            outputs.append(text)

    return outputs

Explanation

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.