Design weighted random index picker

Q: Design weighted random index picker

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Design weighted random index picker

Overview

Comments (0)