Random Pick with Weight
Given an array w of positive integers where w[i] describes the weight of index i, implement pickIndex() which randomly picks an index proportional to its weight.
For testing: given weights and a large number of picks, output the percentage each index was picked (rounded to nearest integer). The output should be close to the weight distribution.
Instead of random testing, output the cumulative weights used for selection as space-separated integers.
Example:
1,3
1 4
- The input array
wis given as[1, 3], representing the weights of the two indices. - To calculate the cumulative weights, we start with the first weight
1and add the second weight3to get the cumulative weight at index 1: 1+3=4. - The cumulative weights are then
[1, 4], where1is the cumulative weight up to index 0 and4is the cumulative weight up to index 1. - The final output is the cumulative weights as space-separated integers:
1 4.
Constraints:
- 1 <= len(w) <= 10^4
- 1 <= w[i] <= 10^5
Background Knowledge
The problem "Random Pick with Weight" involves implementing a function that randomly selects an index from a given array based on the weights associated with each index. This is a classic problem in the realm of probability theory and random sampling. To approach this problem, one needs to understand the concept of weighted random selection, where the probability of selecting an index is proportional to its weight. The weights are typically used to create a probability distribution, which assigns a probability to each index.
In the context of this problem, the probability distribution is created by normalizing the weights, i.e., dividing each weight by the sum of all weights. This ensures that the probabilities add up to 1, which is a fundamental property of a probability distribution. The cumulative distribution function (CDF) is also an essential concept here, as it represents the probability that a random variable takes on a value less than or equal to a given value. In this case, the CDF can be used to determine the index to be selected based on a random number generated between 0 and 1.
The problem requires the implementation of a function that can efficiently generate a random index based on the given weights. This involves designing a data structure that can store the weights and their corresponding cumulative probabilities, allowing for efficient lookup and selection of the index. Hash maps or prefix sum arrays can be useful data structures for this purpose, as they enable fast lookup and calculation of cumulative probabilities.
Algorithm/Approach
The general approach to solving this problem involves the following algorithm pattern:
- Calculate the cumulative weights or probabilities for each index.
- Generate a random number between 0 and 1.
- Use the random number to select an index based on the cumulative probabilities. This approach is commonly used in random sampling and weighted random selection problems.
Step-by-Step Strategy
To implement the solution, follow these steps:
- Calculate the sum of all weights in the array.
- Create a prefix sum array or a hash map to store the cumulative weights.
- Generate a random number between 0 and 1.
- Iterate through the prefix sum array or hash map to find the index where the random number falls within the range of the cumulative weight.
- Return the selected index.
Common Pitfalls
When implementing the solution, watch out for the following:
- Ensure that the cumulative weights are calculated correctly and stored in a suitable data structure.
- Verify that the random number generation is uniform and within the correct range.
- Be cautious of integer overflow when calculating the sum of weights and cumulative probabilities.
Time & Space Complexity
The expected time complexity for this problem is O(n), where n is the number of elements in the array, as we need to iterate through the array to calculate the cumulative weights. The space complexity is also O(n), as we need to store the cumulative weights in a separate data structure. However, the time complexity for the pickIndex() function can be O(log n) or O(1) depending on the data structure used to store the cumulative weights.