Generate Random Point in a Circle

Generate Random Point in a Circle

What is this problem about?

The Generate Random Point in a Circle coding problem asks you to implement a function that returns a random point $(x, y)$ that lies within a given circle. You are given the radius and the center coordinates $(x\_center, y\_center)$. Every point inside the circle must have an equal probability of being selected (uniform distribution).

Why is this asked in interviews?

Meta and other companies use this to test your knowledge of Math, Probability, and Rejection Sampling. It evaluation whether you understand the pitfalls of uniform distribution—specifically, that simply picking a random angle and a random radius leads to more points clustering near the center. It tests your ability to use geometric properties to achieve true uniformity.

Algorithmic pattern used

There are two common solutions:

1. Rejection Sampling:
   • Generate a random point $(x, y)$ within a square of side $2R$ that encloses the circle.
   • Check if the point is inside the circle: $dx^2 + dy^2 \le R^2$.
   • If not, discard and try again. This is perfectly uniform but can take multiple attempts.
2. Polar Coordinates (Inverse Transform Sampling):
   • Pick a random angle $heta$ in $[0, 2\pi]$.
   • Pick a random radius $r$ by taking the square root of a random number in $[0, 1]$ and multiplying by $R$: $r = R imes \sqrt{rand(0, 1)}$. The square root is necessary to correct the area density bias.

Example explanation

Circle at (0,0) with Radius 1.

1. Using Rejection Sampling:
   • Generate $x=0.8, y=0.8$. $0.8^2 + 0.8^2 = 1.28$. $1.28 > 1^2$. Discard.
   • Generate $x=0.2, y=0.3$. $0.2^2 + 0.3^2 = 0.13 \le 1$. Return (0.2, 0.3).
2. Using Polar:
   • Pick $heta = \pi/4$, $u = 0.25$.
   • $r = 1 imes \sqrt{0.25} = 0.5$.
   • Point: $(0.5 \cos(\pi/4), 0.5 \sin(\pi/4))$.

Common mistakes candidates make

• Area Bias: Using $r = R imes rand(0, 1)$ without the square root. This results in a distribution where points are 4x denser at the center than at the edge.
• Floating Point Errors: Not using proper random float generators.
• Square vs Circle: Forgetting that points in the "corners" of the bounding square are not in the circle.

Interview preparation tip

Always discuss why the naive approach (without the square root) is biased. Showing that you understand the relationship between radius and area ($Area = \pi r^2$) is what separates an average candidate from a great one.