Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in Python

Random Pick with Weight

Explore how to perform weighted random selection by implementing a Pick Index function that returns array indices proportional to their weights. Understand the use of modified binary search to efficiently handle probability distributions and constraints, enhancing your coding interview preparation.

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

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

1 / 3

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.

Sequence - Vertical
Drag and drop the cards to rearrange them in the correct sequence.
1
2
3
4

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.

Python 3.10.4
import random
class RandomPickWithWeight:
    def __init__(self, weights):
        # Write your code here
        # The weights array, consisting of integers, is passed to the constructor
        pass
    def pick_index(self):
        # Replace this placeholder return statement with your code
        return 0
# Driver code
def main():
    counter = 900
    weights = [[1, 2, 3, 4, 5],
                [1, 12, 23, 34, 45, 56, 67, 78, 89, 90],
                [10, 20, 30, 40, 50],
                [1, 10, 23, 32, 41, 56, 62, 75, 87, 90],
                [12, 20, 35, 42, 55],
                [10, 10, 10, 10, 10],
                [10, 10, 20, 20, 20, 30],
                [1, 2, 3],
                [10, 20, 30, 40],
                [5, 10, 15, 20, 25, 30]]
    dict = {}
    for i in range(len(weights)):
        print(i + 1, ".\tList of weights: ", weights[i], ", pick_index() called ", counter, " times", "\n", sep="")
        [dict.setdefault(l, 0) for l in range(len(weights[i]))]
        sol = RandomPickWithWeight(weights[i])
        for j in range(counter):
            index = sol.pick_index()
            dict[index] += 1
        print("-"*105)
        print("\t{:<10}{:<5}{:<10}{:<5}{:<15}{:<5}{:<20}{:<5}{:<15}".format( \
            "Indexes", "|", "Weights", "|", "Occurences", "|", "Actual Frequency", "|", "Expected Frequency"))
        print("-"*105)
        for key, value in dict.items():
            print("\t{:<10}{:<5}{:<10}{:<5}{:<15}{:<5}{:<20}{:<5}{:<15}".format(key, "|", weights[i][key], "|", value, "|", \
                str(round((value/counter)*100, 2)) + "%", "|", str(round(weights[i][key]/sum(weights[i])*100, 2))+"%"))
        dict = {}
        print("\n", "-"*105, "\n", sep="")
if __name__ == '__main__':
    main()
Random Pick with Weight