Katkat
Back

Implement weighted random choice

PinterestData Scientist · Technical Screen
MediumData ScientistTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to implement efficient weighted random selection, specifically focusing on cumulative distribution functions and binary search to achieve optimal query performance.

Problem Statement

Given a list of positive integers representing weights for a set of items, implement a class WeightedSampler that selects an item index randomly, where the probability of selecting an index i is proportional to weights[i] / sum(weights).

Requirements

Implement the following methods:

  1. __init__(self, weights: List[int]): Initializes the sampler with a list of weights.
  2. pick_index(self) -> int: Returns a random index based on the weight distribution.

Complexity

  • The __init__ method should be efficient enough to handle large weight arrays.
  • The pick_index method should be optimized for repeated calls, ideally better than O(N) where N is the number of weights.

Examples

# Weights: [1, 3]
# Index 0 has 25% chance, Index 1 has 75% chance.
sampler = WeightedSampler([1, 3])
sampler.pick_index() # Could return 0 or 1

Constraints

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

Edge Cases

  • A list containing a single weight.
  • Weights with large values that might overflow if not handled carefully (though Python handles large integers automatically).

Hints

Hint 1

Transform the weights into a cumulative distribution array (prefix sums) where each index stores the sum of all previous weights plus its own.

Hint 2

Generate a random number between 0 and the total sum, then determine which range in your prefix sum array this number falls into.

Hint 3

Use binary search (such as bisect_left) on the prefix sum array to find the correct index in O(log N) time.

Follow-up questions

  • How would you modify your implementation if the weights needed to be updated dynamically after initialization?
  • If the sum of weights is extremely large (exceeding standard integer limits in other languages), how would you handle the probability distribution?
  • What is the space complexity of your solution, and can you optimize it if the weights are sparse?