Skip to main content

528. Random Pick with Weight

mediumAsked at DoorDash

Given an array of weights, implement pickIndex() that returns an index in proportion to its weight. DoorDash uses this for backend rounds — weighted random sampling shows up in load balancing, driver assignment, and A/B test bucketing.

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

Source citations

Public interview reports confirming this problem appears in DoorDash loops.

  • Glassdoor (2026-Q1)— DoorDash SWE onsite reports cite Random Pick with Weight for backend infrastructure rounds.
  • Blind (2025-12)— DoorDash SDE2 reports note the prefix-sum + binary-search pattern as the actual interview signal.

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","pickIndex"]
[[[1]],[]]
Output
[null,0]

Explanation: Only one option, must pick index 0.

Example 2

Input
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output
[null,1,1,1,1,0]

Explanation: Each call returns a random index proportionally weighted.

Approaches

1. Prefix-sum + binary search (optimal)

Build a prefix-sum array. Pick a random target in [1, total]. Binary search for the smallest prefix that >= target — that's the answer index.

Time
O(n) ctor / O(log n) per pick
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 target = Math.floor(Math.random() * this.total) + 1;
    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: DoorDash's preferred answer. Binary search reduces per-pick cost from O(n) to O(log n). Note the +1 on target so the range maps [1, total] to indices.

2. Linear scan (naive)

Pick a random target. Walk the prefix sums linearly until the cumulative sum exceeds target.

Time
O(n) ctor / O(n) per pick
Space
O(n)
class SolutionLinear {
  constructor(w) {
    this.prefix = [];
    let sum = 0;
    for (const x of w) { sum += x; this.prefix.push(sum); }
    this.total = sum;
  }
  pickIndex() {
    const target = Math.floor(Math.random() * this.total) + 1;
    for (let i = 0; i < this.prefix.length; i++) {
      if (this.prefix[i] >= target) return i;
    }
    return this.prefix.length - 1;
  }
}

Tradeoff: Simpler to write. With 10^4 calls and n = 10^4, total work = 10^8 — borderline. DoorDash interviewers want the binary search.

DoorDash-specific tips

DoorDash interviewers grade specifically on the BINARY SEARCH. State 'pick a random target in [1, total], binary-search the prefix array' BEFORE coding. The +1 / lower-bound details often trip candidates — practice the comparison direction.

Common mistakes

  • Random in [0, total) instead of [1, total] — breaks the half-open mapping when prefix sums start at 0.
  • Using upper_bound semantics when lower_bound is correct (or vice versa).
  • Recomputing the prefix array on each pickIndex call — must be in the constructor.

Follow-up questions

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

  • Random Pick Index (LC 398) — reservoir sampling.
  • Implement Rand10() using Rand7() (LC 470) — uniform reduction.
  • Random Pick with Blacklist (LC 710) — reduce to weighted picks.

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 target = floor(random * total) + 1?

It maps the uniform random [0, 1) into integers [1, total]. Then prefix-sum binary search finds the smallest prefix >= target, which corresponds exactly to the right weighted index.

Lower-bound or upper-bound?

Lower-bound (first >= target). The exit lo = hi when prefix[lo] is the first prefix that crosses the random target.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →