How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding 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 Coding Question

Implement undo/redo with two stacks

Company: Airtable

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

## 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: 1. `TYPE abc` 2. `TYPE d` 3. `DELETE 2` 4. `UNDO` 5. `REDO` Outputs: 1. `abc` 2. `abcd` 3. `ab` 4. `abcd` 5. `ab` ### Constraints (typical) - Up to \(2\times 10^5\) commands. - Total typed characters across all `TYPE` commands up to \(2\times 10^5\).

Quick Answer: 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.

You are given a list of commands for a very small text editor. The editor starts with an empty string. Process the commands in order and return the current text after each command. Supported commands: - `TYPE s`: append string `s` to the end of the current text. - `DELETE k`: delete the last `k` characters. If `k` is larger than the current text length, delete everything. - `UNDO`: undo the most recent `TYPE` or `DELETE` command that has not already been undone. - `REDO`: redo the most recent undone command, if possible. Rules: - `UNDO` or `REDO` with nothing to apply should do nothing. - Any new `TYPE` or `DELETE` after an `UNDO` clears the redo history. - After every command, record the current text. Return the list of recorded texts.

Constraints

0 <= len(commands) <= 2 * 10^5
The total number of characters across all `TYPE` commands is at most 2 * 10^5
Each command is valid and follows one of these formats exactly: `TYPE s`, `DELETE k`, `UNDO`, `REDO`
0 <= k <= 2 * 10^5

Examples

Input: (["TYPE abc", "TYPE d", "DELETE 2", "UNDO", "REDO"],)

Expected Output: ["abc", "abcd", "ab", "abcd", "ab"]

Explanation: This is the basic undo/redo flow: type, type, delete, undo the delete, then redo it.

Input: (["UNDO", "TYPE hi", "DELETE 5", "UNDO", "REDO", "REDO"],)

Expected Output: ["", "hi", "", "hi", "", ""]

Explanation: The first UNDO does nothing. DELETE 5 removes all of "hi". The last REDO also does nothing because there is nothing left to redo.

Input: (["TYPE a", "TYPE bc", "UNDO", "TYPE d", "REDO", "DELETE 2", "UNDO"],)

Expected Output: ["a", "abc", "a", "ad", "ad", "", "ad"]

Explanation: After UNDO, typing `d` clears the redo history, so the later REDO has no effect.

Input: ([],)

Expected Output: []

Explanation: No commands means no outputs.

Input: (["TYPE hello", "DELETE 2", "TYPE y", "UNDO", "UNDO", "REDO", "TYPE !", "UNDO", "REDO"],)

Expected Output: ["hello", "hel", "hely", "hel", "hello", "hel", "hel!", "hel", "hel!"]

Explanation: This case checks multiple undos/redos and verifies that a new TYPE clears the redo stack.

Hints

Use one stack for applied mutating operations and another stack for operations that were undone and could be redone.
For a `DELETE`, store the actual removed substring, not just `k`, so that an `UNDO` can restore the text exactly.

Quick Overview

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.