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

Reservoir Sampling with Recorded Draws

StackAdapt logoStackAdapt● MediumFULLTIMEONSITE INTERVIEW
QuestionFunctionExamplesConstraints

Problem statement

Source note: The interview report identifies this task and its central operation. This practice version states the deterministic interface, boundary behavior, and ordering rules needed for consistent execution while preserving the reported capability.

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 StackAdapt problems

  • Build a Tree from Preorder and Inorder TraversalsONSITE INTERVIEW · Seen Sep 2026
  • Maximum Bananas Delivered by a CamelONSITE INTERVIEW · Seen Sep 2026
  • Running Medians and PercentilesPHONE SCREEN · Seen Aug 2026
All StackAdapt interview questionsSee StackAdapt hiring insights
Saved
class Solution {
    public int[] reservoirSample(int[] values, int k, int[] draws) {
        // Write your code here.
    }
}
Checking account…