RANDOM PICK INDEX | LEETCODE # 398 | PYTHON RESERVOIR SAMPLING

Рет қаралды 7,920

Күн бұрын

Пікірлер: 27

@smoran02 7 ай бұрын

Really missing the proof for why it works for the earlier indices. For example for the second value, probability of 1st selection is 1/2. Probability of being selected next is 1/2 * 2/3 = 1/3. Probability of being selected when you have seen 4 values is 1/2*2/3*3/4 = 1/4. This is what makes the explanation make sense

@provarence7361 Ай бұрын

great comment, was confused about this

@shoaibakhtar9194 5 ай бұрын

Equal possibility return explanation. So in the loop, the index closer to the start is easier to be picked, but also easier to be replaced since more iterations left behind. For example, let's say we have 5 duplicates in total. For the 2nd index, the chance it get returned is: 1/2(pick)*2/3(replace)*3/4(replace)*4/5(replace) = 1/5 with 3 iterations left; Replace probablility is calculated like this:- 2/3(replace means 2 index 1st and 3rd) can be picked and total possibilities are 1,2 and 3 indexes. So change of getting replaced is 2/3) For the 5th index, the chance it get returned is: 1/5(pick) = 1/5 , no chance to be replaced since no iterations left.

@sourvad 8 күн бұрын

You sir, are goated

@shuier525 14 күн бұрын

Comment from Nov 2024. Thank you for pointing out this great solution. The solution tab for this question has been disabled. This RESERVOIR sampling solution is still TLE. Without your explanation, I do not even know there is a RESERVOIR SAMPLING solution. I think the main reason is because leetcode might updated the constraint to a larger number: Constraints: 1

@kareni7572 4 ай бұрын

Found this solution and explanation more intuitive than others!

@manojamrutharaj9071 2 жыл бұрын

Thank you for all these videos with easy explanations. Will be glad if we have all Hard Leetcode problems playsist.

@piyush10793 11 ай бұрын

This would be biased since we always have higher probability to select the first index that equals target right?

@JAIMEAYMERICHFANS 10 ай бұрын

Not really. On the 2nd pass you have a 50 /50 chance to select the 1st and the same for the 2nd.

@KiKi-lt4pf Жыл бұрын

Awesomely explained🎉, but when you suddenly moved to coding my eyes got burnt because of the light theme😂

@crackfaang Жыл бұрын

Normally I hate light mode but I've done so much Leetcode over the years before they had dark mode that my brain is used to the standard theme. But yes, at work whenever I see someone's VS Code and they aren't using a dark theme I think they're a bit nuts

@Krankschwester 6 ай бұрын

Why is this, O(N) solution, "optimal", when you can use a hashmap and answer queries in O(1)? Makes no sense.

@erice.3892 28 күн бұрын

you have to iterate through the list to make the hashmap, which would be O(N) as well. but i see what you mean. you can store the hashmap and reuse it, therefore save time if this function is called multiple times

@arjityadav8371 22 күн бұрын

Yes, his pick function should be optimized to retrieve in O(1) and that can only be done if he has stored the input in hashmap taking up space O(N)

@johnlabarge 6 ай бұрын

I'm confused are the numbers sorted?

@SeanKearney-g7d 2 ай бұрын

@YT.Nikolay 2 жыл бұрын

I solved this question using dict, I am wondering if the interviewer would like to have me implement reservoir sampling. P.S. first time I see this algorithm, worth memorizing? And again, thanks for the video! :)

@YT.Nikolay 2 жыл бұрын

I am dumb, again, I solved the problem myself and then watched the explanation. #facepalm I guess it clicked, and I would be able to solve it if ever have this on interview

@crackfaang 2 жыл бұрын

I’d say know the reservoir sampling solution. It’s quite simple and intuitive once you have seen it before. The dictionary one is too simple and if they are asking this question they probably want to see the optimal one