Expected Rank of the Hired Candidate
Updated
Problem statement
You are hiring for one job and will interview n candidates one at a time. The candidates have ranks 1 to n, where rank 1 is the best and no two candidates share a rank. They arrive in a uniformly random order, so every order is equally likely.
After each interview you must hire the candidate or turn them away for good, and you can only compare a candidate with those you have already seen. You follow this rule:
- Turn away the first
cutoffcandidates, whoever they are. - After that, hire the first candidate who is better than every candidate interviewed before them.
- If nobody has been hired when the last candidate arrives, hire the last candidate.
Return the expected rank of the candidate you hire. Answers within 10-6 of the correct value, or within that fraction of it when the answer is above 1, are accepted.
Function
secretaryExpectedRank(n: int, cutoff: int) → doubleExamples
Example 1
n = 3cutoff = 1return = 1.6666666666666667Write each arrival order as the ranks in the order they arrive. The first candidate is always passed over. In [2,1,3], [3,1,2] and [3,2,1] the second candidate beats the first and is hired (ranks 1, 1, 2). In [2,3,1] the third candidate beats both earlier ones and is hired (rank 1). In [1,3,2] and [1,2,3] nobody qualifies, so the last candidate is hired (ranks 2, 3). The average is 10 / 6 = 5/3.
Example 2
n = 3cutoff = 0return = 2.0With no one passed over, the first candidate already beats everyone seen so far and is hired. Their rank is equally likely to be 1, 2 or 3, so the answer is 2.
Example 3
n = 4cutoff = 2return = 2.0833333333333335The third candidate is hired when they beat the first two, which happens with chance 1/3; they are then the best of three random ranks out of four, with average rank 5/4. Otherwise the fourth candidate is hired, with average rank 5/2. The answer is 1/3 * 5/4 + 2/3 * 5/2 = 25/12.
Constraints
1 <= n <= 1050 <= cutoff < n
More Jane Street Phone Screen questions
- Maximum-Scoring Consecutive Tree LevelsPHONE SCREEN · Seen Nov 2026
- Tree Selection and VisibilityPHONE SCREEN · Seen Nov 2026
- Load/Store Arithmetic InterpreterPHONE SCREEN · Seen Oct 2026
- Instrument Stack Language JumpsPHONE SCREEN · Seen Oct 2026
- Run a Stack Language InterpreterPHONE SCREEN · Seen Oct 2026
- Positive-Integer Expression EvaluationPHONE SCREEN · Seen Oct 2026
- Add Two Integers Given as StringsPHONE SCREEN · Seen Sep 2026
- Angle Between Clock HandsPHONE SCREEN · Seen Jul 2026
- Route Length From Two CyclistsPHONE SCREEN · Seen Jul 2026
- Sort TradesPHONE SCREEN · ONSITE INTERVIEW · Seen Jul 2026
Similar questions at other companies
- Best Single Reroll for Five DiceSusquehanna International Group (SIG) · PHONE SCREENSusquehanna International Group (SIG) interview questions
- Count Array DerangementsInMobi · PHONE SCREENInMobi interview questions
- Biased Coin: Probability of Exactly h HeadsAkuna Capital · PHONE SCREENAkuna Capital interview questions
- Revolver: Will the Next Shot Fire?Tower Research Capital · PHONE SCREEN
- Probability of Consecutive HeadsSquarepoint Capital · PHONE SCREENSquarepoint Capital interview questions
- Expected Fake-Name CollisionsMercor · PHONE SCREENMercor interview questions
- Election District Budget Allocation AnalysisIMC Trading · PHONE SCREENIMC Trading interview questions
- Count Clean Attendance LogsRippling · PHONE SCREENRippling interview questions
- Extra Coin Win ProbabilityMicrosoft · PHONE SCREENMicrosoft interview questions
- Count Staircases with Strictly Increasing StepseBay · ONSITE INTERVIEWeBay interview questions