Implement spreadsheet undo/redo operations

Q: Implement spreadsheet undo/redo operations

This question evaluates a candidate's ability to design stateful data structures and manage operation history, focusing on correctness of undo/redo semantics, handling edge cases, and analyzing time and space complexity.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Problem

Design a data structure that simulates Undo/Redo for a simplified spreadsheet editor.

A user performs a sequence of operations on cells. Each operation changes the value of a single cell.

Operations

SET cell value : set cell (e.g., "A1") to value (string or number).
UNDO k : undo the last k successful SET operations (or as many as possible).
REDO k : redo the last k operations that were undone (or as many as possible).

Rules

UNDO and REDO affect only SET operations.
After an UNDO , if a new SET is executed, the redo history is cleared.
If UNDO k requests more steps than exist, undo all available steps.
If REDO k requests more steps than exist, redo all available steps.

Input/Output (one possible interface)

Given a list of commands, return the final mapping of cell -> value.

Example

Commands:

SET A1 10
SET A1 20
SET B2 5
UNDO 2 (undo: B2=5 , then A1=20 )
REDO 1 (redo: A1=20 )
SET C1 7 (clears redo stack)

Final state: A1=20, C1=7 (and B2 is empty).

Constraints

Up to N commands (e.g., 10^5).
Aim for efficient per-command time and memory.

Discuss the data structures and complexity; implement the core logic.