Katkat
Back

Sample index from probability distribution

LinkedInMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This question tests the ability to implement a weighted random sampling algorithm efficiently using prefix sums and binary search to achieve sub-linear query time.

Problem Statement

Given an array of positive integers weights, where weights[i] represents the weight of the index i, implement a class WeightedSampler that selects an index randomly based on these weights. The probability of selecting index i is weights[i] / sum(weights).

Implement the following methods:

  • __init__(self, weights: List[int]): Initializes the object with the input weights.
  • pick_index(self) -> int: Returns a random index following the defined probability distribution.

Constraints

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

Examples

Example 1:

# Input: weights = [1, 3]
# Object initialization: sampler = WeightedSampler([1, 3])
# Expected behavior: pick_index() returns 0 with 25% probability, 1 with 75% probability.

Edge Cases

  • Single element in weights array.
  • Very large weight values (ensure prefix sum does not overflow if using a language with fixed-width integers).

Hints

Hint 1

Transform the weights into a prefix sum array (e.g., [1, 3] becomes [1, 4]) to represent ranges of values.

Hint 2

Generate a random integer `r` between 1 and the total sum of weights, then locate the smallest index `i` such that `prefix_sum[i] >= r`.

Hint 3

Use binary search (specifically `bisect_left` in Python) on the prefix sum array to find the target index in O(log n) time.

Follow-up questions

  • How would you modify your solution if the weights change dynamically (i.e., you need to update a weight at a specific index)?
  • What is the space complexity of your solution, and can you optimize it if the weights array is extremely sparse?
  • How does the time complexity change if you use a Reservoir Sampling approach instead of prefix sums?