How should I practice Categorical Sampling with Recorded Draws?

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

Is Categorical Sampling with Recorded Draws associated with Microsoft?

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

Categorical Sampling with Recorded Draws

Microsoft● MediumFULLTIMEPHONE SCREEN

Learn

Problem statement

For this exercise, a categorical distribution is represented by nonnegative integer weights. Category i has probability weights[i] / W, where W is the positive total weight.

Assign consecutive ticket ranges to categories in input order. Category i owns [sum(weights[0..i-1]), sum(weights[0..i])). A zero-weight category owns no ticket.

Each element of draws is an already-recorded uniform integer ticket from 0 through W-1. Return the category index containing each ticket, preserving draw order. Do not generate extra random numbers, sort the categories or alter their weights. An empty draw batch returns an empty array.

If the ticket is uniform, each category is selected with exactly its specified probability because its range contains exactly its weight in tickets.

Function

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

Examples

Example 1

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

Category0 owns tickets0 and1, category1 owns2 through4, and category2 owns5.

Example 2

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

Zero-weight categories own no ticket; ticket4 belongs to category3. Draw order is preserved.

Example 3

weights = [3]draws = []return = []

An empty sequence of recorded draws produces no samples.

Constraints

1 <= weights.length <= 100000; 0 <= draws.length <= 100000.
0 <= weights[i] <= 1000000 and 1 <= W <= 1000000000.
Every draw satisfies 0 <= draws[q] < W.
Category indices are zero-based.