Problem · Array
Reservoir Sampling with Recorded Draws
Learn this problem● Medium
GoogleFULLTIMEPHONE SCREEN
See Google hiring insightsGoogleFULLTIMEPHONE SCREENProblem 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