Random Pick with Weight

Try to solve the Random Pick with Weight problem.

We'll cover the following

Statement

You’re given an array of positive integers, weights, where weights[i] is the weight of the ithi^{th} index.

Write a function, Pick Index(), which performs weighted random selection to return an index from the weights array. The larger the value of weights[i], the heavier the weight is, and the higher the chances of its index being picked.

Suppose that the array consists of the weights [12,84,35][12, 84, 35]. In this case, the probabilities of picking the indexes will be as follows:

  • Index 0: 12/(12+84+35)=9.2%12/(12 + 84 + 35) = 9.2\%

  • Index 1: 84/(12+84+35)=64.1%84/(12 + 84 + 35) = 64.1\%

  • Index 2: 35/(12+84+35)=26.7%35/(12 + 84 + 35) = 26.7\%

Constraints:

  • 1≤1 \leq weights.length ≤104\leq 10^4

  • 1≤1 \leq weights[i] ≤105\leq 10^5

  • Pick Index() will be called at most 10410^4 times.

Note: Since we’re randomly choosing from the options, there is no guarantee that in any specific run of the program, any of the elements will be selected with the exact expected frequency.

Examples

Press + to interact
canvasAnimation-image
1 / 3

Understanding the problem

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Random Pick with Weight

1

Given this list of weights, which index has the highest probability of being picked? Note that indexes start at 0.

weights = [5, 6, 10, 8, 9, 7]

A)

0

B)

3

C)

4

D)

2

Question 1 of 30 attempted

Figure it out!

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Try it yourself

Since a good randomized picking function shouldn’t result in elements being picked with precisely the same frequencies as predicted mathematically, we print the frequency with which each element is picked as a result of calling the Pick Index() function 900900 times for each list. Next to the actual frequency, we print the expected frequency. The better our function is, the more closely it matches the expected frequencies over several runs.

You are expected to implement a class whose constructor receives the list of weights and has a method Pick Index() that picks an index at random, taking into account the weight of each index.

import java.util.*;
class RandomPickWithWeight {
    
    public RandomPickWithWeight(int[] weights) {
        // Write your code here
        // The integer's weight array is passed to the constructor
        
    }
    public int pickIndex() {
        // Replace this placeholder return statement with your code
        return 0;
    }
    public static int sumW(int[] arr) {
        int sum = 0;
        // Loop through the array to calculate sum of elements  
        for (int i = 0; i < arr.length; i++) {
            sum = sum + arr[i];
        }
        return sum;
    }
    
    static float round(float var) {
        float value = (int)(var * 100 + .5);
        return (float) value / 100;
    }
    public static void main(String args[]) {
        int counter = 900;
        int[] weights1 = {1, 2, 3, 4, 5};
        int[] weights2 = {1, 12, 23, 34, 45, 56, 67, 78, 89, 90};
        int[] weights3 = {10, 20, 30, 40, 50};
        int[] weights4 = {1, 10, 23, 32, 41, 56, 62, 75, 87, 90};
        int[] weights5 = {12, 20, 35, 42, 55};
        int[] weights6 = {10, 10, 10, 10, 10};
        int[] weights7 = {10, 10, 20, 20, 20, 30};
        int[] weights8 = {1, 2, 3};
        int[] weights9 = {10, 20, 30, 40};
        int[] weights10 = {5, 10, 15, 20, 25, 30};
        int[][] weights = {weights1, weights2, weights3, weights4, weights5,
                weights6, weights7, weights8, weights9, weights10};
        HashMap < Integer, Integer > dict = new HashMap < > ();
        for (int i = 0; i < weights.length; i++) {
            System.out.println((i + 1) + ".\tInput: " + Arrays.toString(weights[i]) + ", pickIndex() called " + counter + " times" + "\n");
            for (int l = 0; l < weights[i].length; l++) {
                dict.put(l, 0);
            }
            for (int j = 0; j < counter; j++) {
                RandomPickWithWeight sol = new RandomPickWithWeight(weights[i]);
                int index = sol.pickIndex();
                dict.put(index, dict.get(index) + 1);
            }
            System.out.println(new String(new char[100]).replace('\0', '-'));
            System.out.println("Indexes\t" + "|" + "\tWeights\t   " + "|" + "\t   Occurences  \t" + "|" + "\tFrequency\t" + "|" + "\tExpected Frequency");
            System.out.println(new String(new char[100]).replace('\0', '-'));
            for (Map.Entry < Integer, Integer > entry: dict.entrySet()) {
                System.out.println(entry.getKey() + "\t|\t" + weights[i][entry.getKey()] + "\t   | \t" + dict.get(entry.getKey()) + "\t\t|\t" + round(dict.get(entry.getKey()) / (float) counter) * 100 + "%" + "\t\t|\t" + round(weights[i][entry.getKey()] / (float) sumW(weights[i]) * 100) + "%");
            }
            dict.clear();
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Random Pick with Weight