Implement weighted random index picker

Q: Implement weighted random index picker

This question evaluates understanding of weighted random sampling, probabilistic reasoning, preprocessing and dynamic update strategies, numerical stability, and time/space complexity analysis.

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 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.

Implement weighted random index picker

Overview

Comments (0)