Sample Points Uniformly from a Unit Disk
Company: Waymo
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Sample Points Uniformly from a Unit Disk
Write a function that takes the requested number of points, `n`, and returns `n` random two-dimensional points distributed uniformly over the area inside the unit circle centered at the origin.
The output is a collection of coordinate pairs. Explain why the sampling rule is uniform over the disk's area. The task does not prescribe a random seed or a fixed sequence of coordinates; many sampled outputs are valid.
### Clarifications
Uniformity is over area, rather than over the radius alone or only around the circumference. The input represents a number of requested points. Discuss the empty output when no points are requested.
```hint Compare regions with equal area
Consider how much of the disk lies within a chosen distance of the center.
```
### What a Strong Answer Covers
- Generates points inside the radius-one disk and returns the requested number of coordinate pairs.
- Explains the radial distribution needed for uniform area coverage.
- Distinguishes random sampling from returning one deterministic coordinate list.
- States the time and storage cost in terms of the requested number of points.
### Follow-up Questions
- Why does choosing a radius uniformly between zero and one concentrate points near the center?
- How would rejection sampling from the surrounding square produce another valid uniform sampler?
Overview: Derive uniform random sampling inside a unit disk, explain the radial distribution, and compare a polar sampler with rejection sampling.
Read the full Waymo Data Scientist interview experience this question came from
Community answers
Answer by seanlee2019sf
import math
import random
def sample_unit_disk(n):
points = []
for _ in range(n):
radius = math.sqrt(random.random())
angle = 2.0 math.pi random.random()
points.append((radius math.cos(angle), radius math.sin(angle)))
return points
Answer by CS20BT023.alum24
To sample points uniformly over the area of a unit disk, generating polar coordinates $(\theta, r)$ using a uniform radius $r \sim U(0, 1)$ fails because outer concentric rings have larger circumferences and contain more area than inner rings. Sampling $r$ uniformly leads to a higher density of points near the center.
To achieve uniform density per unit area, we use the Inverse Transform Sampling method on the polar cumulative distribution function (CDF):
$$r = \sqrt{U_1}, \quad \theta = 2\pi U_2 \quad \text{where } U_1, U_2 \sim U(0, 1)$$
Converting back to Cartesian coordinates yields:
$$x = \sqrt{U_1} \cos(2\pi U_2), \quad y = \sqrt{U_1} \sin(2\pi U_2)$$