Barclays Hiring | Probability Based Sampling, Prefix Sum Optimization and Binary Search Selection Technique | Off Campus OA 2022

Problem Statement You are given an array w where w[i] represents the weight of index i. Implement a data structure that supports: Solution(int[] w) int pickIndex() The function pickIndex() should randomly return an index such that the probability of choosing index i is proportional to its weight. For example: Probability(index i) = w[i] / sum(w) Example 1 Input: w = [1,3] Output: pickIndex() Possible Results: 0 -> 25% 1 -> 75% Example 2 Input: w = [2,5,3] Output Probabilities: Index ...