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:

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:

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

---