Random Pick with Weight Interview Question for Google

You are given a 0-indexed array of positive integers w where w[i] describes the weight of the i<sup>th</sup> index.

You need to implement the function pickIndex(), which randomly picks an index in the range [0, w.length - 1] (inclusive) and returns it. The probability of picking an index i is w[i] / sum(w).

For example, if w = [1, 3], the probability of picking index 0 is 1 / (1 + 3) = 0.25 (i.e., 25%), and the probability of picking index 1 is 3 / (1 + 3) = 0.75 (i.e., 75%).

Example 1:

Input ["Solution","pickIndex"] [[[1]],[]] Output [null,0]

Explanation Solution solution = new Solution([1]); solution.pickIndex(); // return 0. The only option is to return 0 since there is only one element in w.

Example 2:

Input ["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"] [[[1,3]],[],[],[],[],[]] Output [null,1,1,1,1,0]

Explanation Solution solution = new Solution([1, 3]); solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4. solution.pickIndex(); // return 1 solution.pickIndex(); // return 1 solution.pickIndex(); // return 1 solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4.

Since this is a randomization problem, multiple answers are allowed.

Constraints:

1 <= w.length <= 10^4
1 <= w[i] <= 10^5
pickIndex will be called at most 10^4 times.

# Weighted Random Index Picker

This problem requires us to implement a `pickIndex()` function that randomly selects an index from an array, where each index has a weight associated with it. The probability of selecting an index is proportional to its weight. This can be solved efficiently using prefix sums and binary search.

## 1. Brute Force Solution (Conceptual)

A brute-force approach would involve creating a large array where each index `i` from the input `w` is repeated `w[i]` times. Then, randomly select an index from this large array. However, this approach is highly inefficient in terms of space, especially when weights are large.

## 2. Optimal Solution: Prefix Sums and Binary Search

The optimal approach involves calculating prefix sums of the weights and then using binary search to efficiently find the index corresponding to a randomly generated number.

### Algorithm:

1.  **Calculate Prefix Sums:** Create a new array `prefix_sums` where `prefix_sums[i]` is the sum of weights from `w[0]` to `w[i]`. This allows us to map a range of numbers to each index.
2.  **Generate Random Number:** Generate a random integer between 1 and the total sum of weights (i.e., `prefix_sums[-1]`).
3.  **Binary Search:** Use binary search on the `prefix_sums` array to find the index where the generated random number would fall. This index is the randomly selected index.

### Python Code:

```python
import random

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)
        
        low, high = 0, len(self.prefix_sums) - 1
        while low <= high:
            mid = (low + high) // 2
            if self.prefix_sums[mid] < target:
                low = mid + 1
            else:
                high = mid - 1
        
        return low

# Example Usage
# w = [1, 3]
# solution = Solution(w)
# print(solution.pickIndex())
# print(solution.pickIndex())
# print(solution.pickIndex())

Explanation:

The __init__ method calculates the prefix sums and stores them in self.prefix_sums.
The pickIndex method generates a random integer between 1 and the total sum of weights.
Binary search is then used to find the smallest index i such that prefix_sums[i] is greater than or equal to the generated random number. This index is the selected index.

3. Big(O) Run-time Analysis

Initialization (__init__): O(n), where n is the length of the input array w. We iterate through the array once to calculate the prefix sums.
pickIndex(): O(log n), where n is the length of the input array w. Binary search is used to find the index.

4. Big(O) Space Usage Analysis

Initialization (__init__): O(n), where n is the length of the input array w. We store the prefix sums in an array of the same size.
pickIndex(): O(1). Binary search only uses a constant amount of extra space.

5. Edge Cases

Empty Input Array: If the input array w is empty, the program should raise an exception since we cannot pick an index.
All Weights Are Zero: If all weights are zero, the program cannot pick an index based on the specified probabilities. Handle this situation by raising an exception or returning a default value.
Single Element Array: If the array has only one element, the pickIndex() method should always return 0.

Edge Cases Code:

import random

class Solution:
    def __init__(self, w):
        if not w:
            raise ValueError("Input array cannot be empty")
        
        total_weight = sum(w)
        if total_weight == 0:
            raise ValueError("Weights cannot all be zero")

        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):
        if len(self.prefix_sums) == 1:
            return 0

        target = random.randint(1, self.total_sum)
        
        low, high = 0, len(self.prefix_sums) - 1
        while low <= high:
            mid = (low + high) // 2
            if self.prefix_sums[mid] < target:
                low = mid + 1
            else:
                high = mid - 1
        
        return low

Conclusion

The optimal solution uses prefix sums and binary search to efficiently pick a random index based on its weight, adhering to the problem's constraints. Error checking for empty inputs and zero weights improves robustness.