Implement uniform sampling in squares

Implement a class Square representing an axis-aligned square on the 2D plane that supports sampling a uniformly random point inside the square. Then extend your design to handle an array of N non-overlapping squares and support picking a uniformly random point from the union of all squares (i.e., each point’s probability is proportional to its square’s area). Specify the APIs you would expose, the data structures used (e.g., prefix sums over areas), the algorithm for sampling, time/space complexity, and how you would avoid bias from floating-point precision.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Weighted Square Selection (Uniform Sampling Core)

You are sampling a uniformly random point from the union of N non-overlapping axis-aligned squares, where each point's probability is proportional to its square's area. The standard algorithm draws a random value target in [0, total_area), then picks the square whose cumulative-area interval contains target, and finally samples a point uniformly inside that square.

Implement the weighted-selection core of that algorithm. Given sides (a list where sides[i] is the side length of square i, so its area is sides[i] * sides[i]) and a value target, build prefix sums over the areas and return the index i of the square whose half-open cumulative-area interval [prefix[i-1], prefix[i]) contains target (with prefix[-1] = 0).

Return -1 if the input is empty, if target < 0, or if target >= total_area.

Why a half-open interval: each square owns [prefix[i-1], prefix[i]). A target exactly equal to a cumulative boundary belongs to the NEXT square, which is precisely what a bisect_right over the prefix array yields. This boundary rule is what keeps the sampling unbiased.

Example: sides = [2, 3, 1] -> areas [4, 9, 1], prefix [4, 13, 14], total 14.

• target = 3 -> index 0 (in [0, 4))
• target = 4 -> index 1 (boundary belongs to next square, [4, 13))
• target = 13 -> index 2 (boundary, [13, 14))
• target = 14 -> -1 (>= total area)

Constraints

• 1 <= N <= 10^5 squares (N may be 0, in which case return -1).
• 1 <= sides[i] <= 10^4 (integer side lengths; area fits comfortably in a 64-bit integer for the totals).
• 0 <= target < total_area for a valid in-range query; out-of-range or negative target returns -1.
• Squares are non-overlapping, so areas add without double-counting.
• Use a half-open interval per square: a target equal to a cumulative boundary belongs to the next square (bisect_right semantics).

Hints

1. Convert each side length to an area (side * side), then build a running prefix-sum array of cumulative areas. The last entry is the total area.
2. To pick a square for a given target, binary-search for the first prefix value strictly greater than target. That index is the owning square. Python's bisect.bisect_right does exactly this.
3. Get the boundary rule right: square i owns [prefix[i-1], prefix[i]). A target exactly equal to prefix[i-1] belongs to square i, not square i-1 -- this is what keeps the sampling unbiased. Guard the empty list, negative target, and target >= total_area by returning -1.
4. Full sampling (not graded here): draw target = random()*total_area to pick the square, then draw a point uniformly within that square's [x, x+side) x [y, y+side) box. To avoid floating-point bias, do the weighted selection on integer areas (as here) and only introduce floats for the final intra-square coordinate.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

Implement a class Square representing an axis-aligned square on the 2D plane that supports sampling a uniformly random point inside the square. Then extend your design to handle an array of N non-overlapping squares and support picking a uniformly random point from the union of all squares (i.e., each point’s probability is proportional to its square’s area). Specify the APIs you would expose, the data structures used (e.g., prefix sums over areas), the algorithm for sampling, time/space complexity, and how you would avoid bias from floating-point precision.

Recommended Approach

Start with a brute-force baseline to confirm correctness, then identify the repeated work or ordering property that enables a better data structure such as a hash map, heap, stack, queue, two pointers, prefix sums, BFS/DFS, or dynamic programming. Write the implementation around a small invariant and test that invariant directly.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

State the baseline complexity and the optimized complexity. For most interview constraints, justify why the optimized approach meets the expected input size.

Edge Cases and Tests

Empty and singleton inputs, duplicates, ties, invalid inputs, boundary values, and tests that exercise the main invariant.