Random Pick with Weight


#1

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.

Note:

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

Example 1:

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

Example 2:

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

Explanation of Input Syntax:

The input is two lists: the subroutines called and their arguments. Solution's constructor has one argument, the array w. pickIndex has no arguments. Arguments are always wrapped with a list, even if there aren't any.


#2

The algorithm below does the following:

  • Generate an array with value at index being the total number of elements until that index.
  • Generate a random value between 0 and the total at last index minus one.
  • Do a binary search on the array from step 1 to find the upper bound for the random value, return it. That would be the index with weighted average considered.
type Solution struct {
    sum []int
}


func Constructor(w []int) Solution {
    for i := 1; i < len(w); i++ {
        w[i] += w[i - 1]
    }
    
    return Solution{w}
}


func (this *Solution) PickIndex() int {
    size := len(this.sum)
    
    r := rand.Intn(this.sum[size-1])
    s, e := 0, size-1
    for s<e{
        m := (s+e)/ 2
        if this.sum[m]<=r{
            s = m+1
        } else {
            e = m
        }
    }
    
    return s
}


/**
 * Your Solution object will be instantiated and called as such:
 * obj := Constructor(w);
 * param_1 := obj.PickIndex();
 */

#3

similar logic in Java.

class Solution {

    int[] weights;
    int total;
    java.util.Random rand = new java.util.Random();
    public Solution(int[] w) {
        int sum = 0;
        this.weights = new int[w.length];
        for(int i=0;i<w.length;i++){
            sum += w[i];
            weights[i] = sum;
        }
        System.out.println("total is - "+sum);
        this.total = sum;
    }
    
    public int pickIndex() {
        int val = rand.nextInt(total);
        int l=0, r=weights.length-1;
        while(l<r){
            int m = (l+r)/2;
            if(weights[m] > val){
                r = m;
            }else{
                l = m+1;
            }
        }
       
        return l;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(w);
 * int param_1 = obj.pickIndex();
 */