Skip to main content

528. Random Pick With Weight

mediumAsked at Uber

Given a positive-integer weights array, implement pickIndex() that returns i with probability proportional to w[i]. Uber asks this to test prefix sum + binary search and the uniform-on-[0,total) framing.

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

Source citations

Public interview reports confirming this problem appears in Uber loops.

  • Glassdoor (2026-Q1)— Uber dispatch / experimentation team onsite reports list this as a recurring favorite.
  • Blind (2025-12)— Recurring in Uber backend interview reports — fits naturally with A/B test routing.

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.

Example 2

Input
Solution([1,3,5]); pickIndex() x4
Output
Indices distributed by 1:3:5 over many calls.

Explanation: Over many calls, ratios approach the weight ratios.

Approaches

1. Linear scan per pickIndex

Pick a random r in [0, total). Walk the array accumulating; return when running 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 pivoting to binary search.

2. Prefix sum + binary search (optimal)

Precompute prefix sums. Each pick is a binary search for the smallest prefix > 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 monotonically increasing by construction, so binary search applies directly.

Uber-specific tips

Uber wants the uniform-random framing said 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 is the difference between 'works' and 'works and demonstrates understanding'.

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 binary search (search for smallest prefix > r, not >=).
  • Recomputing prefix sums per pickIndex call instead of in the constructor.

Follow-up questions

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

  • What if weights could change online? (Fenwick tree gives O(log n) updates and picks.)
  • Reservoir sampling — different problem but related randomness concept.
  • 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.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →