Please use Laptop/Desktop or any other large screen for the Mock Interview Session.

Random pick with weight and vertical order traversal of a binary tree



YouTube Video Thumbnail
Link

Watch above sample mock interview video to see how it works.
Login and Buy Premium to Start the Interview



Random Index Picker Based on Weights

Random Index Picker Based on Weights

Problem Statement

You are given an array weights of positive integers where each weights[i] represents the weight of index i. Implement a function chooseIndex that randomly selects an index from the array such that the probability of picking each index is proportional to its weight.

Constraints

  • 1 ≤ weights.length ≤ 8000
  • 1 ≤ weights[i] ≤ 5 × 104
  • chooseIndex may be invoked up to 8000 times.

Examples

Example 1:
Input:
["Picker","chooseIndex"]
[[[2]],[]]
Output:
[null,0]

Example 2:
Input:
["Picker","chooseIndex","chooseIndex","chooseIndex","chooseIndex","chooseIndex"]
[[[2,5]],[],[],[],[],[]]
Output:
[null,1,1,0,1,1]