Random Pick with Weight

You are given an array of positive integers, weights, where weights[i] is the weight assigned to index i.

Random Pick with Weight

Problem Statement

You are given an array of positive integers, weights, where weights[i] is the weight assigned to index i.

Write a function, pickIndex(), which performs a weighted random selection. It should return an index from the weights array. The larger the value of weights[i], the heavier that index is, and the higher the chance it gets picked.

For example, suppose the array is [12, 84, 35]. The chances of picking each index would be:

• Index 0: 12 / (12 + 84 + 35) = 9.2%
• Index 1: 84 / (12 + 84 + 35) = 64.1%
• Index 2: 35 / (12 + 84 + 35) = 26.7%

Constraints

• 1 ≤ weights.length ≤ 10⁴
• 1 ≤ weights[i] ≤ 10⁵
• pickIndex() will be called at most 10⁴ times.

Note: Since this is a random selection process, there's no guarantee that any single run of the program will match the exact expected percentages perfectly. Over many calls, though, the results should trend toward these probabilities.

Solution

The main idea: if we call pickIndex() many times (say, 1000 times), the results should roughly follow the weight-based probabilities. For example, an index with weight 5 should show up roughly proportional to that weight compared to the others.

Steps

• We first build a running sum array. Each entry stores the total sum so far, adding up all the weights up to that index. This creates a set of "ranges" — for example, weights [12, 84, 35] become running sums [12, 96, 131].
• To pick an index, we generate a random number between 1 and the total sum of all weights.
• We then use binary search to find the first running sum that is greater than or equal to this random number. The index of that running sum is our answer.
• This works because each index "owns" a range of numbers proportional to its weight. A heavier weight owns a bigger range, so it's more likely that our random number lands inside it.

Code

class RandomPickWithWeight {
    constructor(weights) {
        this.runningSums = [];
        let runningSum = 0;

        for (let w of weights) {
            runningSum += w;
            this.runningSums.push(runningSum);
        }
        this.totalSum = runningSum;
    }

    // Method to pick an index based on the weights
    pickIndex() {
        let target = Math.floor(Math.random() * this.totalSum) + 1;
        let low = 0;
        let high = this.runningSums.length;

        while (low < high) {
            let mid = Math.floor(low + (high - low) / 2);
            if (target > this.runningSums[mid]) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}