You’re given an array of positive integers, w, where w[i] describes the weight of the ith index. You need to perform weighted random selection to return an index from the w array. The larger the value of w[i], the heavier the weight is. Hence, the higher the chances of its index being picked.

1-random-weighted-pick.js

class RandomPickWithWeight {
  constructor(w) {
    // w is an array of numbers, each number is a weight of the index where it's stored
    // so our task is to return a random index with respect to weights,
    // so the most "heavy" index is the most probable to be returned
    this.weights = w
    // build an array of rolling sums
    this.sums = []
    for (let i = 0; i < w.length; ++i) {
      const prevSum = this.sums[i - 1] || 0
      this.sums.push(prevSum + w[i])
    }
  }

  getRandomInt() {
    return Math.floor(Math.random() * this.sums[this.sums.length - 1])
  }

  pickIndex() {
    const rand = this.getRandomInt()
    let start = 0;
    let end = this.sums.length - 1

    while (start < end) {
      const mid = Math.floor((start + end) / 2)
      // we are looking for the first sum that is greater than rand
      // we found one that is greater, but were not sure if it's the first
      // so we shift end to be this position (mid) instead of mid-1 so we dont lose it
      if (this.sums[mid] > rand) {
        end = mid
      } else {
        // this sum is less than or equal to rand, so we discard it, shifting left side to mid + 1
        start = mid + 1
      }
    }

    return start
  }
}

2-README.md