Skip to main content

528. Random Pick With Weight

mediumAsked at Meta

Given a positive-integer weights array, implement pickIndex() that returns i with probability proportional to w[i]. Meta asks this to test whether you reach for prefix sums + binary search and can articulate the uniform-random-on-[0, total) framing.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Meta loops.

  • Glassdoor (2026-Q1)— Meta E4 onsite reports cite this as a recurring 'Meta favorite' design problem.
  • Blind (2025-10)— Recurring Meta interview problem.

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] (inclusive) and returns it. The probability of picking an index i 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([1,3]); pickIndex()
Output
[null,1]

Explanation: pickIndex returns 0 with prob 1/4 and 1 with prob 3/4.

Approaches

1. Linear scan per pickIndex

Pick a random number r in [0, total), walk the array adding weights until cumulative sum > r.

Time
O(n) per pick, O(n) construction
Space
O(1)
class SolutionLinear {
  constructor(w) {
    this.w = w;
    this.total = w.reduce((s, x) => s + x, 0);
  }
  pickIndex() {
    const r = Math.random() * this.total;
    let cum = 0;
    for (let i = 0; i < this.w.length; i++) {
      cum += this.w[i];
      if (r < cum) return i;
    }
    return this.w.length - 1;
  }
}

Tradeoff: Acceptable for small n but O(n) per call. Mention before jumping to binary search.

2. Prefix sum + binary search (optimal)

Precompute prefix sums. Each pick is a binary search for the smallest prefix sum > random.

Time
O(log n) per pick, O(n) construction
Space
O(n)
class Solution {
  constructor(w) {
    this.prefix = [];
    let sum = 0;
    for (const x of w) {
      sum += x;
      this.prefix.push(sum);
    }
    this.total = sum;
  }
  pickIndex() {
    const r = Math.random() * this.total;
    let lo = 0, hi = this.prefix.length - 1;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (this.prefix[mid] <= r) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  }
}

Tradeoff: O(log n) per pick. The prefix sum array is sorted (monotonically increasing) by construction, which makes it binary-searchable.

Meta-specific tips

Meta interviewers want the uniform-random framing articulated. State out loud: 'Each weight w[i] corresponds to an interval of length w[i] on the number line [0, total). I pick a uniform-random point in [0, total) and find which interval it lands in via binary search.' That framing earns the bar; jumping to code without it loses signal.

Common mistakes

  • Treating Math.random() as inclusive of 1 — it's [0, 1) so r is in [0, total) by construction.
  • Off-by-one in the binary search (should find smallest prefix > r, not >=).
  • Storing the original weights without prefix sums (wastes O(log n) opportunity).

Follow-up questions

An interviewer at Meta may pivot to one of these next:

  • What if the weights could change online (insertions)?
  • Reservoir sampling — different problem but related randomness concept.
  • What if you needed to pick k indices without replacement?

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 binary search and not direct indexing?

Direct indexing would require an array of length total — which can be 10^9 (n * max weight). Prefix sums give O(n) space; binary search gives O(log n) per query.

What if total overflows?

In JavaScript, numbers are doubles so they handle values up to ~2^53. For larger sums, use BigInt — same algorithm, different arithmetic.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →