How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Uber.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Uber during technical interviews.

Implement uniform sampling in squares

Quick Overview

Implement uniform sampling in squares evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

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.

Quick Answer: Implement uniform sampling in squares evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

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

Examples

Input: ([2, 3, 1], 0)

Expected Output: 0

Explanation: areas [4,9,1], prefix [4,13,14]. target 0 is in [0,4) -> square 0.

Input: ([2, 3, 1], 3)

Expected Output: 0

Explanation: target 3 is still in [0,4) -> square 0.

Input: ([2, 3, 1], 4)

Expected Output: 1

Explanation: target 4 equals the first cumulative boundary; the boundary belongs to the next square [4,13) -> square 1.

Input: ([2, 3, 1], 12)

Expected Output: 1

Explanation: target 12 is in [4,13) -> square 1.

Input: ([2, 3, 1], 13)

Expected Output: 2

Explanation: target 13 equals the second boundary; belongs to next square [13,14) -> square 2.

Input: ([2, 3, 1], 14)

Expected Output: -1

Explanation: target 14 equals total_area, which is out of the valid half-open range [0,14) -> -1.

Input: ([5], 0)

Expected Output: 0

Explanation: single square, area 25; target 0 is in [0,25) -> square 0.

Input: ([5], 24)

Expected Output: 0

Explanation: target 24 is the last valid index in [0,25) -> square 0.

Input: ([], 0)

Expected Output: -1

Explanation: empty input -> -1 regardless of target.

Input: ([1, 1, 1, 1], 2)

Expected Output: 2

Explanation: four unit squares, prefix [1,2,3,4]. target 2 equals a boundary -> next square, index 2.

Input: ([3, 4], -1)

Expected Output: -1

Explanation: negative target is out of range -> -1.

Hints

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.
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.
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.
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.

Quick Overview