Regions Cut by Random Chords
Updated
Problem statement
Draw k chords in a circle. Each chord joins two points chosen uniformly at random on the edge of the circle, and all 2k points are chosen independently.
The chords cut the inside of the circle into regions. Return the expected number of regions.
Your answer is accepted if its absolute error or its relative error is at most 10^-9.
Function
expectedRegions(k: int) → doubleExamples
Example 1
k = 3return = 5.0This is the interview question. Add the chords one at a time. The first chord splits the disk into 2 regions. Each later chord adds 1 region, plus 1 more for each earlier chord it crosses, and two random chords cross with chance 1/3.
So the expected count is 1 + 1 + (1 + 1/3) + (1 + 2/3) = 5.
Example 2
k = 2return = 3.3333333333333335Two chords give 3 regions if they do not cross and 4 if they do. They cross with chance 1/3, so the answer is 3 + 1/3 = 10/3, about 3.3333.
Example 3
k = 4return = 7.0Four chords make C(4, 2) = 6 pairs, each crossing with chance 1/3, so 2 crossings are expected. The answer is 1 + 4 + 2 = 7.
Constraints
1 <= k <= 10^6
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
- Meeting of Points Moving Toward Initial SuccessorsThe Walt Disney Company · PHONE SCREENThe Walt Disney Company interview questions
- Point Inside a TriangleSambaNova Systems · PHONE SCREEN · ONSITE INTERVIEWSambaNova Systems interview questions
- Light Source Hits: Sample, Compare, and FitOpenAI · PHONE SCREENOpenAI interview questions
- Range of a Third CorrelationTower Research Capital · PHONE SCREEN
- Three Points in a Semicircle: Monte Carlo EstimateSquarepoint Capital · PHONE SCREENSquarepoint Capital interview questions
- Max Points on a LineUber · PHONE SCREENUber interview questions
- Count Axis-Aligned and Rotated SquaresGoogle · PHONE SCREENGoogle interview questions
- Union Area of Two RectanglesDocuSign · PHONE SCREENDocuSign interview questions
- Best-Fit Plane Normal from 3D PointsThe Voleon Group · PHONE SCREEN
- Intersection of Two RectanglesFigma · PHONE SCREENFigma interview questions