Design command executor with undo
NetflixSoftware Engineer · Technical ScreenLast updated
This problem tests the application of the Command design pattern and stack-based data structures to manage reversible operations in an application state.
Problem Statement
Design a command executor system that manages the state of a simple text document. The system must support performing operations (commands) and rolling them back (undo).
Implement the CommandExecutor class, which manages a document represented as a single string. You need to implement the following operations:
execute(command): Executes a command and stores it in a history log.undo(): Reverses the last successfully executed command and removes it from the history.
Define an interface Command that contains the following methods:
execute(current_state) -> new_stateundo(current_state) -> previous_state
Requirements
- The system should maintain a history of commands performed.
- If an
undo()is called when the history is empty, the system should do nothing. - The state of the document is a single string.
Example
# Assume a command that appends a string
class AppendCommand:
def __init__(self, text_to_add):
self.text_to_add = text_to_add
def execute(self, state): return state + self.text_to_add
def undo(self, state): return state[:-len(self.text_to_add)]
executor = CommandExecutor()
executor.execute(AppendCommand("Hello"))
executor.execute(AppendCommand(" World"))
# Current state: "Hello World"
executor.undo()
# Current state: "Hello"
Constraints
- Commands should be atomic.
- The history can grow indefinitely; consider memory management if necessary.
- Handle cases where the document state might be empty.
Hints
Hint 1
Use two stacks: one to keep track of the executed commands and another to hold the current state or references to objects to reconstruct previous states.
Hint 2
The Command pattern allows you to encapsulate all parameters needed for an action within an object, making it easy to store in a stack.
Hint 3
Ensure the Command interface clearly distinguishes between the 'forward' logic and the 'inverse' logic for every operation.
Follow-up questions
- How would you implement a 'redo' feature? What happens if a new command is executed after an undo operation?
- How would you limit the command history size to a fixed number of operations (e.g., last 100 actions)?
- How would you make this thread-safe if multiple users were editing the same document simultaneously?
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.