Random Pick with Weight | Bucket approach | Leetcode

This video explains a very tricky and important interview question which is to randomly pick index based on weighted value.In this problem, we are provided with an array of weights and we are required to choose an index in such a way that the probability of getting an index chosen is higher for a higher weight index and lower for a lower weight index.I have explained the approach to solve this problem using bucket.Once we form buckets then the next step is to just generate the random number for each query in the range of 0 to SUM and use binary search to find in which bucket does the random number fall into.We can also use upper_bound to avoid implementing binary search.I have explained the code walkthrough at the end.CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
=================================================================
INSTAGRAM: / surya.pratap.k
LinkedIn: / surya-pratap-kahar-47b...
=================================================================
CODE LINK: gist.github.co...
SIMILAR PROBLEM:-
Aggressive cow: • Aggressive cow | SPOJ

[@roopakalluri4014]

The first sentence is awesome: I'm sure you didn't understand anything from the problem statement!

[@techdose4u]

🤣

[@ibrahimshaikh3642]

😄

[@NewMovieTrailersTransformed]

I liked it too because i really didn't understood anything about the problem :P

[@AG-zc2jt]

🤣

[@MinhNguyen-lz1pg]

Yep same here, glad that im not the only one lol

[@misoren9645]

Hi for anyone wondering why we use upper_bound instead of lower_bound, I thought about it and here is the explanation: 1) lower bound returns the first element (in the range) "not less than" (i.e. greater or equal), upper bound returns the first element greater than the value to search. 2) The value to search is rand()%sum and this returns a number from (0 to sum - 1). Particular cases: a) so say you search for the value (sum - 1) [last possible value in rand()%sum] you should return the last index as well, which is why you would be searching for sum, which is greater than sum - 1, so you use upper bound. For instance if last value of the weights/array is 1, lower_bound would give the index before the last one, which is equal to sum - 1, which would be wrong. b) Say, the first element of the cumulative sum is x (S[0] = x), then numbers from (0... x- 1) should map to first index (0 / S[0]) (since this fills a "bucket" of length "x"), so if you search for value x you should map to the second index, so using lower_bound of x would give you 0, which is wrong. So you use upper_bound. For example, say array is [1,2,3], sum is [1,3,6] if you search for value 1, you should not return 0, which is what lower bound gives, since they are equal, you should return 1, because the number 0 (in the line) is mapping to 1, so the bucket of size 1 is already allocated. For the general case: each interval of numbers map until S[x] - 1, so if you search for S[x], using lower_bound gives you x, but x maps until S[x] - 1 and not S[x], so you need the first greater value, which upper bound gives. Therefore you use upper_bound. This is also why, you can use lower_bound if you add + 1 to the value searching (rand() % sum + 1), in that case, first index will map from (1... to S[0]), so searching with lower_bound S[0] should give you 0, which is correct and similar for the general case.

[@ShubhamMahawar_Dancer_Actor]

worst explanation by leetcode in their problem statement ,but you nailed it.

[@techdose4u]

😅

[@divyashahi9364]

why haven't u used lower_bound it would have been more appropriate, but using lower_bound gives wrong ans from larger test input may you please explain that, BTW, really nice explanation.

[@techdose4u]

I will check.

[@sneha_2005]

Thanks for this video. I was trying so hard to understand the question from the discussion section and everyone was using this cumulative array and I couldn't understand how it is helping. Now I am getting it finally!

[@techdose4u]

The problem was not at all explained. It was a very good problem but only if the problem statement was better 😅

[@simplecop123]

I cheated myself by copy pasting the solution for this problem. Because I do not want to lose the streak of coding challenge. Leetcode have so many good problems yet they go with stupid problem.

[@techdose4u]

