Design a text editor with undo/redo
Problem: Text Editor with Undo/Redo
Design and implement a text document editor that supports the following operations:
insert(chars): Appends the given characters to the end of the document.delete(k): Removes up tokcharacters from the end of the document. Ifkexceeds the current document length, all existing characters are removed.undo_last(): Undoes the most recent effective operation.redo_last(): Re-applies the last undone operation.
The design must include an Operation interface (or abstract class) with two methods:
apply(doc) -> doc: Applies the operation to a given document state and returns the new document state.rollback_operation() -> Operation: Returns an inverseOperationobject that can undo the effects of the current operation.
The editor must maintain separate undo and redo stacks. A crucial constraint is that applying any new insert or delete operation must clear the entire redo stack.
A get_current_content() -> str method must be provided to retrieve the current document content.
The implementation should robustly handle various edge cases, including:
- Consecutive
deleteoperations. - Attempting to
deletefrom an empty document. - Calling
undo_last()orredo_last()when their respective stacks are empty. - Ensuring that only effective
deleteoperations (i.e., those that actually remove characters) are recorded for undo.
Candidates are required to analyze the time and space complexity for each operation and justify their data structure choices.
Unit tests should be provided to cover the following scenarios:
- Simple
undo/redoflows. - Multiple consecutive
deleteoperations. deleteoperations wherekis very large and exceeds the current document length.- Sequences of operations that contain no
insertoperations. - Idempotent
redo_last()calls when no operations are available to be redone.
AI interview prep
Core dilemma
The central engineering conflict is balancing efficient state mutation and reversion (undo/redo) with memory usage, especially for large documents and extensive operation histories. It requires careful design of the document representation and the `Operation` objects to avoid performance bottlenecks and excessive memory consumption.
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Design a text editor with undo/redo
Problem: Text Editor with Undo/Redo
Design and implement a text document editor that supports the following operations:
insert(chars): Appends the given characters to the end of the document.delete(k): Removes up tokcharacters from the end of the document. Ifkexceeds the current document length, all existing characters are removed.undo_last(): Undoes the most recent effective operation.redo_last(): Re-applies the last undone operation.
The design must include an Operation interface (or abstract class) with two methods:
apply(doc) -> doc: Applies the operation to a given document state and returns the new document state.rollback_operation() -> Operation: Returns an inverseOperationobject that can undo the effects of the current operation.
The editor must maintain separate undo and redo stacks. A crucial constraint is that applying any new insert or delete operation must clear the entire redo stack.
A get_current_content() -> str method must be provided to retrieve the current document content.
The implementation should robustly handle various edge cases, including:
- Consecutive
deleteoperations. - Attempting to
deletefrom an empty document. - Calling
undo_last()orredo_last()when their respective stacks are empty. - Ensuring that only effective
deleteoperations (i.e., those that actually remove characters) are recorded for undo.
Candidates are required to analyze the time and space complexity for each operation and justify their data structure choices.
Unit tests should be provided to cover the following scenarios:
- Simple
undo/redoflows. - Multiple consecutive
deleteoperations. deleteoperations wherekis very large and exceeds the current document length.- Sequences of operations that contain no
insertoperations. - Idempotent
redo_last()calls when no operations are available to be redone.