Katkat
Back

Apply operations efficiently using Command pattern

OracleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

This problem tests the application of the Command design pattern to encapsulate, track, and optimize a series of state mutations on a shared object.

The Task

You are building a document processing engine. Your system needs to manage a Document state and a sequence of Operation objects that modify this state. Some operations (like 'bold' or 'italicize') are idempotent, while others (like 'insert text') are cumulative.

Implement the Command pattern to support a series of modifications. Your goal is to optimize the execution by merging redundant or reversible operations before applying them to the document.

Requirements

Define an interface Command with an execute(state) method. Implement the following operations:

  • Insert(text): Appends text to the document.
  • Format(style): Applies a style (e.g., 'BOLD') to the document.

The Optimization Challenge

Before executing, the system should pre-process the command queue:

  1. If two consecutive Insert operations exist, merge them into a single Insert operation.
  2. If two consecutive identical Format operations exist, ignore the redundant one.

Example

# Initial state: "Hello"
# Operations: [Insert(" World"), Format("BOLD"), Format("BOLD"), Insert("!")]
# Optimized Queue: [Insert(" World"), Format("BOLD"), Insert("!")]
# Final State: "Hello World!" (with BOLD applied)

Constraints

  • The system must handle a list of up to 10,000 operations.
  • You must maintain the order of operations while allowing for merging.
  • State is mutable; keep your command objects decoupled from the document's internal storage logic.

Hints

Hint 1

Use a stack-based approach while iterating through the command list to easily compare the current command with the last processed command.

Hint 2

The 'execute' method should modify the state object in-place; ensure the state object exposes necessary methods to receive these updates.

Hint 3

Consider defining an 'isMergeableWith' or 'equals' method within the Command interface to keep the optimization logic clean and extensible.

Follow-up questions

  • How would you extend this system to support an 'Undo' operation for every command?
  • If some operations are commutative (order doesn't matter, e.g., applying different text colors), how could you optimize the execution order to maximize merges?
  • What concurrency issues arise if multiple threads attempt to optimize and execute commands on the same document state?