Median of Uniform Draws in an Interval
Updated
Problem statement
You draw n numbers. Each number is chosen uniformly at random from the interval [0, length], and the draws are independent.
The count n is odd, so after sorting the draws there is exactly one middle number. That middle number is the median. For example, the median of 2.5, 0.4, 1.7 is 1.7.
Return the probability that the median lies in the interval [a, b]. Your answer is accepted if its absolute error or its relative error is at most 10^-9.
Function
medianInIntervalProbability(n: int, length: int, a: int, b: int) → doubleExamples
Example 1
n = 3length = 3a = 1b = 2return = 0.48148148148148145This is the interview case. The median of three numbers is the second smallest. It is at most x exactly when at least two of the three numbers are at most x.
Each number is at most 2 with probability 2/3. So the median is at most 2 with probability 3 × (2/3)^2 × (1/3) + (2/3)^3 = 12/27 + 8/27 = 20/27.
Each number is at most 1 with probability 1/3. So the median is at most 1 with probability 3 × (1/3)^2 × (2/3) + (1/3)^3 = 6/27 + 1/27 = 7/27.
The answer is 20/27 - 7/27 = 13/27, about 0.4815.
Example 2
n = 1length = 10a = 2b = 5return = 0.3With one number, the median is that number. A uniform number on [0, 10] lands in [2, 5] with probability 3/10 = 0.3.
Example 3
n = 5length = 4a = 1b = 3return = 0.79296875The median of five numbers is the third smallest, so it is at most x when at least three numbers are at most x. Each number is at most 3 with probability 3/4.
So the median is at most 3 with probability 10 × (3/4)^3 × (1/4)^2 + 5 × (3/4)^4 × (1/4) + (3/4)^5 = (270 + 405 + 243) / 1024 = 918/1024.
The range is symmetric around 2, so the median is at most 1 with the same probability that it is at least 3: 1 - 918/1024 = 106/1024. The answer is 918/1024 - 106/1024 = 812/1024 = 203/256, which is 0.79296875.
Constraints
1 <= n <= 999nis odd.1 <= length <= 10^90 <= a <= b <= length
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
- One Number Is the Average of the Other TwoPHONE SCREEN · Seen Jun 2025
- Which Coin Pattern Shows Up FirstPHONE SCREEN · Seen May 2025
- Random Points Inside One ArcPHONE SCREEN · Seen Jan 2025
Similar questions at other companies
- Count Array DerangementsInMobi · PHONE SCREENInMobi interview questions
- Biased Coin: Probability of Exactly h HeadsAkuna Capital · PHONE SCREENAkuna Capital interview questions
- Probability of Consecutive HeadsSquarepoint Capital · PHONE SCREENSquarepoint Capital interview questions
- Election District Budget Allocation AnalysisIMC Trading · PHONE SCREENIMC Trading interview questions
- Count Clean Attendance LogsRippling · PHONE SCREENRippling interview questions
- Count Staircases with Strictly Increasing StepseBay · ONSITE INTERVIEWeBay interview questions
- Count Shipment SchedulesMorgan Stanley · OAMorgan Stanley interview questions
- Find Encrypted NumberAmazon · OA
- Valid PasswordsMathWorks · OAMathWorks interview questions
- Coloring HousesSnowflake · OASnowflake interview questions