How should I practice Random Pick with Weight Using Recorded Draws?

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

Is Random Pick with Weight Using Recorded Draws associated with Google?

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

Random Pick with Weight Using Recorded Draws

Google● MediumFULLTIMENEW GRADPHONE SCREENONSITE INTERVIEW

Learn

Problem statement

You are given an array weights of positive integers and a sequence draws of recorded uniform random tickets. The weight at index i determines how many tickets select that index.

Let total be the sum of all weights. Tickets are integers from 0 through total - 1. Assign the first weights[0] tickets to index 0, the next weights[1] tickets to index 1, and so on. For each ticket, return its selected index. Keep the answers in the same order as draws.

The weights do not change between draws. If a ticket is sampled uniformly from this range, index i is selected with probability weights[i] / total. The input supplies each sampled ticket so the expected result is reproducible.

Function

pickIndices(weights: int[], draws: int[]) → int[]

Examples

Example 1

weights = [1,3]draws = [0,1,2,3]return = [0,1,1,1]

Ticket 0 belongs to index 0; tickets 1, 2, and 3 belong to index 1.

Example 2

weights = [2,1,2]draws = [0,1,2,3,4]return = [0,0,1,2,2]

The half-open ticket intervals are [0,2), [2,3), and [3,5).

Example 3

weights = [5]draws = [4,0,2]return = [0,0,0]

Every valid ticket chooses the only index.

Constraints

1 <= weights.length <= 2000.
1 <= weights[i] <= 10^5.
1 <= draws.length <= 2000.
For every ticket t in draws, 0 <= t < total, where total is the sum of all weights.
total <= 2 * 10^8, so cumulative weights fit in a signed 32-bit integer.