Here's the complete solution:
class Solution
prefix := array of size n
total := 0
function __init__(weights)
n := length of weights
for i from 0 to n - 1
total := total + weights[i]
prefix[i] := total
function pickIndex()
// Pick random number in [1, total]
r := random integer in range [1, total]
// Binary search for smallest i where prefix[i] >= r
left := 0
right := length of prefix - 1
while left < right
mid := left + (right - left) / 2
if prefix[mid] < r then
left := mid + 1
else
right := mid
return left
Time: for initialization (building prefix sum), per pick (binary search). Space: for the prefix sum array.