This problem was very good but sadly, poorly framed :(

[@boyuanchang8708]

I subscribed as soon as you said I'm sure you didn't understand anything from the problem statement lmfao...

[@techdose4u]

😂

[@markos8955]

you use upper_bound . why not lower_bound()?

[@techdose4u]

Don't use either. Implement your own. None of them are working now.

[@bhumikabhatia3416]

Is there a reason why we can't use lower bound? All the test cases did not pass if I used lower bound. >= will be lower bound so if our random number is 3 it should fall in the second bucket right so what's wrong with using lower bound?

[@techdose4u]

I think lower_bound gives you the floor and upper_bound gives you the ceil and we have assumed our bucket to end at cumulative sum. Each bucket is assumed to be to the left of the current element. So it's natural to use ceil and not floor.

[@techdose4u]

Lower and Upper bound both are failing for this problem now. So it is required to implement our own binary search.

[@misoren9645]

​@@techdose4u lower_bound, upper_bound and the solution implemented has nothing to do with ceil and floor. Ceil and floor are for decimal (with decimal part) numbers. Here the weights are integers and the cumulative sum therefore is also an integer, so searching the number and the modulus operation is also an integer, so there is no ceil/floor operation here. Rather lower_bound is for not less than (greater or equal) comparison while upper_bound is for greater comparison.

[@abhishekgairola9166]

Why do we use upper_bound and not lower_bound , and % is taken with sum and not sum+1??

[@pavanguntuboina8934]

Sir y upper_bound y not lower_bound could u tell me plz

[@techdose4u]

This you should try yourself. Forget upper and lower bound. Just remeber binary search.

[@TheTushar35]

would like to meet you sometime! How can i contact you?

[@techdose4u]

My pleasure :)

[@avaz7939]

I love your opening of "I'm pretty sure you didn't get anything from this problem statement" :D Great explanation

[@NikhilKumar-oy7mx]

this can also be used for probability array like in 1st example probability were (1/6, 2/6, 3/6) so create a vector and store 1 once, 2 twice and 3 thrice. and when you generate rand() from this the purpose will be fulfilled. Please let me if this lacks in any manner than what's shown in video.

[@techdose4u]

This cannot be used. Your weight range from 1 to 1e5. You cannot make a line by counting each number. This is the same concept as perfect subarray from Google kickstart round C question 3. You should have seen that. You idea can work for very small numbers and will consume a lot of extra space.

[@md_aaqil8027]

Java Solution class Solution { Random random; int[] nums; public Solution(int[] w) { random = new Random(); nums = new int[w.length]; nums[0] = w[0]; for(int i = 1; i < w.length; i++) { nums[i] = nums[i - 1] + w[i]; } } public int pickIndex() { int n=random.nextInt(nums[nums.length-1])+1; int left=0,right=nums.length-1; while(left

[@techdose4u]

👍

[@roshankharke3725]

Sir, your mic quality is so good everything you explain is pretty clear and I can listen to you all day :P

[@techdose4u]

🤣hahaha Nice

[@NikhilKumar-oy7mx]

yaha thodi koi number de raha h. aadat jayegi nhi tumhari :) (:

[@NikhilKumar-oy7mx]

I am not sure how the ans is checked as at the end we are generating random and picking based on probability so even though the probability might be less for some element but still it can be picked.

[@techdose4u]

Answer is checked correctly because they the distribution of rand(). So a certain percentage of error can be allowed and if you get lower error then you pass because you must have followed correct process. Rand() is not random. I have already explained this to one guy in comment. It all depends on the seed you use. Same seed or no seed will yield same answer after compilation.

[@ShreyanGoswami]

I think this is the most interesting problem leetcode has given in their monthly coding challenge. Thanks for the explanation.

[@techdose4u]

I agree with you. But they ruined the problem using very poor problem statement.

[@sohinidey6711]

Still now I can't understand the meaning of the question to ready the question again.. understood ur video..

[@techdose4u]

It was not explained at all. How can anyone solve without understanding what to do 😅

[@neelamgour5538]

@@techdose4u how did you get then

[@ajaychauhan-lu6yy]

consider the weights as 1 2 3 4 now the cumulative sums are. 1 3 6 10... suppose randomly generated number is 3...its upper bound will give index corresponding to 6 i.e 2 whereas the ans should be 1 which is given by lower bound...why is this so?? PLEASE EXPLAIN..

[@techdose4u]

Both upper and lower bound are now giving wrong answers. Better to just implement binary search.

[@ajaychauhan-lu6yy]

@@techdose4u so why upper bound solution got accepted???

[@DeepakSingh-uf5vv]

What if the array is made up of floats something like 0.76546, 2, 0.65, ....

[@ishakansal778]

thankyou so much sir. Sir its a request if you can share a list of all questions asked in Microsoft coding round. I am preparing for 2020 campus placements

[@techdose4u]

There is no specific questions for Microsoft. Just practice as many questions as you can. No special questions are asked for it. Everyone will ask the same type of questions.

[@fatimajaffal9843]

I just wonder why you subtract -v.begin() ?

[@techdose4u]

Upper bound doesn't give integer type but difference if those 2 values will give integer. V.begin() is always first index. So subtracting it is as good as not subtracting. That is just done to change the data type to integer.

[@fatimajaffal9843]

@@techdose4u got it, thanks for very helpful video.

[@techdose4u]

Welcome :)

[@NikhilKumar-oy7mx]

@@techdose4u you can also use binary_search()

[@niranjanhegde1535]

Wow! Was waiting for this video. I had difficulty in understanding the question

[@techdose4u]

:)

[@Evie-uj1en]

"I'm pretty sure you didn't get anything from this problem statement..." LMAO

[@subhamkumarmishra9610]

Late upload bro. I had been waiting for your video to pop up. Your explanations are pretty amazing .

[@techdose4u]

Office work will make videos late 😅

[@amarnaath5673]

TECH DOSE I guess youre Surely working in FANG wow what a talent Man✨

[@subhamkumarmishra9610]

@@amarnaath5673 HAHA ! yes you are right.

[@birudaya9964]

same here. :P

[@--------------------------2792]

rand()%sum will never choose sum we should use sum+1 it got passed in online judge because some relaxation is given for random number question.

[@sreejiths2735]

Great explanation, but how are we sure that rand function always produces the result in the way we wanted, if it's completely random, then it can stick to a single element or two also right.

[@techdose4u]

Nope. Rand sequence depends on seed value. Rand is based on algorithms which is not random. If you give same input then you will get same output. To make it look random, we generally use seed value as a previous value using which subsequent random numbers are generated. Generally current time is used as a seed in rand() and so it won't ever stick to one value. If you compile and generate random nos then you will get the same sequence each time if you don't explicitly use changed seed for each compilation. The problem setter doesn't expect you to do this. Thats how it predicts the rand generation graph. It has a typical distribution curve. Search. Nothing is completely random.

[@sreejiths2735]

@@techdose4u Wow, this cleared my doubts, thank you so much for the detailed explanation sir, you are doing an extremely awesome work.

[@techdose4u]

Thanks :)

