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.

What difficulty level is this interview question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Airtable.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Airtable during technical interviews.

Implement spreadsheet undo/redo operations | Airtable Interview Question

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.

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.

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

Implement spreadsheet undo/redo operations

Quick Overview

Problem

Operations

Rules

Input/Output (one possible interface)

Example

Constraints

Comments (0)

Implement spreadsheet undo/redo operations

Quick Overview

Problem

Operations

Rules

Input/Output (one possible interface)

Example

Constraints

Comments (0)