LeetCode Problem: Random Topics

LeetCode Problem: Random Topics

1. Random Pick with Weight

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. For example:

i 0 1
w[i] 1 3

As shown, the index 0 has a weight 1, and the index 1 has a weight 3.

Here is the code to solve the problem:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import java.util.Random;

public class RandomPickWithWeight {
Random random;
int[] sum;

public RandomPickWithWeight(int[] w) {
this.random = new Random();
this.sum = w.clone();
for (int i = 1; i < sum.length; i++) {
sum[i] += sum[i - 1];
}

}

public int pickIndex() {
int pick = random.nextInt(sum[sum.length - 1]) + 1;

int left = 0;
int right = sum.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (sum[mid] < pick) {
left = mid + 1;
} else if (sum[mid] > pick) {
right = mid - 1;
} else {

return mid;
}
}

return left;
}

public static void main(String[] args) {
/**
* index: [0,1]
* weight:[1,3]
*/
RandomPickWithWeight randomPick = new RandomPickWithWeight(new int[]{1, 3});

int pick_1 = randomPick.pickIndex();
int pick_2 = randomPick.pickIndex();
int pick_3 = randomPick.pickIndex();
System.out.println(String.format("[%d, %d, %d]", pick_1, pick_2, pick_3));
}
}

The idea of the above code is shown in the following video: https://www.youtube.com/watch?v=_pnWZe44rdo


2. Implement Rand10() Using Rand7()

Given a function rand7 which generates a uniform random integer in the range 1 to 7, write a function rand10 which generates a uniform random integer in the range 1 to 10.

Here is the code to solve the problem:

1
2
3
4
5
6
7
public int rand10() {
int random = 41;
while(random > 40) {
random = 7*(rand7() - 1) + rand7();
}
return random % 10 + 1;
}

The idea of the above code is shown in the following video: https://www.youtube.com/watch?v=mK0JeED2D8k