## 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 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)`.

InterviewDB Question · Los Angeles

Rectangle Fitting Tracker - Geometry Coding Interview

Question Details

Problem Design a RectangleFitter that tracks a set of axis-aligned rectangles and answers fitting queries. Example: 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).

Full Details

🔒

Unlock all Codesignal questions

Full insider details, leaked discussions, and candidate experiences.

or every company, $100/year →

About This Question

This is a reported interview question from a codesignal interview.

It covers the following topics: Coding, General Coding Assessment, Q4 .

Topics

Coding General Coding Assessment Q4

Rectangle Fitting Tracker - Geometry Coding Interview

Question Details

Full Details

About This Question

Topics

More Codesignal Interview Questions