How should I practice Three Points in a Semicircle: Monte Carlo Estimate?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Squarepoint Capital phone screen problems in FastPrep.

Is Three Points in a Semicircle: Monte Carlo Estimate associated with Squarepoint Capital?

FastPrep tags this as a Squarepoint Capital phone screen coding practice problem when the problem catalog has that company and stage context.

Three Points in a Semicircle: Monte Carlo Estimate

Squarepoint Capital● EasyINTERNPHONE SCREEN

Problem statement

Pick three random points on a circle. How likely is it that all three fit inside one semicircle? A Monte Carlo simulation estimates this: draw many random triples and count how many fit.

Here, the random draws are already done. Each row of trials holds the angles of three points, in whole degrees. Angles wrap around the circle, so 359 and 0 are 1 degree apart. Do not generate new random points.

A semicircle is an arc of exactly 180 degrees, and it includes both of its ends. So two points that are exactly opposite each other do fit in one semicircle. Points can repeat within a trial.

Return the fraction of trials whose three points all fit inside one semicircle. Answers within 10^-9 of the exact value are accepted.

Function

estimateSemicircleProbability(trials: int[][]) → double

Examples

Example 1

trials = [[0,120,240],[10,20,30],[350,0,10]]return = 0.6666666666666666

In [0,120,240], every neighboring pair is 120 degrees apart, so no semicircle holds all three. [10,20,30] fits in a short arc. [350,0,10] also fits, because the arc from 350 to 10 crosses 0 and spans only 20 degrees. Two of the three trials fit, so the answer is 2/3.

Example 2

trials = [[0,90,180],[0,90,181]]return = 0.5

[0,90,180] fits on the arc from 0 to 180, which includes both ends. In [0,90,181], the gaps around the circle are 90, 91 and 179. Every gap is under 180, so no semicircle holds all three. One of the two trials fits, so the answer is 0.5.

Example 3

trials = [[300,100,5],[45,45,45]]return = 1.0

Angles are not sorted and can repeat. [300,100,5] fits on the arc from 300 to 100, which spans 160 degrees and crosses 0. All three points in [45,45,45] are the same point. Both trials fit, so the answer is 1.

Constraints

1 <= trials.length <= 1000
trials[i].length == 3
0 <= trials[i][j] <= 359