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 undo/redo with two stacks | Airtable Interview Question

Q: Implement undo/redo with two stacks

This question evaluates a candidate's ability to design and implement efficient mutable state management and history tracking using data structures (such as stacks), along with string manipulation and algorithmic complexity reasoning.

Problem: Undo/Redo for a Simple Text Editor

Design a data structure that simulates a very small text editor with undo and redo.

You are given a sequence of commands; after each command, output the current text.

Commands

TYPE s : append string s to the end of the current text.
DELETE k : delete the last k characters (if k exceeds current length, delete everything).
UNDO : undo the most recent mutating command ( TYPE or DELETE ) that has not already been undone.
REDO : redo the most recent undone command, if no new mutating command has occurred since the undo.

Notes / Rules

UNDO / REDO that cannot be applied should do nothing.
Any new TYPE / DELETE after an UNDO clears the redo history.

Input / Output

Input: a list of commands in the format above.
Output: the editor text after each command.

Example

Commands:

TYPE abc
TYPE d
DELETE 2
UNDO
REDO

Outputs:

abc
abcd
ab
abcd
ab

Constraints (typical)

Up to $2\times 10^5$ commands.
Total typed characters across all TYPE commands up to $2\times 10^5$ .

Problem: Undo/Redo for a Simple Text Editor

Design a data structure that simulates a very small text editor with undo and redo.

You are given a sequence of commands; after each command, output the current text.

Commands

TYPE s : append string s to the end of the current text.

DELETE k : delete the last k characters (if k exceeds current length, delete everything).

UNDO : undo the most recent mutating command ( TYPE or DELETE ) that has not already been undone.

REDO : redo the most recent undone command, if no new mutating command has occurred since the undo.

Notes / Rules

UNDO / REDO that cannot be applied should do nothing.

Any new TYPE / DELETE after an UNDO clears the redo history.

Input / Output

Input: a list of commands in the format above.

Output: the editor text after each command.

Example

Commands:

TYPE abc

TYPE d

DELETE 2

UNDO

REDO

Outputs:

abc

abcd

ab

abcd

ab

Constraints (typical)

Up to

2\times 10^5

commands.

Total typed characters across all TYPE commands up to

2\times 10^5

Implement undo/redo with two stacks

Quick Overview

Implement undo/redo with two stacks

Problem: Undo/Redo for a Simple Text Editor

Commands

Notes / Rules

Input / Output

Example

Constraints (typical)

Submit Your Answer to Earn 20XP

Implement undo/redo with two stacks

Quick Overview

Implement undo/redo with two stacks

Problem: Undo/Redo for a Simple Text Editor

Commands

Notes / Rules

Input / Output

Example

Constraints (typical)

Submit Your Answer to Earn 20XP