[@adrian14752]

this might be really dumb, but where in the question does it say the weights are sorted?

[@srivatsanv.r1162]

I was waiting for your explanation. I followed the same approach of cumulative sum and binary search. Only half of the test cases were passed but when I tried to find iterative way solution got accepted. I didn’t use any binary search utility rather I wrote it as a function. I tried to print the sum index for most of the random elements and it was fine. Not sure why it failed. Help me. Thanks Tech dose 🙏

[@techdose4u]

Glad that you implemented :)

[@soumilkhandelwal4388]

Man, the question said nothing about the question itself... lol. Thanks for explanation

[@techdose4u]

Yea correct 😅

[@kumarc4853]

thank you

[@techdose4u]

Welcome

[@vaibhavgoel3915]

Awesome Explanation, curious to know that as in your code you are not making any IO operation by yourself, so do using fast IO in solution constructor will effect the speed of the code

[@techdose4u]

Yes. Try without it and you will understand.

[@awsomeoproductions4]

Amazing video! What microphone do you use?

[@techdose4u]

Boya

[@100bands]

Great explanation as always. One subtle thing I think you should have mentioned is that the expected leetcode answer is likely to be different from your actual answer but it doesn't mean that your answer is wrong. This wasn't obvious to me at first.

[@techdose4u]

Actually these type of random distribution type question depends on your percentage accuracy. Question setter knows the distribution of rand fn (which is not completely random). We are not using changing seed as well. That's how these questions work.

[@sameergirkar]

Quick Clear and Complete explanation of the problem as well as the solution. 👍🏻 Thank for the explanations.

[@techdose4u]

Welcome :)

[@birudaya9964]

what they actually meant in the output portion, I meant how they are related to our return value. Also, how the latter pickindex arrays are filled? this question is still unbelievable

[@techdose4u]

Poor problem statement but very good question if properly explained.

[@andyhujian]

What if the range of rand() is smaller than v.back()?

[@techdose4u]

Rand_Max is atleast 32767 and it depends on implementation and our weights were were 10K if I remember correctly. So, there will be no problem. The question setter must be knowing these stuffs 😅

[@kunalsinghgusain2070]

Enough end this bucket. Come to the point man. You cleared the intent long ago but that extremely extra explanation made the video long. 🤣👍

[@techdose4u]

