Implement weighted random index picker
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Design a class WeightedPicker that is initialized with an array of positive integer weights w and supports pick() that returns an index i with probability proportional to w[i]. Optimize for up to 10^7 picks after preprocessing 10^5 weights. Discuss preprocessing choices (prefix sums vs. alias method), random number generation, numerical stability, and time/space complexity. Extension: support addWeight(i, delta) and pick() with sublinear-time updates and queries.
Quick Answer: This question evaluates understanding of weighted random sampling, probabilistic reasoning, preprocessing and dynamic update strategies, numerical stability, and time/space complexity analysis.