Random Point in Non-overlapping Rectangles

Random Point in Non-overlapping Rectangles

What is this problem about?

The Random Point in Non-overlapping Rectangles problem asks you to uniformly randomly pick a point in a set of non-overlapping axis-aligned rectangles. The point is picked with probability proportional to the rectangle's area. This coding problem combines weighted random selection with 2D point generation. The array, math, binary search, reservoir sampling, randomized, and prefix sum interview pattern is demonstrated.

Why is this asked in interviews?

Uber and Google ask this because it extends random pick with weight to 2D geometry. The key: the probability of picking each rectangle is proportional to its area, then uniformly sample within the chosen rectangle.

Algorithmic pattern used

Area-weighted prefix sums + binary search + 2D sampling. Compute area of each rectangle. Build prefix area array. For each pick: random number in [1, total_area], binary search for the rectangle. Within the chosen rectangle (x1,y1,x2,y2): pick random x in [x1,x2], random y in [y1,y2].

Example explanation

rects=[(1,1,3,3),(5,5,8,7)]. Areas: 4, 6. Prefix: [4,10]. Total=10.

• Pick r=3: bisect_left([4,10],3)=0 → rectangle 0. Random x in [1,3], y in [1,3].
• Pick r=7: bisect_left([4,10],7)=1 → rectangle 1. Random x in [5,8], y in [5,7].

Common mistakes candidates make

• Using perimeter instead of area for weighting.
• Off-by-one in rectangle area: (x2-x1+1)*(y2-y1+1) for grid points.
• Incorrect random point generation within rectangle.
• Not handling rectangles of area 1 (single point).

Interview preparation tip

Random Point in Non-overlapping Rectangles combines area-weighted sampling with 2D point generation. The two-step process: (1) pick rectangle proportional to area, (2) uniform point within chosen rectangle — is the standard approach for any multi-region sampling problem. Practice extending this to 3D volumes, irregular shapes (triangles), or dynamic rectangle additions.