Katkat
Back

Design paint editor with undo/redo

BlackRockSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates a candidate's ability to implement mutable state management, efficient data structures and algorithms for pixel operations (draw, erase, flood fill) alongside correct undo/redo history tracking and state consistency.

Implement a simplified Paint editor that supports drawing on a 2D canvas and reverting changes using undo and redo operations.

Canvas

You are given a 2D grid representing a canvas. Each cell can store:

  • a color value (string or integer), or
  • None for an empty cell.

You will initialize the canvas with a given width and height. Assume coordinates are zero-based and given as (x, y) where x is the column index and y is the row index. Coordinates are guaranteed to be within bounds.

Required Operations

You must design and implement a Paint class with the following methods:

  1. draw(x, y, color)
  • Set the pixel at position (x, y) to the given color.
  1. erase(x, y)
  • Remove whatever color is at (x, y) and set it back to empty (None).
  1. fill(x, y, color)
  • Perform a flood fill operation starting at (x, y):
  • Let orig be the color currently at (x, y).
  • Replace the pixel at (x, y) with color.
  • Recursively replace any adjacent cells (up, down, left, right) that have color orig with color.
  • Stop expanding when encountering a different color or the canvas boundary.
  • If orig is already equal to color, the operation may be a no-op.
  1. undo()
  • Revert the canvas to the state before the most recent modifying operation (draw, erase, or fill).
  • If there is no operation to undo, this may be a no-op.
  1. redo()
  • Re-apply the most recently undone operation, restoring the canvas to the state after that operation.
  • If there is no operation to redo, this may be a no-op.

Behavior Rules

  • Any operation that modifies the canvas (draw, erase, fill) should become an undoable action.
  • Calling undo() moves the current state into a redo history so that it can be restored with redo().
  • Calling redo() re-applies that state and moves it back into the undo history.
  • After performing a new modifying operation (draw, erase, fill), the redo history must be cleared.
  • All operations should be deterministic and consistent.

Requirements

  • Design and implement the Paint class and its methods.
  • You may choose any reasonable data structures for representing:
  • The canvas.
  • Undo and redo histories.
  • Your implementation must correctly maintain canvas state, undo/redo history, and fill behavior.

Assume reasonable constraints, e.g., canvas up to a few thousand by a few thousand cells and up to tens of thousands of operations.