How to Design a Proportional Randomized Sampler?
Company: Pinterest
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
##### Scenario
Randomized promotion engine must pick an item proportional to its score, but scores have no upper bound.
##### Question
Design a sampler pick() that returns an item with probability proportional to its (possibly very large) weight. Discuss memory and precision trade-offs when weights exceed 32-bit limits.
##### Hints
Prefix-sum array + binary search or alias table; rescale or use long/double for huge weights.
Quick Answer: This question evaluates proficiency in randomized algorithms and probabilistic sampling, with emphasis on numerical precision, large-weight handling, and memory-versus-accuracy trade-offs. Commonly asked in Coding & Algorithms interviews for data-science roles, it assesses practical application ability grounded in conceptual understanding of numerical stability and relevant data-structure choices.
You are given an array weights of n non-negative integers representing item weights, and an integer r such that 0 <= r < sum(weights). Implement weighted_pick(weights, r) that returns the smallest index i for which r < weights[0] + weights[1] + ... + weights[i]. This deterministically maps a uniform integer draw r in [0, sum(weights) - 1] to the item chosen proportionally to its weight. At least one weight must be positive. Use integer arithmetic to handle weights larger than 32-bit.
Constraints
- 1 <= n <= 2e5
- weights[i] are integers with 0 <= weights[i]
- At least one weights[i] > 0
- 0 <= r < sum(weights)
- sum(weights) <= 1e20 (weights may exceed 32-bit limits)
- Use integer arithmetic; avoid floating point precision loss
Hints
- Build a prefix-sum array of weights and binary search for the first prefix strictly greater than r.
- Use 64-bit or arbitrary-precision integers; avoid floating point to prevent precision loss with huge weights.
- Zero-weight items are never selected; using bisect-right over prefix sums naturally skips them.
- For many repeated picks, precompute the prefix once or consider the alias method for O(1) sampling.