Counting Points Kept by Rejection Sampling
Updated
Problem statement
You want random points inside the unit ball in d dimensions (the unit disk when d = 2). You make a candidate point by choosing each of its d coordinates independently and uniformly between 0 and 1. You keep the point if the sum of the squares of its coordinates is at most 1; otherwise you throw it away.
You make z candidate points this way. Return the standard deviation of the number of points you keep.
Your answer is accepted if its absolute error or its relative error is at most 10^-9.
Function
keptCountStdDev(z: int, d: int) → doubleExamples
Example 1
z = 1000d = 2return = 12.982599444231628This is the interview case. A candidate is a uniform point in the unit square, and it is kept when it lies in the quarter of the unit disk inside that square. So each candidate is kept with chance p = (π/4) / 1 = π/4 ≈ 0.7854, independently of the others.
The number kept is binomial: its average is 1000 p ≈ 785.4 and its standard deviation is √(1000 p (1 - p)) ≈ √168.55 ≈ 12.98.
Example 2
z = 1000d = 3return = 15.793767688245294In three dimensions the unit ball has volume 4π/3, and the part with all coordinates positive is one eighth of it. So p = π/6 ≈ 0.5236.
The average is about 523.6, and the standard deviation is √(1000 p (1 - p)) ≈ √249.44 ≈ 15.79.
Example 3
z = 5d = 1return = 0.0In one dimension a candidate is a single number between 0 and 1, and its square is always at most 1. Every candidate is kept, so exactly 5 are kept every time and the standard deviation is 0.
Constraints
1 <= z <= 10^91 <= d <= 30
More Susquehanna International Group (SIG) Phone Screen questions
- Dice Sum That Is a Multiple of mPHONE SCREEN · Seen Nov 2026
- Find Median from Data StreamPHONE SCREEN · Seen Nov 2026
- Painting Arcs to Nearest Neighbors on a CirclePHONE SCREEN · Seen Sep 2026
- Filter Movies by Inclusive Year RangePHONE SCREEN · Seen Jul 2026
- Best Single Reroll for Five DicePHONE SCREEN · Seen Feb 2026
- Catching the Bus to the MoviePHONE SCREEN · Seen Jan 2026
- Two Dice Summing to a TargetPHONE SCREEN · Seen Jan 2026
- Median of Uniform Draws in an IntervalPHONE SCREEN · Seen Oct 2025
- One Number Is the Average of the Other TwoPHONE SCREEN · Seen Jun 2025
- Which Coin Pattern Shows Up FirstPHONE SCREEN · Seen May 2025
Similar questions at other companies
- Range of a Third CorrelationTower Research Capital · PHONE SCREEN
- Three Points in a Semicircle: Monte Carlo EstimateSquarepoint Capital · PHONE SCREENSquarepoint Capital interview questions
- Union Area of Two RectanglesDocuSign · PHONE SCREENDocuSign interview questions
- Intersection of Two RectanglesFigma · PHONE SCREENFigma interview questions
- Light Source Hits: Sample, Compare, and FitOpenAI · PHONE SCREENOpenAI interview questions
- Max Points on a LineUber · PHONE SCREENUber interview questions
- Count Axis-Aligned and Rotated SquaresGoogle · PHONE SCREENGoogle interview questions
- Best-Fit Plane Normal from 3D PointsThe Voleon Group · PHONE SCREEN
- Meeting of Points Moving Toward Initial SuccessorsThe Walt Disney Company · PHONE SCREENThe Walt Disney Company interview questions
- Maximum Visible DronesAnduril · PHONE SCREENAnduril interview questions