FastPrepReservoir Sampling with Recorded Draws
Problems/Reservoir Sampling with Recorded Draws

Reservoir Sampling with Recorded Draws

Google logoGoogle● MediumFULLTIMEPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: This was a PhD intern interview. This problem is rebuilt. The report only keeps that the exercise was an applied sampling program. The reservoir model and the interface with recorded draws are our own choices. Our version is about 20% the same as the reported question.

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 <= 200000
  • 1 <= k <= values.length
  • draws.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

Interview reports that mention this question

  • Google SWE and PhD Intern Coding: 14 Experiences (Part 3 of 3)

Google interview experiences

  • Google L4 SWE Phone Screen: 1 Experience
  • Google ML Engineering Manager Onsite: 1 Experience
  • Google Experienced SWE First Round and Onsite: 1 Experience
  • Google AI Coding Interview and AI OA: 2 Experiences
  • Google SWE Intern Interview Results Timeline: 13 Experiences
All Google interview questionsSee Google hiring insights
Saved
class Solution {
    public int[] reservoirSample(int[] values, int k, int[] draws) {
        // Write your code here.
    }
}
Checking account…