Undo/redo для движка формул как в Excel
Undo/redo для движка формул как в Excel
Ответить самому
Сначала сформулируйте ответ как на собеседовании, затем откройте разбор и оцените себя.
Короткий ответ
Store immutable cell states in per-cell history with a current index. Undo moves the index back and restores that state; redo moves forward. Any new set/sum after undo must truncate future states before appending the new state.
Полный разбор
Represent a cell state explicitly: either a constant value or a formula reference list. For each cell, keep a history array of states and a current position. The active state of a cell is history[cell][position[cell]], with a missing state meaning an empty zero cell.
On set or sum, first validate the new operation. For sum, cycle detection must happen before mutating durable state. Then, if the cell is not at the end of its history, truncate all states after the current position. Append the new state and advance the position.
Undo(cell) checks whether position[cell] can move left. If so, decrement it and restore the previous state. Redo(cell) checks whether it can move right and increments it. Restoration should be centralized in one helper so constants, formulas and empty cells are handled consistently.
The main edge cases are formulas depending on cells whose own state later changes, cycles introduced by restored formulas, and whether undo/redo is per-cell or global-command based. In the interview prompt, per-cell history is enough, but in a product you should define these semantics up front.
Теория
Undo/redo is a versioned state problem: keep old immutable states and a cursor, and discard redo history when a new branch is created.
Типичные ошибки
- Pop history on undo, which makes redo impossible.
- Forget to truncate redo history after a new operation.
- Store only numeric values and lose formula dependencies.
- Mutate state before validating a formula cycle.
Как отвечать на собеседовании
- Define the state object before writing stack logic.
- Say whether history is per-cell or global-command based.