# Solving Leetcode Interviews in Seconds with AI: Random Pick with Weight


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "528" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

	# Problem Statement
	> You are given a 0-indexed array of positive integers w where w[i] describes the weight of the ith index. You need to implement the function pickIndex(), which randomly picks an index in the range [0, w.length - 1] (inclusive) and returns it. The probability of picking an index i is w[i] / sum(w).  For example, if w = [1, 3], the probability of picking index 0 is 1 / (1 + 3) = 0.25 (i.e., 25%), and the probability of picking index 1 is 3 / (1 + 3) = 0.75 (i.e., 75%).    Example 1:  Input ["Solution","pickIndex"] [[[1]],[]] Output [null,0]  Explanation Solution solution = new Solution([1]); solution.pickIndex(); // return 0. The only option is to return 0 since there is only one element in w.  Example 2:  Input ["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"] [[[1,3]],[],[],[],[],[]] Output [null,1,1,1,1,0]  Explanation Solution solution = new Solution([1, 3]); solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4. solution.pickIndex(); // return 1 solution.pickIndex(); // return 1 solution.pickIndex(); // return 1 solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4.  Since this is a randomization problem, multiple answers are allowed. All of the following outputs can be considered correct: [null,1,1,1,1,0] [null,1,1,1,1,1] [null,1,1,1,0,0] [null,1,1,1,0,1] [null,1,0,1,0,0] ...... and so on.    Constraints:  1 <= w.length <= 104 1 <= w[i] <= 105 pickIndex will be called at most 104 times.  

	# Explanation
	Here's a breakdown of the approach and the Python code:

*   **Prefix Sums:** Calculate the prefix sums of the weights array `w`. This allows us to efficiently determine the probability range for each index.
*   **Binary Search:** Use binary search on the prefix sums to find the index that corresponds to a randomly generated number between 0 and the total sum of weights.
*   **Random Number Generation:** Generate a random integer within the range of the total weight to simulate the weighted probability distribution.

*   **Runtime Complexity:** O(n) for initialization and O(log n) for `pickIndex()`.
*   **Storage Complexity:** O(n)

	
	# Code
	```python
	import random
import bisect

class Solution:

    def __init__(self, w):
        """
        :type w: List[int]
        """
        self.prefix_sums = []
        total_sum = 0
        for weight in w:
            total_sum += weight
            self.prefix_sums.append(total_sum)
        self.total_sum = total_sum

    def pickIndex(self):
        """
        :rtype: int
        """
        random_target = random.randint(1, self.total_sum)
        index = bisect.bisect_left(self.prefix_sums, random_target)
        return index
	```