This is the third time in the last few weeks that a problem has involved prefix sums for me, looks like its important. Thanks for the explanation, was clear, gonna try to code it up. My first attempt was very inefficient.
Why use a binary search? What's wrong with taking that random number generated and mod it to len(weights)? Wouldn't that still give you a random index with the correct weight associated?
Thanks for the Binary Search fundamentals explanation! You've emphasised that we return left pointer after "while" loop done. Does it really matter which pointer to return as we exit from the loop when left and right pointers become equal anyway? Or there is some extremely rare case which dictates we need to return exactly the left one?
I think often it does matter right one we return as it is dictated by how you move the left and right pointers during the loop and the loop condition itself. It's usually easy to figure out when you are walking your interviewer it, but realistically by the time interview day comes around you will have memorized this so you don't have to think about it.
Thanks for response. I guess we return the right pointer here as the right range contains all the possible "valid" numbers, so it's conceptually makes more sense to return pointer from right area for this challenge. @@crackfaang
A lot of people have requested it and based on the solutions on Leetcode it’s a DP problem which I don’t do on this channel because I hate it. If there’s a good DFS + Memoization solution that’s actually legible (some people have horrendous code…) then I’ll post it. Though it’s Facebook tagged and I know for a fact they don’t ask DP questions so I’m skeptical this question is actually being asked there
@@crackfaang agreed. My only concern is that since it was asked by FB (10+ during last 6 months), I am afraid there is an intuitive non DP solution, but so far the proposed solutions looks horrible
For this problem, the main algorithm revolves around the binary search and is the core code you need to write. For that reason I would not recommend using bisect because then the problem becomes too simple and the interviewer will probably ask you for the implementation. In questions where the binary search part is an accessory and not the main code you need to write, you can usually get away with bisect but it’s always at the interviewer’s discretion whether they allow it
Great explanation! Another more intuitive way to do the binary search part is to go with the binary search template, just do a further check when self.prefix_sums[m] >= target (we would like the target to be in (self.prefix_sums[m-1], self.prefix_sums[m] ] ). Further check: if (m - 1) < 0 or ( (m - 1) >= 0 and self.prefix_sums[m-1] < target), we can return m, otherwise, we do the normal left moving.
I was able to pass this question on leetcode by using random.choices() (albeit being very slow compared to other answers). I was just wondering if this would be an allowed solution? As I understand it, init would take O(n) time but I'm not sure what the complexity of pickIndex() using random.choices(population, weights, k=1) would be. Does anyone happen to know this?
You shouldn’t use random.choices(). The whole point of the question is to write the code to pick the index. Worst case scenario you do it in O(n) time with the naive solution but this is a binary search question and you’ll likely find it hard to pass without writing it. The binary search solution isn’t really a trick solution as if you can figure how to set up the naive linear solution, then it’s easy to realize you can optimize it by seeing that the values are sorted in order and thus can use binary search.
@@crackfaang haha yeah I just didn't think of the cumulative sum and range thing on my own. I was able to figure out the memory timeout solution though so maybe a bit more thought would have led me to this solution.
You probably already know the answer to your question, or it doesn't matter anymore, but I can clarify. The issue with using randint is that you select a random integer between 0 and max_sum instead of a random floating point number between 0 and max_sum. Imagine the prefix sums represent distances on a number line. For example, say we have w = [1, 9], then prefix sums will be [1, 10]. To correctly allocate the probabilities for 1 and 9, we must denote all the distances between 0 and 1 to w[0] and all the distances from 1 (not inclusive) to 10 (inclusive) to w[1]. Now, if you shaded in the number line for the corresponding values, you would see that w[0] gets 1/10 of the number line, and 9 gets 9/10 of the number line, which is what we wanted. But if you use randint, w[0] (1) would have values allocated 0 and 1, which is incorrect since we really want any point between 0 and 1 to correspond to 1. I hope this makes sense.
![LOWEST COMMON ANCESTOR OF A BINARY TREE III [PYTHON]](http://i.ytimg.com/vi/vZxxksAP8yk/mqdefault.jpg)
I have upcoming interview at Facebook next month. Pray for me guys..
how did it go? Mine is coming in two weeks
This is the third time in the last few weeks that a problem has involved prefix sums for me, looks like its important. Thanks for the explanation, was clear, gonna try to code it up. My first attempt was very inefficient.
This problem is trickier than I thought without putting my hands on it. Thanks for explaination!
Thanks for the video!! I've been struggling for hours to get the binary search right, and you cleared it all up!!
It’s certainly a tricky one but once you see how it works it’s actually quite intuitive
your explanation is great.
fantastic vid and explanation, keep up the great work!
Thank you! Glad you enjoyed the video and hope you find value in the other content
just curious why r = len(self.prefix_sums) as opposed to r = len(self.prefix_sums) - 1
ahh, its because l < r not l
@@zuccca it doesn't really matter. It just dictates the slicing to mid point. The mid point for len(self.prefix_sum) would just be +1
It was a little bit confusing but I appreciate you explaining the solution.
Why use a binary search? What's wrong with taking that random number generated and mod it to len(weights)? Wouldn't that still give you a random index with the correct weight associated?
Thanks for the Binary Search fundamentals explanation! You've emphasised that we return left pointer after "while" loop done. Does it really matter which pointer to return as we exit from the loop when left and right pointers become equal anyway? Or there is some extremely rare case which dictates we need to return exactly the left one?
I think often it does matter right one we return as it is dictated by how you move the left and right pointers during the loop and the loop condition itself. It's usually easy to figure out when you are walking your interviewer it, but realistically by the time interview day comes around you will have memorized this so you don't have to think about it.
Thanks for response. I guess we return the right pointer here as the right range contains all the possible "valid" numbers, so it's conceptually makes more sense to return pointer from right area for this challenge.
@@crackfaang
Excellent solution could you please add max consecutive ones III(LC 1004)
Very elegant explanation. Thanks a lot. Can you please do Leetcode 2060 as well?
A lot of people have requested it and based on the solutions on Leetcode it’s a DP problem which I don’t do on this channel because I hate it. If there’s a good DFS + Memoization solution that’s actually legible (some people have horrendous code…) then I’ll post it. Though it’s Facebook tagged and I know for a fact they don’t ask DP questions so I’m skeptical this question is actually being asked there
@@crackfaang agreed. My only concern is that since it was asked by FB (10+ during last 6 months), I am afraid there is an intuitive non DP solution, but so far the proposed solutions looks horrible
Thanks for the video, ser
why do we pick random number within 0 and total and not within prefixSum[0] and total ?
Can we use bisect.bisect(self.cumulative, target) instead of implementing binary search?
For this problem, the main algorithm revolves around the binary search and is the core code you need to write. For that reason I would not recommend using bisect because then the problem becomes too simple and the interviewer will probably ask you for the implementation.
In questions where the binary search part is an accessory and not the main code you need to write, you can usually get away with bisect but it’s always at the interviewer’s discretion whether they allow it
Great explanation! Another more intuitive way to do the binary search part is to go with the binary search template, just do a further check when self.prefix_sums[m] >= target (we would like the target to be in (self.prefix_sums[m-1], self.prefix_sums[m] ] ). Further check: if (m - 1) < 0 or ( (m - 1) >= 0 and self.prefix_sums[m-1] < target), we can return m, otherwise, we do the normal left moving.
Thank you
I am thinking that leetcode 704, also can figure it out by find the leftMost boundary, but what if inside the array doesn’t have the target?
never mind, I got it
I was able to pass this question on leetcode by using random.choices() (albeit being very slow compared to other answers). I was just wondering if this would be an allowed solution? As I understand it, init would take O(n) time but I'm not sure what the complexity of pickIndex() using random.choices(population, weights, k=1) would be. Does anyone happen to know this?
You shouldn’t use random.choices(). The whole point of the question is to write the code to pick the index. Worst case scenario you do it in O(n) time with the naive solution but this is a binary search question and you’ll likely find it hard to pass without writing it.
The binary search solution isn’t really a trick solution as if you can figure how to set up the naive linear solution, then it’s easy to realize you can optimize it by seeing that the values are sorted in order and thus can use binary search.
@@crackfaang haha yeah I just didn't think of the cumulative sum and range thing on my own. I was able to figure out the memory timeout solution though so maybe a bit more thought would have led me to this solution.
not sure why but random.randint(0, max_sum) fails in leetcode. Changing it to random.uniform(0, max_sum) passes.
You probably already know the answer to your question, or it doesn't matter anymore, but I can clarify. The issue with using randint is that you select a random integer between 0 and max_sum instead of a random floating point number between 0 and max_sum. Imagine the prefix sums represent distances on a number line. For example, say we have w = [1, 9], then prefix sums will be [1, 10]. To correctly allocate the probabilities for 1 and 9, we must denote all the distances between 0 and 1 to w[0] and all the distances from 1 (not inclusive) to 10 (inclusive) to w[1]. Now, if you shaded in the number line for the corresponding values, you would see that w[0] gets 1/10 of the number line, and 9 gets 9/10 of the number line, which is what we wanted. But if you use randint, w[0] (1) would have values allocated 0 and 1, which is incorrect since we really want any point between 0 and 1 to correspond to 1. I hope this makes sense.