Interview Question Software Engineer / Developers
Team: Java
Country: India
Interview Type: In-Person
Assuming there is always a solution, as mentioned in some of the answers above, 2nd egg is tougher. Also on the same lines, if first egg does not break even at 50th floor, 1st one is tougher.
If it breaks at he first floor, throw the second one from 2nd floor. If it doesn't break, then 2nd egg is stronger. Otherwise, we can't figure out which one is stronger.
first try at 10th floor if egg1 breaks,then try egg2 at 11th floor if it breaks then egg1 is toughest else egg 2 is toughest
if egg1 not breaks at 10th , try at 19th , if egg1 breaks then try egg2 at 20th floor if it breaks then egg1 is toughest else egg 2 is toughest
if egg1 not breaks at 19th , try at 27th , if egg1 breaks then try egg2 at 28th floor if it breaks then egg1 is toughest else egg 2 is toughest
do this again for 34th,40th,45th,49th floors in sequence
in worst case you require 8 attemts
:The best answer:
I shall generalize the solution for a general "n storeyed building"
Divide the interval of checking as sqrt(n)
Check for 1st egg to break at 1*sqrt(n) , 2*sqrt(n) , 3*sqrt(n) , .....until u reach "n"
Suppose it breaks at i*sqrt(n)
then check for the second egg at (i-1)*sqrt(n) , (i-1)*sqrt(n) +1 , (i-1)*sqrt(n) +2 , ..... , i*sqrt(n)
This gives the answer in O( sqrt(n) ) time which shall be least of all
How about we don't care about the building and just smash the eggs against each other with equal force? The strongest will survive.
Absolutely incorrect.
1. The force of the first egg against the second is always equal by value (and opposite by direction) to the force of the second egg against the first - third law of Newton.
2. If you thrust two eggs together with some force, there can be one of the three outputs:
a). Both eggs break.
b). None break.
c) One of them breaks, the other not.
You will have to try [potentially] large amount of different forces to find out which egg is tougher.
The problem statement is ill defined. The problem is not to "find the toughest egg," but instead to find out the highest floor from which an egg will not break when dropped out of a window.
If one is to learn an elegant solution best suited to the intended audience it's best to start with a better definition - found here: tinyurl<dot>com/lglon3g
I first thought this was the classic two egg puzzle (classic-puzzles.blogspot.com/2006/12/google-interview-puzzle-2-egg-problem.html), but it turns out this one is slightly different, so I am changing the solution:
Drop the egg at every other floor starting at 2nd, i.e., 2, 4, 6, 8, ...
if it breaks at that ith level, drop the second egg at i-1th floor, if the second egg breaks, then first is the toughest, second otherwise.
This isn't the same question. The question asks to find 'the toughest egg', while your question posits identical eggs. The solution will not work. For example, if the first egg breaks on the 10th floor, you have no information other than that it is less tough than being able to stand a tenth-floor fall, meaning if the second egg is also in that range you will not be able to tell which is tougher.
@Up you're right, it's not the same problem. Unfortunately it doesn't let me delete it, so I updated the solution. I gotta tell you though, this version has no originality.
Dropping at alternate levels wont work.
I mean u drop 1st egg at 8th floor and it breaks, then if you drop 2nd egg from n-2 which is 6th floor and it breaks, easy the first egg was the tough one.
But if it does not there are 2 things, it does not break at 6th floor so u might to try it now at 7th floor, if it not break there, fine we can still keep adding 1 floor to it. But if breaks at 7th floor, that does not prove egg 1 is weaker since we never tried it at 7th floor which would make them equal or egg 1 might have won.
The only answer i see here is go to each floor, once you find the floor where egg 1 breaks, try n-1, n and n+1 for the possible answers.
One egg is tougher than the other. That's implied in the question, because the question is asking which one is the toughest.
Therefore, they can't break on the same floor, because then that means they are equally tough and there won't be a solution.
Start from bottom of the building and find which story one of the gg breaks..for example egg 1 breaks at 4th story..now drop egg 2 at 4-1 i.e. 3rd story if it breaks then egg one was toughest else try 4th if it breaks both toughest else egg 2 is toughest.
- Anonymous July 01, 2013