How Good Are the Estimates of n?
Updated
Problem statement
The numbers 1, 2, ..., n are in a hat. You draw m different numbers, so every set of m numbers is equally likely. Let M be the largest number drawn and A the average of the numbers drawn. Someone who does not know n estimates it in one of three ways:
estimator = 0: the largest number,M.estimator = 1: twice the average minus one,2A - 1.estimator = 2: the corrected largest number,(m + 1) / m × M - 1.
Return the mean squared error of the chosen estimate: the expected value of (estimate - n)^2.
Your answer is accepted if its absolute error or its relative error is at most 10^-9.
Function
estimatorMse(n: int, m: int, estimator: int) → doubleExamples
Example 1
n = 10m = 3estimator = 0return = 5.95Three numbers from 1 to 10, estimated by the largest one. On average the largest is 3 × 11 / 4 = 33/4, so it is 7/4 too low (the bias). Its variance is 231/80. The mean squared error is 231/80 + (7/4)^2 = 231/80 + 245/80 = 119/20 = 5.95.
Example 2
n = 10m = 3estimator = 1return = 8.555555555555555The average of the draws is 11/2 on average, so 2A - 1 has no bias. One draw has variance (10^2 - 1) / 12 = 33/4, and the average of 3 different draws has variance 33/4 / 3 × (10 - 3) / (10 - 1) = 77/36. So 2A - 1 has mean squared error 4 × 77/36 = 77/9, about 8.556.
Example 3
n = 10m = 3estimator = 2return = 5.133333333333334The corrected estimate 4/3 × M - 1 has no bias, and its variance is (4/3)^2 × 231/80 = 77/15, about 5.133. It beats both other estimators here.
Constraints
1 <= m <= n <= 10^60 <= estimator <= 2
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
- Integers With Multiple Sum of Two CubesCharta Health · PHONE SCREEN · ONSITE INTERVIEWCharta Health interview questions
- Dice-Walk Winning ProbabilityGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Logistic Regression with Gradient DescentYahoo · PHONE SCREENYahoo interview questions
- Evaluate an Arithmetic Expression Written in WordsBrex · PHONE SCREEN
- Constant-Time Weighted Pick with an Alias TableEtched · PHONE SCREEN
- Integer to English Words in USD and INR StylesVeeam · PHONE SCREEN
- Adaptive Calibration ErrorOpenAI · PHONE SCREENOpenAI interview questions
- Sum of Smallest Non-DivisorsThe D.E. Shaw Group · PHONE SCREENThe D.E. Shaw Group interview questions
- Square Root FunctionCitadel · PHONE SCREENCitadel interview questions
- Reorderable Task Scheduler With CooldownWaymo · PHONE SCREENWaymo interview questions