Random Pick with Weight

Random Pick with Weight

What is this problem about?

The Random Pick with Weight problem asks you to design a class that randomly picks an index with probability proportional to its weight. If weights=[3,1], index 0 should be picked 75% of the time and index 1 25% of the time. This coding problem uses prefix sums with binary search for weighted random sampling. The array, math, binary search, randomized, and prefix sum interview pattern is the core.

Why is this asked in interviews?

Apple, Uber, Microsoft, Meta, Amazon, Google, Bloomberg, and Adobe ask this because weighted random sampling is fundamental to machine learning (sampling proportional to importance), load balancing, A/B testing, and recommendation systems. The prefix sum + binary search approach is clean and efficient.

Algorithmic pattern used

Prefix sums + binary search. Build prefix sum array from weights. Total = prefix[-1]. For each pick: generate random number r in [1, total]. Binary search in prefix array for the leftmost position where prefix[i] >= r. Return that index.

Example explanation

weights=[3,1,2]. Prefix=[3,4,6]. Total=6.

• Pick r=2: bisect_left([3,4,6], 2)=0. Return 0 (range [1,3] maps to index 0).
• Pick r=4: bisect_left([3,4,6], 4)=1. Return 1 (range [4,4] maps to index 1).
• Pick r=5: bisect_left([3,4,6], 5)=2. Return 2 (range [5,6] maps to index 2). Probability proportional to weight ✓.

Common mistakes candidates make

• Using r in [0, total-1] instead of [1, total] (shifts distribution).
• Using bisect_right instead of bisect_left (different boundary behavior).
• Not normalizing weights (prefix sums handle this implicitly).
• Off-by-one in random number generation.

Interview preparation tip

Random Pick with Weight is the canonical weighted sampling problem. The prefix sum creates "weight intervals" on [1, total]; binary search finds which interval a random number falls into. Practice: "weighted random shuffle," "probabilistic load balancer," "roulette wheel selection." The prefix sum + bisect_left pattern is the standard implementation — memorize it.