Statement

You’re given an array of positive integers, weights, where weights[i] is the weight of the $i^{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]$ . In this case, the probabilities of picking the indexes will be as follows:

Index 0: $12/(12 + 84 + 35) = 9.2\%$
Index 1: $84/(12 + 84 + 35) = 64.1\%$
Index 2: $35/(12 + 84 + 35) = 26.7\%$

Constraints:

$1 \leq$ weights.length $\leq 10^4$
$1 \leq$ weights[i] $\leq 10^5$
Pick Index() will be called at most $10^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

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 $900$ times for each array. 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 array of weights and has a method Pick Index() that picks an index at random, taking into account the weight of each index.

package main
import (
	"fmt"
	"strings"
	// "math/rand"
	"math"
	"text/tabwriter"
	"os"
)
/**
 * Your RandomPickWithWeight object will be instantiated and called as such:
 * obj := Constructor(w);
 * param_1 := obj.PickIndex();
 */
type RandomPickWithWeight struct {
	
}
func Constructor(weights []int) RandomPickWithWeight {
	// Write your code here
    // The weights array, consisting of integers, is passed to the constructor
	return RandomPickWithWeight{
	}
}
// Method to pick an index based on the weights
func (r *RandomPickWithWeight) PickIndex() int {
	
	// Replace this placeholder return statement with your code
	return 0
}
// Driver code
func main() {
	counter := 900
	weights := [][]int {
		{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 := make(map[int]int)
	for index, value := range weights {
		obj := Constructor(value)
		fmt.Printf("%d.\tInput: %s, pickIndex() called %d times\n\n", index + 1, strings.Replace(fmt.Sprint(value), " ", ", ", -1), counter)
		for i, _ := range value {
			dict[i] = 0
		}
		for j := 0; j < counter; j++ {
			sol := obj.PickIndex()
			dict[sol] += 1
		}
		sum := 0
		for _, v := range value {
			sum += v
		}
		fmt.Printf("%s\n", strings.Repeat("-", 72))
		w := tabwriter.NewWriter(os.Stdout, 10, 0, 0, ' ', tabwriter.Debug)
		fmt.Fprintln(w, "Indexes", "\t", "Weights", "\t", "Occurences", "\t", "Frequency", "\t", "Expected Frequency")
		fmt.Fprintln(w, strings.Repeat("-", 10), "\t", strings.Repeat("-", 10), "\t", strings.Repeat("-", 10), "\t", strings.Repeat("-", 10), "\t", strings.Repeat("-", 20))
		i := 0
		for _, v := range dict {
			if len(value) <= i {
				break
			}
			frequency := math.Round((float64(v)/float64(counter)) * 10000.0) / 100.0
			eFrequency := math.Round((float64(value[i])/float64(sum)) * 10000.0) / 100.0
			fmt.Fprintln(w, i, "\t", weights[index][i], "\t", v, "\t", frequency, "%", "\t", eFrequency, "%")
			i++
		}
		w.Flush()
		fmt.Printf("\n%s\n\n", strings.Repeat("-", 100))
	}
}

Random Pick with Weight

Two Pointers

Modified Binary Search

Conclusion

Random Pick with Weight

Statement

Examples

Understanding the problem

Figure it out!

Try it yourself