Search⌘ K
AI Features

Random Pick with Weight

Explore how to implement a weighted random selection function that picks an index based on given weights. Understand the problem constraints, probability calculations, and practice coding this solution in Go, leveraging modified binary search for efficient selection.

Statement

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

Implement the function PickIndex(), which performs weighted random selection to return an index from the w array. The larger the value of w[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 w.length ≤104\leq 10^4

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

  • PickIndex() 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

Implement your solution in the following coding playground.

Go
usercode > Solution.go
package main
type Solution struct {
}
func Constructor(w []int) Solution {
return Solution{}
}
func (s *Solution) PickIndex() int {
return -1
}
Random Pick with Weight