Katkat

Design command executor with undo

NetflixSoftware Engineer · Technical Screen

Last 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:

  1. execute(command): Executes a command and stores it in a history log.
  2. 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_state
  • undo(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?