algoadvance

You are given an array w of positive integers, where w[i] describes the weight of index i.

Write a function pickIndex which randomly picks an index in proportion to its weight.

Clarifying Questions

1. Are the weights guaranteed to be positive integers?
   • Yes, each weight is a positive integer.
2. Can weights be zero?
   • No, weights are positive integers as specified.
3. Are we going to have multiple pickIndex calls after initializing with the array w?
   • Yes, the function pickIndex may be called multiple times.

Strategy

The problem can be broken down into two main parts:

1. Preprocessing: Before we start picking indices, we will preprocess the weights to accumulate the probabilities.
2. Random Picking: For each pick, we will use the accumulated weights to determine which index to pick in proportion to its weight.

Preprocessing

We’ll calculate a prefix sum of the weights. This will allow us to use binary search to quickly determine the correct index for a given pick.

Random Picking

To pick an index, we:

1. Generate a random number between 1 and the total sum of the weights.
2. Use binary search to find the target index in the prefix sum array.

Steps:

1. Initialization:
   • Create a prefix sum array from the input weights.
2. Picking an Index:
   • Generate a random integer in the range from 1 to the total sum of weights.
   • Use binary search (bisect in Python) to find the first prefix sum that is greater than or equal to the random number.

Time Complexity

• Preprocessing: O(N), where N is the number of weights.
• Picking: O(log N) due to the binary search.

Code

import random
import bisect

class Solution:
    def __init__(self, w):
        self.prefix_sums = []
        self.total_sum = 0
        
        for weight in w:
            self.total_sum += weight
            self.prefix_sums.append(self.total_sum)

    def pickIndex(self):
        target = random.randint(1, self.total_sum)
        index = bisect.bisect_left(self.prefix_sums, target)
        return index

Explanation

• Initialization (__init__ method):
  • self.prefix_sums stores the accumulated sums of weights. For example, if w = [1, 3, 2], the prefix_sums will be [1, 4, 6].
  • self.total_sum is the total of all weights; here it would be 6.
• Pick an Index (pickIndex method):
  • Generate a random integer between 1 and self.total_sum. This corresponds to randomly selecting a point on the cumulative weight scale.
  • Use bisect.bisect_left to find the first index in the prefix_sums where the cumulative sum is greater than or equal to the random number.

This approach ensures that indices with larger weights have a proportionally higher chance of being picked, as required by the problem statement.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?