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
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.
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
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! :)
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
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
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
Your answer did not go through. The hash map method went through fine. I got this "time limit exceed' error using your answer. Please help....
reservoir sampling is cool
Why is this, O(N) solution, "optimal", when you can use a hashmap and answer queries in O(1)? Makes no sense.
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.
I'm confused are the numbers sorted?
no
This would be biased since we always have higher probability to select the first index that equals target right?
Not really. On the 2nd pass you have a 50 /50 chance to select the 1st and the same for the 2nd.
Awesomely explained🎉, but when you suddenly moved to coding my eyes got burnt because of the light theme😂
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
Found this solution and explanation more intuitive than others!
Thank you for all these videos with easy explanations.
Will be glad if we have all Hard Leetcode problems playsist.
I don't understand the question, can anybody explain that? 😂
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! :)
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
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
Thank you very much
great explanation
nice