Rectangle grid with IDs: coverage counts, replace and delete, O(1) queries, batch undo

Implement a class that maintains a two-dimensional grid of cells onto which rectangles are placed, each rectangle with its own ID. The requirements arrive in five parts, each building on the code from the previous one. Expect a fair amount of code; having a clear plan for undo before Part 4 makes the later parts much smoother. Assume, unless the interviewer says otherwise, that the grid has `width` columns and `height` rows, that cell `(x, y)` satisfies `0 <= x < width` and `0 <= y < height`, and that a rectangle is given by two opposite corner cells `(x1, y1)` and `(x2, y2)` with `x1 <= x2` and `y1 <= y2`, covering every cell between them, corners included. Rectangles may overlap. ### Clarifying Questions - Is a rectangle that extends past the grid rejected, clipped, or ruled out by contract? - Are the corners always given in order, or must the class normalize them? - How should a failed operation, such as removing an unknown ID, be reported: an exception, a return value, or silently? ### Part 1 — Add rectangles and count coverage Implement `add(rect_id, x1, y1, x2, y2)` and `query(x, y)`, which returns how many rectangles cover cell `(x, y)`. In this part every ID is new. ```hint Correct first Start with the representation that makes both operations obviously correct; the later parts will say which operation has to be fast. ``` #### What This Part Should Cover - Inclusive boundary handling and validation of the input - A clear data representation, with the cost of each operation - A few hand-checked cases with overlapping rectangles ### Part 2 — Replace and delete by ID Adding a rectangle with an ID that already exists replaces that ID's old rectangle with the new one. Also implement `remove(rect_id)`, which deletes the rectangle with that ID. ```hint Replacing safely Think about what has to happen to the old rectangle before the new one takes effect, and what should remain if the new rectangle turns out to be invalid. ``` #### Clarifying Questions for this Part - If the replacement rectangle is invalid, should the old rectangle stay in place? #### What This Part Should Cover - An ID-to-rectangle mapping and the exact replacement semantics - Behavior for unknown IDs and invalid replacements - How the cost of each operation changes, if at all ### Part 3 — Constant-time queries Change the implementation so that `query` runs in O(1), while `add` and `remove`, including replacement, take time proportional to the area of the rectangles they touch. ```hint Shift the work Decide what per-cell information could be kept up to date on every write so that a query becomes a single lookup. ``` #### What This Part Should Cover - The per-cell state maintained on every write, kept consistent with the ID map - The exact cost of add, remove and replace, and the memory used - When this trade-off is the wrong one, for example for a very large grid ### Part 4 — Undo Implement `undo()`, which reverts the most recent successful modification. Undoing a replacement must restore the previous rectangle for that ID, and calling `undo()` repeatedly keeps walking back through earlier modifications. ```hint Remember the past For each successful change, record just enough to put every affected ID back exactly the way it was. ``` #### Clarifying Questions for this Part - Do failed operations and queries leave anything to undo? - What should `undo()` do when there is nothing left to undo? #### What This Part Should Cover - A history record that handles add, replace and remove uniformly - Undo that restores both the ID map and the per-cell state - The cost of undo and the memory the history uses ### Part 5 — Remove everything at a point Implement `remove_at(x, y)`, which deletes every rectangle covering cell `(x, y)`. A single `undo()` must restore that whole batch. ```hint One change, many rectangles Let a single history record describe several IDs at once. ``` #### Clarifying Questions for this Part - If no rectangle covers the cell, does the call count as a modification that `undo()` would consume? #### What This Part Should Cover - Finding the covering rectangles, and its cost - A batch history entry that one undo reverses completely - Whether to keep extra per-cell data to make this operation faster ### What a Strong Answer Covers - Incremental code that keeps the ID map, the per-cell counts and the history consistent after every operation - Correct inclusive boundaries and validation of rectangles and IDs - Stated complexity for every operation in every version, meeting the Part 3 bounds - One history format that handles add, replace, delete and batch delete - Tests for tricky sequences: replace then undo, undo across a batch, undo with an empty history ### Follow-up Questions - Add `redo()`. What happens to it when a new modification arrives after an undo? - The grid is a billion cells on each side and rectangles can be enormous. What can you offer for `add` and `query` now? - How would you cap the memory used by the undo history? - Several threads call these methods at once. What must be atomic?