The Egg Dropping Problem - Interview Question
ฝัง
- เผยแพร่เมื่อ 15 ก.ค. 2024
- In this video, we talk about the famous problem of throwing eggs from a tower.
(datagenetics.com/blog/july2201...)
The most popular version of this is: 2 eggs and a 100 floor tower. We work on the problem to find a generic solution for N floors and K eggs.
Code: github.com/gkcs/ChainReaction...
#interview #puzzle #egg-dropping
Binary search wouldn't be feasible for this problem. If you have less than log(N) eggs, narrowing down to the threshold floor is not always possible.
Eg: 100 floors and 2 eggs.
Throw the egg on floor 50. Breaks.
Throw the egg on floor 25. Breaks.
Uh oh...
Also, thanks to Banipreet Singh Raheja for pointing out two further optimised solutions here: leetcode.com/problems/super-egg-drop/solution/
Cheers!
I am late but using binary search with another hypothesis(i.e finding no of floors with d attempts and n eggs) can optimize the solution..just type in egg dropping problem Brilliant on google and search for the resource on brilliant website, hope it helps :)
Do linear search for last egg in the remaining range?
using binomial coefficient and binary search method we can solve it in O(nlog(k)) time.
www.geeksforgeeks.org/eggs-dropping-puzzle-binomial-coefficient-and-binary-search-solution/
If possible please explain this.
Varun Jain
We can use binary search also, no problem with that :)
Your explanation is very nice. Totally admire your effort :)
But, I am concerned about, How did we get this equation ?
And i always thought where will i use differentiation after my schools, now i have an ans 😂🤣
Hahaha, me too 😛
Now I wonder where would I drop E eggs from N floors xD Just kidding. Great explanation man!
Thanks for explaining each step with such clarity. I love the way you progress toward the problem as to why and how you are doing what you are doing. Don't trade this part for speed-or-anything. Some other channels really lack this as they are just vomiting out things they have mugged up, not telling why and what of the approach. Keep making such videos. Subscribed for eternity.
Thanks Muskan!
Gave me the intuition I was looking for.
Thank you!
Please keep up the good work.🙌
You are great man !! Simply great !! Not just spitting out some mugged up or already cooked up stuff., but explaining everything to the core that too in a simple and effective way. Great job. Keep up the good job and enlighten more people like me.
Thanks Gokul!
Thanks brother.Your way of analysis such difficult problems is awesome in a very young age.Praying for your bright future .God bless you..
Amazing! With the clarity of concept as well as the underlying mathematics, no wonder you work for directi!(saw that from comments) Seeing your approach of problem solving I was thinking if "this guy is from IIT?" and "that's the way true engineer solves problem!". You have definitely motivated me to go more for problem solving! Please upload more videos whenever you get the time. It would be great to get insights from your approach to problem solving :)
Thanks Shivank! I am glad it helped :-D
Heard a lot about DP but never knew its this much fun.....I Just learnt my first DP solved problem!!!
Thanks a lot...
quite possibly , the best explanation of this problem from algorithmic point of view.
Great!
Hey Gaurav, I really like the videos you make. Also, I just wanted to say that whenever you are speaking something I feel like you're going to burst into laughter. 😂 That really makes your videos kinda different in a positive way. :))
Thanks Bhargav!
I saw a few more on youtube but your is best explanation!Thank you.
Thanks!
Thank you so much for this awesome explanation!
You have an amazing explanation skills.
your way of explaination is amazing..keep it up bro!!
Thanks Anup! 🙂
Gr8 Explanation!! Noticed n=7 and e=2 has to have 4 instead of 3. I also created PR on your code.
Amazing now everything is clear to me.Thanks
Watching this at 3 AM. Loving it ❤️
This really helped me a lot! Thanks :)
For some eggs "e", Minimum number of trials required for "n"th floor would be "t"
such that tCe >=n and (t-1)Ce
+gagan nagpal What is C?
Gaurav Sen binomial coefficient
Sorry Gagan, I didn't understand why that would would work. :-/
Could you explain in some detail, or by taking an example?
Hi, I got this solution from here brilliant.org/wiki/egg-dropping/ (last para)
But a very formal proof is given, then I came up with my own greedy proof and here it is.
So, Idea is to maximize the number of floors that we can cover given "t" trials and "e" eggs.
Take some examples for clarity:
t=3,e=1 answer is 3 (1+1+1)
t=5,e=2 answer is 15(5+4+3+2+1)
t=14,e=2 answer is 105(15+14+13......2+1)
{
These answers are inspired by 2 egg puzzle, i.e. given two eggs and "n" floor,find minimum trials
eg
For n=100 , e=2 answer is 14
as the first trial is at 14 then at 27(14+13) then at 39(14+13+12) and so....
}
Here, intuitively we are choosing our first trial as t , such that if egg breaks here then (t-1) must be covered by remaining eggs and further our next trial is at t+t-1 because we have wasted 1 trial at "t" floor, so we can go maximum t-1 more floors ahead and so on...
So every time when eggs are 2, the answer is always the minimum value of" x" such that x+(x-1)+(x-2)+...+1 >=n.
Also, we can say that for "t" trials, and eggs =2, we can go for (t+1)C2 floors ahead eg t=14, floors=105.
So far so good.
Now, things get tricky for eggs=3,4,5
Let us try to think in the same direction for eggs=3,
Here, we should drop our first egg at a floor "f" such that (f-1) can easily be covered by 2 eggs, then are second drop should be at f+(f-1) floor, using the same analogy.
and we already know that the maximum number of floors with 2 eggs and "t" trials are given by (t+1)C2.
So, in effect for eggs =3, and "x" trials, we can cover 2C2 + 3C2 + 4C2+...+(x-1)C2 + xC2 = (x+1)C3 floors.
Hence , we can follow up the pattern and hence the answer.
I hope you may get the essence of it, idea is to maximize the floors by eggs.
for most tutorials on the TH-cam I have to watch on 2x speed. For your videos I have to watch on 0.75x.
Awesome video, thank you.
Gaurav sen and pepcoding made this question crystal clear for me
Love you,bro. Best explanation ever
Thanks!
Love this - very clear
You can make improvement in the innermost loop by doing Binary Search instead of linear search which would make Time Complexity of your code to O(n*e*log(n)).
Yeah that's a good catch.
now I know how to break egg with DP -;). thank you. Clearly explained
There is a problem similar to this in codechef,thanks buddy
No need to solve, the egg will break from 1st floor itself ! :D
Hahaha
In the array at the end of the video, I think that F[7][2] should be 4. If you run your code with N=8 and K=2, F[7][2] is 4.
Thanks so much Martin! I updated the code now :D
Simply great.
When I started learning programming , I loved Java a lot, but there was no one in my college to guide me. Even I remember geeksforgeeks don't use to have its maximum codes in java those days. So, even wanting to do those things, I couldn't do them. Even if I wanted to do them in Java myself I was not sure about if my solution is correct or not. Now coders like you guys make life of people like us great. You guys are really trying your best to promote the coding culture among college graduates. Hope to contribute like you guys one day.
Good work Gaurav, keep sharing the knowledge. At least I don't have to bother to learn DS Algo now. It might be little late than usual for learning them but definitely its not over.
That's the purpose of the channel :)
Let's do this!
@@gkcs Sure man
Very clear explanation. Thank you
Thanks Lokesh!
very nice explanation. Please do more!!
Thanks Janani!
I also had the same idea of using binary search. Suppose floors are numbered from 1..10, we drop a egg to floor 5. If it breaks, then we must search from 1..5, else from 6..10. This will be at max O(log2(n))
I read about 100 floors, 2 eggs. Now it is clear why binary search wont work. We only have 2 eggs, if they both break we cannot get the answer. eg for 100 floors, if threshold of egg is 13, we will break egg at floor 50, then at floor 25. We wont have any remaining eggs to test.
Thats right :-)
The moment u started differentiation it strumbled me
This exact question was asked to me in the OpenText final managerial round.
That's very helpful!!
Thanks!
@Gaurav , your second F[x-1][e-1] says to consider x-1 floors for e-1 eggs. But in your example f[2][2] this will amount to F[0][1] which I didn't understand why you missed ? Can you clarify this .
What if it breaks in my hand by taking upstairs do we consider boundary cases too :D, jokes apart your videos and understanding
are awesome.
I know it's quite late but I must comment. Got to keep the patience to understand this but really nice work done here. especially deriving formula. If you know how did you derive formula then you got soul of this problem. After formula it;'s just calculations and coding that formula. Nice work on explanation and code part too. Keep up the good work.
May be this video also help to relate to Gaurav's formula : th-cam.com/video/KVfxgpI3Tv0/w-d-xo.html
Thanks!
Egg broke and hence he changed his t-shirt 13:53
Hahaha 😛
My mind was now accepting if egg will be ever safe as if we drop even from a foot high :-) The more realistic object should have been coconut, pumpkin etc ... :-)
Anyway idea was good, good explanation.
Thank you 😁
Awesome explanation.
Thanks Bala!
Bro I don't understand why (N/B)+B and why we use differentiation. Can you please explain in short? Thanks for your awesome teaching... :)
In case dynamic programming seems too difficult, we can try practically by taking some eggs in a large building....
Hahaha!
At 16:45 , n=2 and e=2
so
f[2][2] = max(f[2-1][2],f[1-1][2-1]) , here x =1
f[2][2] = max(f[1][2],f[0][1]) , instead of max(f[1][2],f[1][1])
but now the answer will not be 2 so we have to iterate x to n which will include the case when we drop the egg from the top most floor as well.
P.S: Please let me know I am getting something wrong here. :D
Hi Gaurav, while reaching the end of your video, can you please explain why you took the value of x-1 as 1 in your second function which was F(x-1)(e-1) while you started with x=1.
Thanks in advance
I have the same question
I LOVE THIS
great explanation, thanks.
superb gaurav bhai
+Tolani Mahesh Thanks!
Hi Gaurav, excellent explanation. My question is: what is the relationship between the first part of the explanation where you showed that the minimum number of tries is 2 times square-root of N and the later part where you proved the generic case with the minimization?
Oh, I guess the 'brute-force' tries we do within B floors makes it not the best solution... let me know if that is it.
Very neat explanation
fastest case answer throw from the first floor (if i am the owner of first floor) possibility if it breaks then threshold floor is first floor, if it doesnt break then definitely threshold floor is the second floor because second floor owner will definitely break it by throwing it into someones head
which approach is better for beginner in dynamic programing either top-down or bottom-up?
great video
For those wondering, the min. number of tries taken in the last example (when n=8) is 4 ( th-cam.com/video/o_AJ3VWQMzA/w-d-xo.html ), while in the 2nd (minimization using derivative) case, it would be = 2*sqrt(8) = 2 * sqrt(4 * 2) = 2 * 2 * sqrt(2) = 4 * 1.41, which is greater than 4. #IDoNotKnowWhyIPostedThis?
Thanks for posting this 😁
#ThanksForPostingThis
Your first analytic solution of Y = (B + N/B) is based on a fixed size of floors within each segment of floors.
By minimizing Y you get that B=SQRT(N)
For example for N=100, B=10 which tell us that the best attempts are at the lower segment and the top segment suffers from 20 attempts.
A better solution will be if we choose, instead, a decreasing size for each segment of floors;
For the first trial you go [B] floors but for the next you go only [B-1] and the next will be [B-2], ..., [B-B]
By having decreasing sizes, the maximum trials for each segment is now fixed [B], [B-1+1], [B-2+2] ... [B].
The sum of these variable size segment is [B+0] + [B-1]+[B-2]....+[B-B] = 0.5*B^2 = N and therefore;
The optimal initial size B=SQRT(2)*SQRT(N)
For example if N=100 --> B=14
+Rbi Pro Thats correct, and that is what the solution uses for egg size 2.
In fact, recursively, we are looking at segments which can be completed using 1 egg less and one turn less everytime we have to make a throw. Maybe a direct formula can be found for f(n,e), but I don't know it :-p
You are a wonderful wonderful teacher bhaiya ✅✅
Thanks!
Thank you Gaurav.
Thanks Sunil :-)
Thanks for the video! I really enjoy the way you explain things. It is very nice to see the dynamic programming approach to the egg dropping problem. I think though that your logic has a mistake. I implement your algorithm and it gives wrong results. For example it produces F[10,2]=4 instead of 5. In fact, the path predicted if the first two attempts do not break the egg is floors 3 and 6 (which is the correct answer by the way), but then we are left with two eggs and 4 floors to check (7, 8, 9 and 10), which requires a minimum of 3 attempts, so 5 in total. I think that I have pinpointed the mistake at your logic. This problem is kindof special over other dynamic programming problems in the sense that we cannot perform the operations in any order we like. The first steps can be done only in increasing order of floors. When you split the building to bottom and top parts, you ignore this fact and you just add 1 attempt for floor x. This is true for the bottom part of the building, as you are going to treat all its floors in the recursion. For the top part of the building though, this is not true. Your assumption that you reached x with a single attempt is not correct, so for this case you have to add an extra number of attempts, which have been already performed at the bottom part, to reach x. I think this number is int((x-1)/((2**e)-1) but I might be wrong. Thanks again for the video.
Hey Nikolaos, could you try to run the code in the link in the description? I don't think it has a mistake :)
@@gkcs I tried the code. It's what I have understood from the video, and it has the bug I mentioned. For F[10][2] it gives 4. To convince yourself that it is wrong just take the F[100][2]=14 result. There is no way to check 100 floors with 14 tries, by just using 2 eggs. I think what you need to do to fix it is to change your line 23 to:
final int EggSurvivedResult = results[i - x][j] + (x-1)/((int)Math.pow(2, j)-1);
I'll check this out, thanks!
@@gkcs OK... I'm wrong :( Sorry for that. It was my misinterpretation of the DP algorithm results when I was trying to derive the non-DP solution. I lead myself to a different solution, which is not the optimal one, so I modified your algorithm to reach to it. Now I understand better the results of your algorithm, which are correct. At least with two eggs, the problem F[10][2] is indeed 4, and it means start dropping the egg from the 4th floor (not the 3rd as I mentioned earlier) and then move to the 7th (decrease the step by 1). This leads to worst case scenario of 4. The same is true for the F[100][2], which is 14 with the same logic (start dropping at 14th, then 27th, etc, ending up with up to 14 attempts). I will now try to understand the results for eggs>2.
Great! Just relieved I don't have to dig in the code again 😁
making omelette of it will be good choice in our floor rather than throwing and breaking it.
Another solutions, try from 1st, then 2nd floor, then 4th floor, then 8th foor, then 16th floor so on. Basically 2 power n growth every time, Then when it breaks use binary search between that number and last number that doesn't break it
That won't be optimal though. The number of tries could be as large as log(n) + log(n/2) + log(n/4)
= log(n) + log(n) - 1 + log(n) - 2 + log(n) - 3 + ... + 1
= log(n)^2 / 2
Try the approach for 100 floors. It's more than 14 tries.
Hello@@gkcs thanks for replying. Lets assume that our floors are a power 2. So lets assumed this apartment has 128 floors. So now if I jump starting from 0 all the way till 128 in powers of 2. I will be attempting from these floors = [1 2 4 8 16 32 64 128]
So if worst case scenario I realize that my egg breaks for the first time on the top floor only. That means the egg breaks somewhere between 64-128 floors. That means If I do Binary search between these numbers my worst case scenario Big O will be log(2^(n-1)) where n is 7 here (2^7 = 128). This is worst case complexity. Avg case will be less than this right. So are you saying its bad because log of a exponential number is being done here? If that's the case maybe we can use this approach and then divide this part with your block approach. My intent is if n is large like a million, I will find the range quicker with exponential jumps. Please tell if I am wrong somewhere?
@@prabhatracherla3098 take your time and think it through. Can you binary search after breaking an egg at 128?
No. What if you break the second egg at midpoint? You have no more eggs to search with.
If you do a linear search after it breaks at 128, you have reduced the size to 64-128. That's N/2 tries worst case. Pretty bad.
The approaches here are O(sqrt(n)) and better.
Googling differentiation formulas in between 😁
Thank You
Simple AP GP inequality will work too . remind me of my FIITJEE days.😂
Outstanding Sir
Thank you!
@@gkcs You made it so easy to understand.
@@gkcs You made it so easy to understand.
Here, we are searching for the min in the N-1 Floors. Instead we can do a binary search and reduce the complexity from O(N) to O(logN). That would reduce overall complexity from O(EN^2) to O(ENlogN)
Are you sure?
Give it a try 😛
@@gkcs I Just did. Infact O(EN^2) gives a Time limit exceeded on Leetcode for 100 Eggs and 8191 floors
Hey, i am trying much to be a great programmer but I can't think the solution of the problem immediately I take 1 2 days whole to get to the solution can you please guide how can I improve my speed to solve much problems.
We can always use binary serach and use the last egg for linear serach.
This would not be optimal. Try it with 2 eggs and 100 floors. Our solution is 14 worst case tries. Binary search is 50 worst case tries.
Thanks for the clear explanation, @16:18, as x = 1, then F[x-1][e-1] becomes F[0][1], any reason for saying it as F[1][1]
hi can anyone please tell what would be the output when floors>1 and egss=0 if reach this case in recursion ?
how the dp is better than sqrt decomposition approach...dp is running in O(n^3) but sqrt decomposition is running in O(sqrt(n))
can you please explain?
12:52 should'nt the x should start from 1? It would result in a loop, otherwise!
Thank you
Why don't I get this? Am I missing any prerequisite? Anyway, keep up the good work!
Dynamic Programming is a prerequisite for this video 🙂
can you please explain why we have to take maximum of F(x-1,e-1),F(n-x,e)
First of all ,Thank you for sharing knowledge. I have a doubt. Why are we not throwing egg from the last floor , for example if n=5 from 5th floor? Please correct me if i have misunderstood something.
Thanks for this wonderful explanation Gaurav. I had a doubt @13:23 you mentioned that the complexity of this problem is O(n*e*n) which is O(n^2*e). However, if we consider it as table filling problem. we are filling only n*e cells in the table so ideally we are solving n*e sub problems. so isn't it O(n*e) rather than O(n^2*e)? Please explain.
You need to find the max in each cell. That takes O(n) time. Hence n^2*e in total.
runtime for (i), (j) and (i,j) things i believe
Never looked at eggs this way...
Hello Sir,
As you have discussed earlier in this video a method with time complexity O(sqrt(N)) then why we doind Dynamic programming solution even it has bad time colmplexity?
Because the DP solution is correct and the other isn't. We want optimal number of tries, which sqrt decomposition sort of gives us.
@@gkcs "which sqrt decomposition sort of gives us." What does it mean?. Please elaborate on the reason for choosing the DP approach.
Isn't the sqrt(n) computation method better? Why use DP?
how to apply mathematics to solve these problems. how did you come up with a thought to use differentiation to solve maxima,minima. i studied differentiation but application is zero.. could you please share some good video which can fill up this gap
hi gaurav sen, i have a doubt, why are you minimizing the maximum worst cases from 1 to n-1? and not 1 to n? kindly explain pls.
Bro if egg donot fall from n floor it is not supposed to break from above floors i m kinda confused but good explanation 👍👍
when we do a sqrt decomposition, so if we have 1 egg and that breaks at say B then how can we calculate the real answer as we dont have any more egss.
So for sqrt is it the condition that the egg should be atleast 2?
Yes, you need atleast two eggs to break the tower into blocks. In fact, sqrt decomposition is not optimal for the given problem.
Consider a tower of 100 floors.
Each block of size sqrt(100) = 10 floors.
That means, in the worst case, we need B + N/B tries. Thats 10+10=20.
On the other hand, the recursive approach needs only 13 tries.
As he said in the video,
f(n,1)=n , so u should start dropping eggs right from the first floor itself,
which will be optimal.
Can you provide any free resources to learn aptitude ?
Well explained except for the "max" part. Do you have a better explanation for that? Thanks a lot for posting this video :)
Great explanation! However I am doubtful about the solution B = root(N) (at time 5:41 in the video). I think it was for the case of 2 eggs. For two eggs and 100 floors problem it would give number of tries as 20 but the answer is 14.
It is a solution, but not an optimal one.
Better than brute force though :)
can we use a binary search with logN comparison instead of sqrt decomposition for finding the solution??(I am not sure with binary search correctness for this)
Binary search would be a good try. I have added a comment to the video explaining why it wouldn't be optimal, though.
I think when no of floor is fixed than we can use binary search but when it is not fixed than we need to use sqrt decomposition
your explanation is awesome but i have doubt x will be up to n -1 not including n.
Also what happens if we apply square-root reduction repeatedly? Will it converge to the same results as you established later?
No.
They have a mistake in the blog post: if we have a lot of eggs then the solution is (1 + log2 n), not log2 n. I.e you have 2 floors and 1000 eggs, still need to try both floors. log2 of 2 is 1, the answer is 2.
Good catch. The asymptotic complexity is O(log(N)).
can we do the block skipping with dynamic programming? im confused. N -> root(N) -> O(N square)?
i) N was the number of tries in worst case using Brute Force Approach.
ii) 2 * root(N) was the number of tries in the worst case using SquareRoot Decomposition.
iii) O(N^2*e) is Worst Case Time Complexity to solve the problem and the number of TRIES here will be the minimum possible.
I have a question...
Why did you differentiate ? why w.r.t. B ?
because B is varying, N is fixed
@@anshulkoshyari1356 I know that, but why deferentiating that ?
You have a great solution but it is giving TLE on leetcode.
6:19 How is x-1 are the floors remaining after dropping an egg from xth floor? That can be anything less than x right? Shouldn't you have written x-constant? (Since that can be anything from x-1 to 0)
You break at most one egg with one throw.
Lol how many shirts are you going to change :P
The DP solution gives the minimal number of tries. Now suppose we have n=100000 and e=500, I need to find out the threshold floor where egg breaks. And for every floor i want to check, user gives me input that egg is broken or not.
Will binary search work for this case?
Yes. Eggs > log(N).
Could you do a binary search version of this problem? This DP is TLE at OJ. Thank you!
Read the pinned comment
at 16:28 Time, you say F[1] when x =1 , but in the formula it is F[x-1] so should not it be F[0] ??
please make more video related to competitive programming
Try this: th-cam.com/video/FbW_5ipDCbg/w-d-xo.html