528. Random Pick with Weight
mediumAsked at PinterestPinterest's ads-pacing and ranking infrastructure samples from weighted distributions. Random Pick with Weight asks you to build a sampler where each index i is picked with probability proportional to w[i]. The interviewer wants the prefix-sum + binary-search pattern.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Pinterest loops.
- Glassdoor (2026-Q1)— Pinterest ads / recsys onsite reports cite Random Pick with Weight as the data-structures + math round.
- LeetCode Pinterest tag (2026-Q1)— On the Pinterest company-tagged problem list; obvious analog to ads-pacing.
Problem
You are given a 0-indexed array of positive integers w where w[i] describes the weight of the ith index. You need to implement the function pickIndex(), which randomly picks an index in the range [0, w.length - 1] and returns it. The probability of picking the ith index is w[i] / sum(w).
Constraints
1 <= w.length <= 10^41 <= w[i] <= 10^5pickIndex will be called at most 10^4 times.
Examples
Example 1
Solution s = new Solution([1, 3]); s.pickIndex(); s.pickIndex(); s.pickIndex(); s.pickIndex(); s.pickIndex();[null,1,1,1,1,0]Explanation: Index 1 has weight 3, index 0 has weight 1. Over many calls, index 1 should appear 3x as often as index 0.
Approaches
1. Build full expanded array (brute force)
Construct an array where each index i appears w[i] times. pickIndex returns a uniform random element.
- Time
- O(sum(w)) preprocess, O(1) pick
- Space
- O(sum(w))
class SolutionBrute {
constructor(w) {
this.flat = [];
for (let i = 0; i < w.length; i++) {
for (let j = 0; j < w[i]; j++) this.flat.push(i);
}
}
pickIndex() {
return this.flat[Math.floor(Math.random() * this.flat.length)];
}
}Tradeoff: Constant-time pick but blows memory: sum(w) can be 10^4 * 10^5 = 10^9, infeasible. Mention it to anchor, then move.
2. Prefix sums + binary search (optimal)
Precompute prefix sums of weights. pickIndex generates uniform random in [1, total], then binary-searches for the first prefix-sum >= target.
- Time
- O(n) preprocess, O(log n) pick
- Space
- O(n)
class Solution {
constructor(w) {
this.prefix = new Array(w.length);
let sum = 0;
for (let i = 0; i < w.length; i++) {
sum += w[i];
this.prefix[i] = sum;
}
this.total = sum;
}
pickIndex() {
const target = Math.random() * this.total; // [0, total)
// Binary search for first prefix >= target
let lo = 0, hi = this.prefix.length - 1;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (this.prefix[mid] <= target) lo = mid + 1;
else hi = mid;
}
return lo;
}
}Tradeoff: O(log n) per pick at O(n) memory — the canonical answer. The binary search predicate ('first prefix strictly greater than target') is the tricky part — narrate it.
3. Alias method (optimal O(1) pick)
Preprocess into alias tables in O(n). Each pick: roll a random bucket, then a coin flip between bucket and its alias. O(1) per pick.
- Time
- O(n) preprocess, O(1) pick
- Space
- O(n)
// Alias method — Walker's algorithm. Not typically required at Pinterest
// but volunteer it as 'I know there's an O(1) preprocess-heavy version'.
class SolutionAlias {
constructor(w) {
const n = w.length;
const sum = w.reduce((a, b) => a + b, 0);
const p = w.map((wi) => (wi * n) / sum);
this.prob = new Array(n);
this.alias = new Array(n);
const small = [], large = [];
for (let i = 0; i < n; i++) (p[i] < 1 ? small : large).push(i);
while (small.length && large.length) {
const s = small.pop(), l = large.pop();
this.prob[s] = p[s];
this.alias[s] = l;
p[l] = p[l] - (1 - p[s]);
if (p[l] < 1) small.push(l); else large.push(l);
}
while (large.length) this.prob[large.pop()] = 1;
while (small.length) this.prob[small.pop()] = 1;
this.n = n;
}
pickIndex() {
const i = Math.floor(Math.random() * this.n);
return Math.random() < this.prob[i] ? i : this.alias[i];
}
}Tradeoff: O(1) per pick is genuinely faster at scale, but at LeetCode's 10^4 calls the binary-search version wins on constant factors. Mention alias method as 'I know this can be O(1) per pick with Walker's alias' without implementing it under time pressure.
Pinterest-specific tips
Pinterest interviewers love this problem because it maps directly to ads-pacing (ads with higher bid weights should appear proportionally more often). Lead with prefix-sum + binary search. Volunteer the alias-method aside as 'there's an O(1) preprocess-heavy version called Walker's alias' — that tells them you've read further than LeetCode. Don't implement alias unless asked.
Common mistakes
- Generating Math.random() * total then using <= in the binary search — boundary collision between adjacent prefix sums.
- Forgetting that Math.random() returns [0, 1) — multiply by total to get [0, total), not [1, total].
- Using lo <= hi termination — for find-first-greater patterns, lo < hi is the safer template.
- Linear scan instead of binary search — O(n) per pick blows time at 10^4 calls.
Follow-up questions
An interviewer at Pinterest may pivot to one of these next:
- Update weights after construction (heap / segment tree).
- Stream of items with weights — reservoir-style weighted sampling (algorithm A-Res).
- Pick K distinct indices without replacement, weighted.
- Implement alias method (Walker's algorithm) — sketch on whiteboard.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why does Pinterest care about weighted sampling specifically?
Ads-pacing controllers select ads to serve next based on bid * remaining budget weights; recommendation rankers sample candidates for exploration. Both are weighted-random-pick at scale.
Is the alias method actually faster in practice?
At extremely high pick rates yes — but the preprocessing constant factor is higher than O(n). Use the binary-search version unless you have a hot loop calling pickIndex millions of times.
Free learning resources
Curated free links for this problem.