528. Random Pick with Weight
mediumAsked at DoorDashGiven 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 Sam K., 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^41 <= w[i] <= 10^5pickIndex will be called at most 10^4 times.
Examples
Example 1
["Solution","pickIndex"]
[[[1]],[]][null,0]Explanation: Only one option, must pick index 0.
Example 2
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]][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.
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.