Design Elements Intersection: Find Overlapping Rectangles and Compute Intersection Areas
Question Details
Problem
You are given a list of axis-aligned rectangles representing UI elements on a canvas, each defined as (x1, y1, x2, y2) where (x1,y1) is the top-left corner. Implement:
find_intersecting_pairs()—
return all pairs of rectangles that overlap.
2. intersection_area(r1, r2) —
return the area of the overlapping region (0 if they don't intersect).
3. total_covered_area() —
return the total area of canvas covered by at least one rectangle (no double-counting).
python
def intersection_area(r1: tuple, r2: tuple) -> int:
x1 = max(r1[0], r2[0]); x2 = min(r1[2], r2[2])
y1 = max(r1[1], r2[1]); y2 = min(r1[3], r2[3])
**return** max(0, x2-x1) * max(0, y2-y1)
Rects: [(0,0,4,4), (2,2,6,6), (10,10,12,12)]
Intersecting pairs: [(0,0,4,4) & (2,2,6,6)]
Intersection area: (2,2,4,4) -> 4
Total covered area: 16 + 16 - 4 + 4 = 32
Follow-ups
find_intersecting_pairsis O(n^2). Describe a sweep-line algorithm that improves this.- How does
total_covered_areachange for 1000 rectangles? Is inclusion-exclusion still feasible? - What if rectangles can be rotated (not axis-aligned)? What algorithm handles this case?
- In a real UI system, overlapping elements affect z-order rendering. How would you sort overlapping elements for correct paint order?
Full Details
Problem
You are given a list of axis-aligned rectangles representing UI elements on a canvas, each defined as (x1, y1, x2, y2) where (x1,y1) is the top-left corner. Implement:
find_intersecting_pairs()—
return all pairs of rectangles that overlap.
2. intersection_area(r1, r2) —
return the area of the overlapping region (0 if they don't intersect).
3. total_covered_area() —
return the total area of canvas covered by at least one rectangle (no double-counting).
python
def intersection_area(r1: tuple, r2: tuple) -> int:
x1 = max(r1[0], r2[0]); x2 = min(r1[2], r2[2])
y1 = max(r1[1], r2[1]); y2 = min(r1[3], r2[3])
**return** max(0, x2-x1) * max(0, y2-y1)
Rects: [(0,0,4,4), (2,2,6,6), (10,10,12,12)]
Intersecting pairs: [(0,0,4,4) & (2,2,6,6)]
Intersection area: (2,2,4,4) -> 4
Total covered area: 16 + 16 - 4 + 4 = 32
Follow-ups
find_intersecting_pairsis O(n^2). Describe a sweep-line algorithm that improves this.- How does
total_covered_areachange for 1000 rectangles? Is inclusion-exclusion still feasible? - What if rectangles can be rotated (not axis-aligned)? What algorithm handles this case?
- In a real UI system, overlapping elements affect z-order rendering. How would you sort overlapping elements for correct paint order?
About This Question
This is a reported interview question from a figma interview during the phone round.