Undo and Redo Coding Interview: History Models, Branching, and Memory Limits

For an undo-and-redo coding interview, define what one history step means before choosing two stacks. The essential contract is that undo restores the previous committed state, redo reapplies the most recently undone transition, and a new edit after undo usually discards the abandoned future. Then state how much history you retain and which effects are outside the local model.

The implementation and traces below are original exercises. Redux documentation supplies a reference model for past, present, and future; it is not evidence of a specific employer's interview format.

Which questions change the implementation most?

Ask whether history stores a whole document, one component, or a sequence of domain operations. Clarify whether selection and cursor position belong to a step, whether several keystrokes count as one action, and whether failed operations create history. Finally, ask whether the task is single-user and whether history survives restart.

For our exercise, the state is an immutable string. Each successful change is one committed step. Replacing a string with the same value is a no-op and preserves redo history. Empty undo and redo return false. A new changed value clears redo. A positive limit bounds the number of transitions retained along the current history path.

These choices are deliberately small enough to implement and test. A collaborative editor needs additional rules about whose changes are undone. A shopping cart may need to restore the quantity actually removed rather than blindly repeat the requested quantity. Do not quietly import those semantics into a text snapshot exercise.

The Redux guide presents history as past states, one present state, and future states. That shape is a useful starting point independent of whether you use Redux itself. Redux undo history guide

How does the branching trace work?

Start with an empty document, commit A, then AB, and undo once. The current document is A; AB is available for redo. Now commit AX. Under the chosen linear-history contract, AB is no longer reachable through redo.

Action	Past, oldest first	Present	Future, next redo first
Start	Empty	Empty string	Empty
Commit A	Empty string	A	Empty
Commit AB	Empty string, A	AB	Empty
Undo	Empty string	A	AB
Commit AX	Empty string, A	AX	Empty

“Branching” has two possible meanings. This exercise replaces the future when a new branch is created. A version browser that preserves every branch needs a history tree and a way to choose which child to redo. That is a different product and data structure, not a minor extension to the same redo button.

Test the no-op policy at the branch point. After undoing to A, committing A again should not clear AB in our contract. If every setter call clears future history, an innocuous state synchronization can destroy the user's redo path without changing the document.

Also test a rejected edit. Validation should finish before modifying history. An out-of-range deletion should not pop undo, clear redo, or partially change the document. The operation is either one committed transition or no transition.

Can you implement a bounded snapshot model clearly?

Here is an original Python implementation for string snapshots. It uses deques so that evicting the oldest retained state does not require shifting an entire list. The present value remains separate from the two navigation collections.

from collections import deque

class History:
    def __init__(self, initial="", limit=100):
        if not isinstance(initial, str):
            raise TypeError("state must be a string")
        if type(limit) is not int or limit < 1:
            raise ValueError("limit must be a positive integer")
        self.present = initial
        self.limit = limit
        self.past = deque()
        self.future = deque()

    def commit(self, value):
        if not isinstance(value, str):
            raise TypeError("state must be a string")
        if value == self.present:
            return False
        self.past.append(self.present)
        if len(self.past) > self.limit:
            self.past.popleft()
        self.present = value
        self.future.clear()
        return True

    def undo(self):
        if not self.past:
            return False
        self.future.appendleft(self.present)
        self.present = self.past.pop()
        return True

    def redo(self):
        if not self.future:
            return False
        self.past.append(self.present)
        self.present = self.future.popleft()
        return True

The first future element is always the next redo destination. After multiple undos, appendleft places the most recently left state at the front. Redo removes that front element and pushes the former present onto past. Mixing the two ends is a common bug that only appears after more than one undo.

Python documents deque operations at both ends as approximately constant time. That supports the history-container operations here, but it does not make every edit constant time: producing a new string, comparing strings, and releasing abandoned future references can add work. Python deque documentation

The public attributes keep the exercise easy to inspect. A production interface should prevent callers from mutating the deques or replacing present behind the history model. Otherwise, callers can violate the invariants without going through commit.

What invariant makes the memory limit understandable?

Starting from a valid instance and using only its methods, len(past) + len(future) never exceeds limit. Undo and redo transfer one snapshot reference between the two sides while moving present. A changed commit discards future and caps past. The model therefore retains at most limit + 1 snapshot references, including present.

That is a count bound, not a byte bound. One snapshot can contain a much larger document than another. If the interviewer asks for a strict memory budget, add an explicit cost model and state which objects it includes: text payloads, command metadata, indices, and shared nodes may all matter.

