Quick Overview

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.

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.

Overview: 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

  1. Build a prefix-sum array of weights and binary search for the first prefix strictly greater than r.
  2. Use 64-bit or arbitrary-precision integers; avoid floating point to prevent precision loss with huge weights.
  3. Zero-weight items are never selected; using bisect-right over prefix sums naturally skips them.
  4. For many repeated picks, precompute the prefix once or consider the alias method for O(1) sampling.

Loading coding console...

Show the approach

Approach

Compute the cumulative sums prefix[i] = sum(weights[0..i]). Given r in [0, total-1], the desired index i is the smallest index with prefix[i] > r. Using binary search (bisect_right) over the monotonic prefix array yields O(log n) lookup. This approach handles arbitrarily large weights without precision loss by staying in integer arithmetic. Zero-weight entries create repeated prefix values; bisect_right skips them automatically. For repeated queries, precompute the prefix once; alternatively, the alias method offers O(1) sampling at the cost of O(n) preprocessing and O(n) extra memory.

Time complexity:
O(n + log n) per call (O(n) to build prefix, O(log n) to search)
Space complexity:
O(n) extra space for prefix sums