Rectangle Fitting Tracker - Geometry Coding Interview

Question

## Problem Design a `RectangleFitter` that tracks a set of axis-aligned rectangles and answers fitting queries. ```python class RectangleFitter: def add_rect(self, rect_id: str, w: int, h: int) -> None: ... def remove_rect(self, rect_id: str) -> None: ... def fits_in(self, W: int, H: int) -> list[str]: # Return all rect_ids where w <= W and h <= H, sorted by area desc ... def largest_fitting(self, W: int, H: int) -> str | None: # Return rect_id with largest area that fits in W x H container ... def count_fitting(self, W: int, H: int) -> int: ... ``` **Example:** ``` rf = RectangleFitter() rf.add_rect("A", 3, 4) # area 12 rf.add_rect("B", 5, 2) # area 10 rf.add_rect("C", 2, 2) # area 4 rf.fits_in(4, 4) -> ["A", "C"] # B: 5>4 fails rf.largest_fitting(4,4) -> "A" rf.count_fitting(2,2) -> 1 ``` ## Follow-ups - For `fits_in` with n rectangles and q queries, can you preprocess to answer each query in sub-O(n) time? - What 2D data structure (e.g., fractional cascading, 2D segment tree) could help here? - Extend to rotatable rectangles: a rect `(w, h)` fits if `(w<=W and h<=H) or (h<=W and w<=H)`.

Rectangle Fitting Tracker - Geometry Coding Interview

Question Details

Full Details

Topics

More from Codesignal