528. Random Pick with Weight

Q: 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.

Q: 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.

mediumAsked at Pinterest

Pinterest'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 Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-19

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^4
1 <= w[i] <= 10^5
pickIndex will be called at most 10^4 times.

Examples

Example 1

Input

Solution s = new Solution([1, 3]); s.pickIndex(); s.pickIndex(); s.pickIndex(); s.pickIndex(); s.pickIndex();

Output

[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.

Output

Press Run or Cmd+Enter to execute

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.

Practice these live with InterviewChamp.AI

Drill Random Pick with Weight and other Pinterest interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →