Design weighted random index picker
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Take-home Project
Design and implement a data structure that, given an array of positive integer weights w[0..n−1], supports pick() that returns index i with probability proportional to w[i]. Optimize for many pick() calls after a one-time initialization. Specify the API, prove correctness, and analyze time and space. Follow-ups: support point updates to weights; handle large totals without precision loss; compare prefix-sum binary search with the alias method; design tests to detect sampling bias.
Quick Answer: This question evaluates algorithm design and data structure selection for weighted random sampling, along with probability reasoning, correctness proof, time and space complexity analysis, and numerical stability considerations.