Rectangle board: add rectangles, count those covering a point, and undo

Implement a board that holds axis-aligned rectangles and supports three operations: add a rectangle, return how many rectangles on the board contain a given point, and undo. This was the coding round of an onsite. A starting interface (adjust it to the interviewer's answers), where `(x1, y1)` and `(x2, y2)` are opposite corners of the rectangle: ```python class RectangleBoard: def add(self, x1: int, y1: int, x2: int, y2: int) -> None: ... def count(self, x: int, y: int) -> int: ... def undo(self) -> bool: ... ``` ### Clarifying Questions - Are coordinates integers? Can the corners be given in any order, and can a rectangle have zero width or zero height? - Does a point on an edge or exactly on a corner count as inside? - Roughly how many rectangles and queries are expected, and is `count` called much more often than `add`? - What should `undo` do when there is nothing left to undo? - Is redo required? ### Part 1 — Add and count Implement `add` and `count`: `count(x, y)` returns the number of rectangles currently on the board that contain the point `(x, y)`. The same rectangle added twice counts twice. ```hint Measure before optimizing Write the direct version first, then ask how the numbers of adds and queries compare before reaching for a spatial structure. ``` #### What This Part Should Cover - A correct containment test, including corner normalization and the agreed boundary rule - The complexity of the direct approach and when it is good enough - A faster structure for query-heavy workloads, with its costs ### Part 2 — Undo Add `undo()`, which reverts the most recent `add` that has not already been undone and reports whether anything was undone. ```hint Remember what changed Decide what to record at the moment of each change so that reverting it never requires rebuilding the board. ``` #### What This Part Should Cover - The history structure and the exact behavior on an empty history - How undo interacts with whatever index Part 1 uses - The complexity of undo ### What a Strong Answer Covers - Settles coordinate types, corner order, the boundary rule and the empty-undo behavior before coding - Clean, correct code for all three operations, with tests that include edges, corners, duplicates and repeated undo - A complexity analysis, and a justified choice between the direct approach and an index - A history design that generalizes to other mutating operations and to redo ### Follow-up Questions - Add redo. What happens to the redo history when a new rectangle is added after an undo? - Add `remove(rect_id)` and make `undo` revert removals as well. - The board holds a very large number of rectangles and `count` is called far more often than `add`. What structure would you use, and how does undo interact with it? - Return the ids of the rectangles that contain the point, newest first. What changes?