Random point in non-overlapping squares

Implement a class for an axis-aligned square on the plane that returns a uniformly random point inside it. Then extend the design to N non-overlapping squares: return a point uniformly random over their union, so each square is chosen with probability proportional to its area. Specify the APIs, the data structures, the sampling algorithm and its cost, and how you avoid bias from floating-point precision.

Interface

Unless you agree on a different interface with the interviewer, assume:

• Square(x: float, y: float, side: float) with sample() -> tuple[float, float] — a uniform point in [x, x + side) × [y, y + side).
• SquareSampler(squares: list[Square]) with sample() -> tuple[float, float] — uniform over the union.
• The deterministic core, so it can be tested: pick_square(sides: list[int], target: int) -> int — with areas sides[i]² and prefix sums prefix, return the index i whose half-open range [prefix[i-1], prefix[i]) contains target (with prefix[-1] = 0), or -1 if sides is empty, target < 0 or target >= total area.

Example

sides = [2, 3, 1]          # areas [4, 9, 1], prefix [4, 13, 14], total 14
pick_square(sides, 0)   ->  0
pick_square(sides, 3)   ->  0
pick_square(sides, 4)   ->  1     # a boundary belongs to the next square
pick_square(sides, 13)  ->  2
pick_square(sides, 14)  ->  -1    # past the total area

SquareSampler.sample() draws target uniformly in [0, 14), picks the square with pick_square, then calls that square's sample().

Constraints

• 0 <= N <= 10^5; integer sides 1 <= side <= 10^4, so total area fits in 64 bits.
• Many sample() calls per sampler.

Clarifying questions

• Are side lengths integers or floats? Are coordinates integers?
• Should points be continuous or integer lattice points?
• Do squares really never overlap? What should happen if they do?
• Will squares be added or removed after construction?

What a strong answer covers

• One square: x + random() * side, y + random() * side.
• Many squares: prefix sums of areas built once in O(N), then a binary search per sample (bisect_right) in O(log N).
• The boundary rule: half-open ranges so that every unit of area belongs to exactly one square and nothing is double-counted.
• Avoiding bias: choose the square with an integer draw over integer areas (randrange(total)), and use floats only for the point inside the chosen square.
• Testing randomness: fix the seed for unit tests, and run a chi-squared or simple frequency check over many samples.

Follow-ups

• Rectangles instead of squares. What changes?
• The squares may overlap. How do you stay uniform over the union (rejection sampling, or splitting into disjoint pieces)?
• Squares are added and removed between samples. Use a Fenwick tree over areas.
• Pick integer lattice points uniformly, counting points rather than area.