Katkat
Back

Implement weighted random sampling with preprocessing

MetaMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to optimize weighted random selection using binary search on prefix sums, balancing preprocessing time against query latency.

Weighted Random Sampling

You are given an array of positive integers weights, where weights[i] represents the weight of the element at index i. Implement a class WeightedSampler that efficiently picks an index at random, where the probability of picking index i is proportional to weights[i] / sum(weights).

Requirements

  • Implement the __init__(self, weights: List[int]) method to preprocess the data.
  • Implement the pick_index(self) -> int method to return an index based on the weights.

Constraints

  • 1 <= weights.length <= 10^5
  • 1 <= weights[i] <= 10^5
  • pick_index will be called at most 10^4 times.

Examples

# Example 1:
sampler = WeightedSampler([1, 3])
sampler.pick_index() # Returns 1 with 75% probability, 0 with 25% probability.

# Example 2:
sampler = WeightedSampler([1, 2, 3])
# Possible outputs: 0, 1, or 2 based on cumulative distribution.

Edge Cases

  • What if all weights are equal?
  • What if the sum of weights exceeds the capacity of a standard 32-bit integer?
  • How does your solution behave if the weights are updated dynamically (though not required here)?

Hints

Hint 1

Consider calculating the cumulative sum (prefix sums) of the weights array during initialization.

Hint 2

Generate a random number between 0 and the total sum, then use binary search to find the index where the cumulative sum first exceeds that random value.

Hint 3

Ensure your search algorithm handles the case where the random value is exactly equal to a prefix sum boundary correctly.

Follow-up questions

  • How would you modify this solution if the weights were updated frequently in real-time?
  • How does the time complexity change if you use the Alias Method instead of binary search on prefix sums?
  • What are the numerical precision challenges if weights are provided as floats instead of integers?