Katkat
Back

Weighted Random Sampling by Index

TubiMachine Learning Engineer · Technical Screen
MediumMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

This question tests a candidate's ability to implement weighted random sampling using prefix sums and binary search, evaluating practical algorithm design for probability distributions. It assesses proficiency in translating mathematical probability constraints into efficient data structures, a skill commonly probed in machine learning engineering roles where non-uniform sampling is fundamental to model training and inference pipelines.

Weighted Random Sampling by Index

You are given an array of positive integer weights weights, where weights[i] is the weight assigned to index i. Implement a sampler that, on each call, returns a random index i with probability proportional to weights[i].

Concretely, build a class WeightedSampler:

  • The constructor WeightedSampler(weights) receives the array of weights and may do O(n) preprocessing.
  • The method pick_index() returns a single random integer in the range [0, n - 1]. The probability of returning index i must equal weights[i] / sum(weights).

For example, with weights = [1, 3], pick_index() should return 0 about 25% of the time and 1 about 75% of the time. With weights = [1, 2, 3, 4], index 3 should be returned about 40% of the time.

Aim for each pick_index() call to run in O(log n) time after O(n) construction.

Constraints & Assumptions

  • 1 <= n <= 10^5, where n = len(weights).
  • 1 <= weights[i] <= 10^5.
  • The total sum of weights fits in a 64-bit integer.
  • pick_index() may be called up to 10^4 times.
  • You have access to a uniform random source over [0, 1) (or uniform integers over a range).

Output / Expected Behavior

  • The constructor performs preprocessing only and returns nothing.
  • Each pick_index() call returns one integer index. Correctness is judged statistically: over many calls, the empirical frequency of each index must converge to weights[i] / sum(weights).