Practice/Meta/Leetcode 528. Random Pick with Weight

Leetcode 528. Random Pick with Weight

CodingMust

Problem

Design a data structure that supports weighted random selection. You will be given an array of positive integers representing weights, where each weight corresponds to an element at that index. Implement a class that:

1. Takes the weights array in its constructor
2. Provides a pickIndex() method that returns a random index, where the probability of returning index i is proportional to weights[i]

The probability of picking index i should be exactly weights[i] / sum(weights).

For example, if weights are [1, 3], index 0 should be picked 25% of the time and index 1 should be picked 75% of the time.

Requirements

1. Implement a constructor that accepts an array of positive integer weights
2. Implement a pickIndex() method that returns an index based on weighted probability
3. The solution should be efficient enough to handle many calls to pickIndex()
4. All weights are guaranteed to be positive integers

Constraints

• 1 <= weights.length <= 10000
• 1 <= weights[i] <= 100000
• pickIndex() will be called at most 10000 times
• The returned index must be valid (between 0 and weights.length - 1)

Examples

Example 1:

` Input: weights = [1, 3] Operations: pickIndex(), pickIndex(), pickIndex(), pickIndex(), pickIndex() Output: [1, 1, 0, 1, 1] (one possible output) Explanation:

• Total weight = 4
• Index 0 has probability 1/4 = 25%
• Index 1 has probability 3/4 = 75% Over many calls, index 1 should appear roughly 3 times more often than index 0 `

Example 2:

` Input: weights = [1, 2, 3, 4] Operations: pickIndex() called 10 times Output: [3, 2, 1, 3, 3, 2, 3, 1, 3, 2] (one possible output) Explanation:

• Total weight = 10
• Index 0: 10% probability
• Index 1: 20% probability
• Index 2: 30% probability
• Index 3: 40% probability Index 3 should appear most frequently, followed by 2, then 1, then 0 `

Example 3:

Input: weights = [5] Operations: pickIndex(), pickIndex(), pickIndex() Output: [0, 0, 0] Explanation: Only one index exists, so it's always returned