Amazon

Microsoft

2020-06-05

## 528. Random Pick with Weight

### Question:

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"]
[[],[]]
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.

### Solution:

Store the array into a cumulative way that each index represents the sum till the current position. The using binary search to find the insert position.

Using Java built-in binary search.

``````class Solution {
int[] cum;
Random rand;
int max;
public Solution(int[] w) {
cum = new int[w.length];
int total = 0;
for(int i = 0; i < w.length; i++) {
total += w[i];
cum[i] = total;
}
rand = new Random();
max = cum[w.length - 1];
}

public int pickIndex() {
int currpick = rand.nextInt(max) + 1;
int result = Arrays.binarySearch(cum, currpick);
if (result < 0) return -result - 1;
return result;
}
}

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

Using binary search with two pointers:

Binary Search Template:

``````class Solution {
int[] cum;
Random rand;
int max;
public Solution(int[] w) {
cum = new int[w.length];
int total = 0;
for(int i = 0; i < w.length; i++) {
total += w[i];
cum[i] = total;
}
rand = new Random();
max = cum[w.length - 1];
}

public int pickIndex() {
int currpick = rand.nextInt(max) + 1;
int left = 0;
int right = cum.length - 1;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (cum[mid] == currpick ) {
return mid;
} else if (cum[mid] > currpick ) {
right = mid;
} else {
left = mid;
}
}

if (cum[left] >= currpick) {
return left;
} else {
return right;
}
}
}

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

Or:

``````class Solution {
int[] cum;
Random rand;
int max;
public Solution(int[] w) {
cum = new int[w.length];
int total = 0;
for(int i = 0; i < w.length; i++) {
total += w[i];
cum[i] = total;
}
rand = new Random();
max = cum[w.length - 1];
}

public int pickIndex() {
int currpick = rand.nextInt(max) + 1;
int left = 0;
int right = cum.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (cum[mid] == currpick ) {
return mid;
} else if (cum[mid] > currpick ) {
right = mid - 1;
} else {
left = mid + 1;
}
}

return left;
}
}

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