Reservoir Sampling with Recorded Draws
Updated
Problem statement
Simulate size-k reservoir sampling over the integer array values. Begin with the first k values in reservoir slots 0 through k - 1.
For every later array index i, draws[i - k] records an integer drawn from the inclusive range [0, i]. If that recorded draw is smaller than k, replace that reservoir slot with values[i]. Otherwise leave the reservoir unchanged.
Return the final reservoir in slot order.
Function
reservoirSample(values: int[], k: int, draws: int[]) → int[]Examples
Example 1
values = [10,20,30,40,50]k = 2draws = [0,2,1]return = [30,50]Index 2 replaces slot 0 with 30. The draw for index 3 is not smaller than 2, so 40 is skipped. Index 4 then replaces slot 1 with 50.
Example 2
values = [1,2,3]k = 3draws = []return = [1,2,3]The reservoir already contains the complete stream, so no recorded draws are needed.
Example 3
values = [5,6,7,8]k = 1draws = [1,0,3]return = [7]Value 6 is skipped, value 7 replaces slot 0, and value 8 is skipped.
Constraints
1 <= values.length <= 2000001 <= k <= values.lengthdraws.length = values.length - k- For every
j,0 <= draws[j] <= k + j. -1000000000 <= values[i] <= 1000000000
More Google Phone Screen questions
- Best Stock Trade with Buy and Sell DaysPHONE SCREEN · Seen Nov 2026
- Word Chain Jumps in a GridPHONE SCREEN · Seen Nov 2026
- Dice-Walk Winning ProbabilityPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Apartment Housemate PreferencesPHONE SCREEN · Seen Nov 2026
- Price at Query TimestampsPHONE SCREEN · Seen Nov 2026
- Course Schedule Cycle DetectionPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Logger Rate Limiter with Every-Arrival HistoryPHONE SCREEN · Seen Nov 2026
- Minimum Total Layover WaitPHONE SCREEN · Seen Nov 2026
- Reach a Destination Through Scheduled FlightsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
Similar questions at other companies
- Constant-Time Weighted Pick with an Alias TableEtched · PHONE SCREEN
- Evenly Schedule Vehicle InspectionsAmazon · PHONE SCREEN
- Implement Cross-Entropy LossOpenAI · PHONE SCREENOpenAI interview questions
- Cumulative No-Intercept Regression BetasCitadel · PHONE SCREENCitadel interview questions
- Add Signed Character ArraysByteDance · PHONE SCREENByteDance interview questions
- Automation Pipeline, Part 2: Stage WorkersPlaid · PHONE SCREENPlaid interview questions
- Attention With Absolute Index BiasNVIDIA · PHONE SCREENNVIDIA interview questions
- K-Means Delivery ZonesDoorDash · PHONE SCREEN · ONSITE INTERVIEWDoorDash interview questions
- Token Bucket Request DecisionsDatadog · PHONE SCREENDatadog interview questions
- Gradient Descent for Linear RegressionMicrosoft · PHONE SCREENMicrosoft interview questions