🤣 Everyone doesn't get it as quickly as you did man 😅

[@kunalsinghgusain2070]

@@techdose4u that's true and I realized later when I actually coded it myself. Apologies if you found my comment rude.

[@The85souvikdas]

Thank you for the explanation...problem was very unclear.

[@techdose4u]

Yea correct :)

[@yitingg7942]

Wow Great explanation. Can't believe you can do it this way.

[@techdose4u]

Thanks :)

[@mehular0ra]

explained really well sir!

[@techdose4u]

Thanks :)

[@minakshikudalkar557]

Really appreciate your efforts Sir :) Thanks for the videos, very clear and easy to understand!

[@techdose4u]

Thanks :)

[@ashuterasoft]

you are awesome

[@HimanshuSingh-ob9qo]

👍

[@techdose4u]

👍

[@spetsnaz_2]

Don't know what to say about this question 😐

[@techdose4u]

🤣 Don't utter anything.

[@shrad6611]

explanation is good but I really hate this problem

[@techdose4u]

True

[@rishabhkumar8115]

Thanks for this video. I was trying so hard to understand the question from the discussion section and everyone was using this cumulative array and I couldn't understand how it is helping. Now I am getting it finally!

[@evgeni-nabokov]

Understanding the problem took more time than making up the algorithm in my head. I am curious how they test nondeterministic solutions.

[@neelalexpaul]

Great explanation. I would suggest using lower_bound over upper_bound to make the concept clear. Something like the following: int random = (rand() % maxVal) + 1; return (lower_bound(prefixSum.begin(), prefixSum.end(), random) - prefixSum.begin());

[@abhishekgautam1063]

Very unclear problem statement :(

[@techdose4u]

Yea. Not explained anything at all.

[@abhishekgautam1063]

@@techdose4u yes sir!

[@saurabhsomani9188]

Hi Surya, I have followed your approach and have written my java code. The code is failing 1 particular test case on LeetCode. Can you please have a look at the below code and let me know your thoughts on it? ``` class Solution { int sum = 0; int[] bucket; public Solution(int[] w) { bucket = new int[w.length]; //calculate sum for(int i : w) sum += i; //Bucket array will define the range in which the random number generated should be found //The bucket array will have single values which will define the rightmost side of range //with the leftmost number denoted by it previous value. //for index 0, the previous number will be zero '0'. So the range will be 0 to w[0]. //now for the next element at index 1 the leftmost side will be bucket[0] + w[1]. int leftBoundary = 0; for(int i = 0; i < w.length; i++){ bucket[i] = leftBoundary + w[i]; leftBoundary = bucket[i]; } //For the random number to be searched and determine if it lies in which bucket, we will only //use the rightmost side of the range, i.e, the value in the bucket array. //if the random number generated is less than the righmost side of range, we choose that bucket //by returning its index. Here the index corresponds to same position in 'w' array & in //'bucket' array. } public int pickIndex() { Random rand = new Random(); int upperBound = sum + 1; //random numbers to be generated from 0 to sum int randomNumber = rand.nextInt(upperBound); //since the bucket array is a cumulative sum, it is in sorted order. So do a binary search int start = 0; int end = bucket.length - 1; while(start < end){ int mid = start + (end - start) / 2; // if(bucket[mid] == randomNumber) // return mid; // else if (bucket[mid] >= randomNumber) end = mid; else start = mid + 1; } return start; } } /** * Your Solution object will be instantiated and called as such: * Solution obj = new Solution(w); * int param_1 = obj.pickIndex(); */ ```

[@saurabhsomani9188]

Hi Surya, I fixed the code. The error was with the scope of 'Random' class variable. I made the variable as a global instance and used 'this' keyword for all the global/class variables.

[@ashishm8850]

Thank you!

[@techdose4u]

Welcome :)

[@gadgetguy6651]

Amazing explanation!

[@Anand_Jena]

hi what os are you using ?

[@nagajaswanth831]

Waited for you video .......

[@techdose4u]

I hope you tried your best to solve it :)

[@nagajaswanth831]

@@techdose4u yes sir, I always try to complete the question before you upload your video, but I didn't understand this question..you prove that wait is worth....

[@techdose4u]

Thanks :)

[@Igloo11]

Always awesome explanation!!

[@chankwongyin7455]

Well explained!

[@agileprogramming7463]

Wow that was a tough one!

[@yatri6329]

Kuch nhi samjh aya kya bol gya