Katkat
Back

Design Extensible Undo and Redo for a Spreadsheet

AirtableSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

This problem tests your ability to design a robust Command pattern architecture capable of handling complex state transitions, such as data deletions and dependency-aware recalculations, in a spreadsheet environment.

Problem Statement

You are tasked with designing an undo/redo system for a spreadsheet application. Unlike a simple text editor, a spreadsheet involves dependencies (cell A depends on B), structural changes (deleting a row), and external side effects (API calls).

Design a system that tracks user operations such that they can be undone and redone reliably. Your system must handle:

  1. Data Mutations: Updating the value of a single cell.
  2. Structural Changes: Deleting a row (which impacts existing formulas).
  3. Transactional Integrity: Recalculating affected cells when an undo/redo action is performed.
  4. Non-Undoable Actions: Handling operations that cannot be reverted (e.g., publishing a sheet to the web).

Define the necessary interfaces or classes for a Command pattern approach. Explain how you would store the command history and how you manage the execution flow.

Requirements

  • Provide a Command interface with execute() and undo() methods.
  • Describe how you store the state before and after an operation to ensure accurate rollbacks.
  • Explain the strategy for handling dependencies when an undo operation triggers a cascade of formula updates.

Example Scenario

  • User deletes Row 5.
  • DeleteRowCommand stores the Row 5 data (for restoration) and the indices of dependent formulas.
  • When undo() is called, the system restores Row 5 and re-registers the previously broken dependencies.

Constraints

  • Assume the spreadsheet can contain up to 100,000 cells.
  • The system must prevent memory leaks in the history buffer.

Hints

Hint 1

Consider defining a 'Memento' or a state-snapshot object that each command carries to facilitate precise restoration.

Hint 2

For structural changes like row deletion, the Command needs to store a 'delta' or the complete row object to recreate it accurately.

Hint 3

Use a registry of listeners or a reactive dependency graph to ensure that undoing a cell value change automatically triggers a recalculation of dependent cells.

Follow-up questions

  • How would you handle 'batch' commands, where a single user action (like dragging a fill handle) changes 50 cells at once?
  • If an operation is 'non-undoable', how should the UI inform the user and how should the command history be handled (e.g., clearing the stack)?
  • How would you persist this command history to a backend server to support collaborative editing between multiple users?