Build a Rectangle Board with Remove-at-Cell, Batch Remove, and Undo

Implement a 2D board that holds axis-aligned rectangles. The requirements arrive one at a time, and each Part builds on your code from the previous one, so the later Parts reward a structure that extends without a rewrite. The focus is data structures and state management rather than a clever algorithm. ### Constraints and Clarifications - Assume the board is a grid of `width` by `height` integer cells; cell `(x, y)` has `0 <= x < width` and `0 <= y < height`. - A rectangle is given by inclusive corner cells `(x1, y1)` and `(x2, y2)` with `x1 <= x2` and `y1 <= y2`. - Unless the interviewer decides otherwise, assume rectangles may overlap and a rectangle added later is drawn on top. - Provide a way to read the board back so each Part can be tested, for example `top_at(x, y)`, which returns the id of the rectangle drawn on top at a cell, or `None`. ### Clarifying Questions - Can rectangles overlap, and if so, which one is visible at a shared cell? - Is a rectangle removed by the id that `add_rectangle` returned, or by its coordinates? - What should happen for a rectangle that extends past the board's edge, or for removing an id that is not on the board? - Does `undo` need a matching `redo`? ### Part 1 — Add and remove rectangles Implement `add_rectangle(x1, y1, x2, y2) -> int`, which places a rectangle and returns its id, and `remove_rectangle(rect_id) -> bool`, which takes it off the board. ```hint Pick the stored state Decide whether the board stores painted cells or a collection of rectangles, and consider what each choice makes easy or hard once removed rectangles must come back and cells must be queried. ``` #### What This Part Should Cover - A storage model and the reason for it - Id assignment and validation of the coordinates - Behavior for overlapping rectangles and for removing an unknown id ### Part 2 — Undo Implement `undo()`, which reverts the most recent operation that changed the board. Repeated calls keep stepping back through earlier changes. ```hint What undo must remember For each kind of change, ask what information reverses it exactly, so that the board after an undo is identical to the board before the change, including which rectangle is visible where. ``` #### Clarifying Questions for this Part - Should an operation that changed nothing, such as removing an unknown id, count as a step for `undo`? - What should `undo` do when there is nothing left to undo? #### What This Part Should Cover - A history representation (inverse operations or snapshots) and its memory cost - Exact restoration: the same id, the same coordinates and the same stacking order - No-op operations and an empty history ### Part 3 — Remove the rectangle at a cell Implement `remove_at(x, y)`, which removes the rectangle at cell `(x, y)`. It must be undoable like any other change. ```hint Which one, and how fast Decide which rectangle is meant when several cover the cell, and estimate what finding it costs as the number of rectangles grows. ``` #### Clarifying Questions for this Part - When several rectangles cover the cell, is the topmost one removed, or all of them? - Is `remove_at` addressed by a board cell, as assumed here, or by a position in the list of rectangles? #### What This Part Should Cover - The selection rule at a covered cell, and the empty-cell case - The cost of the lookup, and when a spatial index would pay off - Reuse of the existing removal and history path ### Part 4 — Batch remove Implement `batch_remove(rect_ids)`, which removes several rectangles in one call. A single `undo` must restore all of them. ```hint One step or many Think about what the user sees if the batch is recorded as several separate changes, and about what should happen when one of the ids is not on the board. ``` #### Clarifying Questions for this Part - If one id in the batch is unknown or repeated, should the whole batch fail, skip that id, or remove the rest? - Is a batch selected by a list of ids, or by everything inside a region of the board? #### What This Part Should Cover - A history entry that groups the batch, so one undo restores all of it - Validation before any change, and duplicates or unknown ids in the input - The cost of a batch and of undoing it ### What a Strong Answer Covers - A data model that each new requirement extends without a rewrite - One mutation path through which every change is recorded for undo - Exact restoration of ids, coordinates and stacking order - Clear, tested behavior for no-ops, unknown ids, empty cells and an empty history - The complexity of each operation, and where a spatial index would change it ### Follow-up Questions - Add `redo`. What happens to the redo history when a new change is made after an undo? - Add an operation that moves a rectangle. What does undo need in order to support it? - The board holds a very large number of rectangles and `remove_at` is called constantly. How would you make it fast, and what does that do to add, remove and undo? - How would you cap the memory used by a long undo history?