How should I practice Reservoir Sampling with Supplied Random Draws?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Microsoft onsite interview problems in FastPrep.

Is Reservoir Sampling with Supplied Random Draws associated with Microsoft?

FastPrep tags this as a Microsoft onsite interview coding practice problem when the problem catalog has that company and stage context.

Reservoir Sampling with Supplied Random Draws

Microsoft● MediumFULLTIMEONSITE INTERVIEW

Learn

Problem statement

Given a finite stream, retain exactly k samples using reservoir sampling.

Initialize the reservoir with the first k items. For arrival index i from k onward, draws[i-k] is a supplied uniform draw from 0 through i, inclusive. If the draw is less than k, replace that reservoir slot; otherwise leave the reservoir unchanged. Return reservoir slots in slot order.

Function

reservoirSample(stream: int[], k: int, draws: int[]) → int[]

Examples

Example 1

stream = [10,20,30,40,50]k = 3draws = [1,4]return = [10,40,30]

The draw for 40 replaces slot 1; the draw for 50 is outside the reservoir and causes no replacement.

Example 2

stream = [7,8]k = 2draws = []return = [7,8]

When the stream length equals k, every item remains in the reservoir.

Constraints

1 <= k <= stream.length <= 100000
draws.length = stream.length - k
For 0 <= j < draws.length, 0 <= draws[j] <= k + j
-10^9 <= stream[i] <= 10^9