For the example, define a hypothetical budget over encoded text bytes and track that quantity. Do not label it exact Python heap usage. Runtime object overhead and shared references make a simple string-length sum an estimate of a particular payload measure, not a heap profiler.

When evicting snapshots, remove the oldest undoable state first and explain what the user loses: they can no longer navigate before the retained boundary. If storing deltas instead, dropping an old dependency may make later replay impossible unless a base checkpoint is retained. Memory reclamation must preserve a usable history, not just reduce a counter.

When are commands or patches better than snapshots?

Snapshots are easy to reason about when state is small and immutable. They make restoration straightforward and provide a useful reference implementation. Their cost becomes unattractive when every keystroke retains an otherwise nearly identical large document.

A command can store the change plus enough information to reverse it. For deletion, that means the removed text and its position, not only the requested length. For a capped cart removal, record the quantity actually removed. Replaying the original request under a different state is not necessarily an inverse.

Patches can describe changed fields without storing the whole document. Immer provides patch and inverse-patch facilities for its supported state model. If you choose a library, check its treatment of paths, non-JSON values, and changes to the surrounding structure. Immer patches documentation

A hybrid stores periodic checkpoints plus changes between them. That can trade restoration time for retained memory. Explain the longest replay path and what happens when the oldest checkpoint is removed. “Use deltas” is incomplete without a reconstruction strategy.

For this interview, begin with the simplest representation that meets the stated size constraint. Keep its tests as a reference when implementing a more compact version. An optimized command log that cannot reproduce the same visible states is not an improvement.

How should grouped edits become one undoable action?

Typing a word one character at a time and dragging an object through hundreds of pointer events usually produce too many history entries. A group should retain the state before the first included change and the state after the last, or an equivalent reversible transaction.

Define group boundaries using both intent and time. A pause may end typing, but moving the cursor, pasting text, changing fields, or starting a different command can also end it. A time window alone can merge two unrelated actions that happen quickly.

For the string exercise, add a staging value for an explicit transaction. Apply intermediate edits to staging, then commit once. Canceling discards staging without touching past or future. Nested groups require a policy: merge into the outer transaction, maintain a stack, or reject nesting. State which policy you implement.

If the group returns to the original value, our no-op contract says it creates no history entry. Check whether selection changes should make it a meaningful edit anyway. That decision depends on whether selection is included in state, which is why the opening clarification matters.

For text entered through an input method editor, composition events help distinguish an in-progress composition from committed input. Do not blindly turn every intermediate input event into a separate undo record. MDN compositionend event

What cannot be undone by restoring local state?

Restoring an old cart snapshot does not reverse a charge already accepted by a payment service. Restoring editor text does not retract an email already sent. Keep reversible local presentation changes separate from external side effects and their domain-specific compensating actions.

Asynchronous work creates another boundary. If a response started before undo completes afterward, it can overwrite the restored state. Associate work with a document revision or operation identity and decide whether a stale result is ignored, rebased, or presented for review.

In collaboration, the “previous global snapshot” may include another user's valid changes. Replacing it wholesale can erase their work. Local undo usually needs to express the inverse of the current user's operation in a changed context. That requires a collaboration model, not simply sharing the two deques between clients.

Make the scope explicit in the final answer: this implementation is a single-user in-memory history for immutable strings. Persistence, concurrent editing, and external compensation are follow-up designs. Clear boundaries demonstrate judgment without pretending the small implementation solves every editor problem.

Which tests expose the misleadingly correct solution?

Use the branch trace as a deterministic baseline. Then test multiple undo and redo calls, empty boundaries, identical commits, rejected types, and a capacity of one. Confirm that redo cannot re-enter a discarded branch after a changed commit.

Add an inverse property: after one successful undo, a redo with no intervening edit restores the prior present and navigation state. A second property checks the retained-count invariant after every randomly generated operation. These properties find failures that a single “A, AB, undo” demonstration misses.

For memory eviction, commit three distinct values with a limit of two. Undo twice and verify the oldest reachable value is the retained boundary, not the initial empty state. A third undo should return false without changing anything.

When optimizing to commands, run the same generated operation sequence against both models. Compare visible states and the availability of undo and redo after every step. Keep the reference model independent enough that it does not repeat the exact indexing mistake of the implementation under test.

Sources and Further Reading

• Redux: Implementing undo history
• Python: deque objects
• Immer: Patches and inverse patches
• MDN: compositionend event