NVIDIA Morgan Stanley Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
ans) 1) place egg in each floor then the drops are 100.
2) Drop egg in 2nd floor then if it is broken then come to 1st floor and then drop the egg if it broken then we can say that from 1st floor on-wards eggs will broke else we can say 2nd floor on-wards.. If the egg not broken in 2nd floor then drop egge from 4th floor and apply same rule..... worst case -- 50 ways.
3) drop egg from 10th floor if it broke then start from 1st up to 9th floor --- like that the in worst case the ways are -- 19( 10,20,30,40,50,60,70,80,90,100, 91,92,93,94,95,96,97,989,99)
-------- 14(14+1)/10 = 105 it is near to 100.
so consider this case
drop egg from 14th floor if it broke then start from 1st to 13th floors .... if it is not broke then drop egg from 27th(14+13)floor if it broke start from 15th floor to 26th floor...
in fist scenarion and second scenario the no.of ways are 14 only.
continue the process like 39th(27+12)floor, 50th floor(39+11)...........
You can get the best ans in 12th ways and worest ans is 14th ways...
If its 100 floors. The best solution is to divide into slots each containing 10 floors. So we have 10 slots of 10 floors each.
Using the first egg try throwing from the end of each slot : 10th floor,20 th floor, 30th floor etc.
Say the egg breaks at 30 floor and not at 20th floor .
Now linearly try throwing the egg from 21st floor to 30 th floor. The max impact floor will be between 20th and 30th.
For a 100 floor building we can get the problem solved with max 10 + 9 tries. 10 tries to find the slot and 9 tries to find the floor within slot.
i think its a rather good answer... why do you call it stupid ? I think we could work on the idea and optimize it a bit more.. like dividing it into something better.. like... 11*9 < 10*10 .. but i didnt really do the math... good answer anyway ! Please explain when you call an answer stupid :) thanks
why it is stupid ???
lets assume we will throw first from 10th floor and it will break .. what is the next step ???????
if we apply binary search than 7 trial needed...drop from 50 if not break,drop from 50/2 that is 25,if break than 2(50+25)=37..drop it from 37th flr...likewise but in worst case u will need logn eggs.
@buzz.
You can brake at most 2 eggs in the process, but the solution you provided could brake log100 eggs.
It can be done also using 6 iterations..
1st drop from 6th floor(1+5 iterations)
then from 11th(2+4 iterations)
then from 15th (3+3 iterations)
then from 18th (4+2 iterations)
finally 20th floor (5+1 iterations)
But u shld give a generalised ans bcoz if suddenly the interviewer changes the no. of building to 100 then what would be your ans ???
May be u r at home so u took ur time and solved but what will u do there ???
Ans for 100 storey building :P
the question says you just have two bulbs. If we start from 6th floor and bulb breaks we just have one more chance to figure out from which floor bulb will break.
For trying second time unless we choose floor 1 and bulb breaks from 1st floor we can not be sure that any other floor could be a correct answer.
My point is we have limited bulbs in question
we can use binary search to find the floor from where the egg would be broken.
like we have 1,2,3,4,5.....100.
numbers r sorted. so we need to apply only binary search in this.
1- first we check at 50.if broken then answer.
2- if not then on 75 if broken then answer.
3- if not then 88
.......like this.
i think it would be the optimum solution.
OMG, why are people so obsessed here with algorithms ? Its a simple problem, why the **** would you need binary search for it !!! You are only getting two chances to break the eggs you dumb *******!!!
@eshank rastogi: Your answer is half complete. You would use binary search for the first egg and linear search for the second egg. Let me elaborate:
When you check by dropping the first egg from floor 50 for example; if the egg breaks you wouldn't get the answer as you implied (correct me if I misunderstood). You would then go on to search linearly with the second egg preferably starting from the lower floors to find the highest floor from which dropping the egg won't break it.
@Anonymous: If you look around yourself, algorithms are everywhere. There is nothing wrong with Eshank's answer. And if you do like to call people dumb using an anonymous moniker then why don't you present your "better" solution.
It is very clear
1) You are given 2 eggs.
2) Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.
Means out of two egg one will break even in first floor i.e.fragile or stronger i.e.may not even break if dropped from 100 th floor.
3) So drop any one from first floor if it breaks then second one won't break even 100 th floor.
Wow !!!!! The Exact solution and analysis of this problem is as follow.
In Computer science best method for searching is binary search. But here we can't apply that because we have only two eggs (which is a restriction for testing)
what we have to do is that we will start from 2nd floor and continue to drop first egg until it breaks at some floor.
It means try with 2, 4, 6, 8, ..... and so on up to 100. [this multiple is depend on number of eggs]
if first egg breaks befor or upto 100th floor (suppose Xth floor)
then try Second egg at X-1 floor to check whether egg can be dropped from X-1 floor without breaking or not.
In this way we can find the exact floor.
Now in best case We need only 2 drops that means from 2nd and 1st floor
while in worst case we need 51 drops. This situation arise when 1 egg breaks when dropped from 100th floor so we have to test with 99th floor using 2nd egg
So final answer Best case =2 and worst case=51, and avg case = 2*(2+4+...+100)/100 -1
it says that "eggs can be very hard or very fragile""may break from first floor or may not even from 100"
so no test dropping from any floor can prove that it wont break if thrown in a different manner from the same floor.
Its a play of words puzzle and not algorithmic.Testing common sense.
I had the same confusion "DoubleG" but i re-read the statement again.True, that it's written that an egg might break even from 1st floor or may not even break from 100th floor.. and + it's written that "EGGS ARE IDENTICAL" here's the catch.. now if two eggs are identical then it will both break at the same floor only.. In the worst case it will break at the 100th floor or might not even break :D and in the best it will break from the first floor itself.. So, these two cases are simple that's why eliminated.. hence what remains is the normal caseee.. which is wonderfully solved by user prateekjain12@gmail.com... check out!
Take a Pregnant bird took her to the 100th floor kill her and drop her.. Trust me egg will never break! :D
Validations:
1. They never said egg should be in direct contact with you
2. If egg breaks, pick one more pregnant bird and do not kill her just drop her coz flyng bird is also not a validation
Mission Accomplished! Discussion Closed!
put the egg in a jar of peanut butter and drop it. it will be intact. it did not say you could not put it in something.
honey u put 2 eggs in ur belly...jump frm 100th floor..if u alive then bingo u got it ...if not better luck next birth.
Observation: Regardless of how we drop Egg1, Egg2 must do a linear search. i.e., if Egg1 breaks between floor 10 and 15, we have to check every floor in between with the Egg2
The Approach:
A First Try: Suppose we drop an egg from the 10th floor, then the 20th, …
»»If the first egg breaks on the first drop (Floor 10), then we have at most 10 drops total.
»»If the first egg breaks on the last drop (Floor 100), then we have at most 19 drops total (floors 10, 20, ... ,90, 100, then 91 through 99).
»»That’s pretty good, but all we’ve considered is the absolute worst case. We should do some “load balancing” to make those two cases more even.
Goal: Create a system for dropping Egg1 so that the most drops required is consistent, whether Egg1 breaks on the first drop or the last drop.
1. A perfectly load balanced system would be one in which Drops of Egg1 + Drops of Egg2 is always the same, regardless of where Egg1 broke.
2. For that to be the case, since each drop of Egg1 takes one more step, Egg2 is allowed one fewer step.
3. We must, therefore, reduce the number of steps potentially required by Egg2 by one drop each time. For example, if Egg1 is dropped on Floor 20 and then Floor 30, Egg2 is potentially required to take 9 steps. When we drop Egg1 again, we must reduce potential Egg2 steps to only 8. That is, we must drop Egg1 at floor 39.
4. We know, therefore, Egg1 must start at Floor X, then go up by X-1 floors, then X-2, …, until it gets to 100.
5. Solve for X+(X-1)+(X-2)+…+1 = 100. X(X+1)/2 = 100 -> X = 14
We go to Floor 14, then 27, then 39, … This takes 14 steps maximum.
drop one egg from 1st floor..
if it breaks {
then its d fragile one.
take the hard one nd drop it from each floor from 2 onwards...
suppose it breaks at 20th floor..
DATS THE ANS....(exactly 2 eggs broken and got the ans)
}
if it does not break
{
thats the hard one....
try dropping the same egg frm each floor 4m 2 onwards....
say it breaks at floor 30..
DATS THE ANS(just one egg broken)
}
Buddies, It is all about to find minimum number of drops to find the floor from which eggs can break if drop from that floor.
so my answer is 14 drops maximu required to find the concerned answer. 14,27,39,50,60,69,78,87,96,100
suppose if try from 14th floor and first egg breaks then we have to linearly search from the 1st floor to 13th floor to find the exact floor. and if first egg doesn't break then we will try next on 27th floor, if egg breaks then we have to find exact by linearly search from 15th to 26th floor. and so on. In the worst case, 14 times I need to try to find the exact location amongst 100 floors.
So you need to solve n+(n-1)+(n-2)+...+1<=100, from where (n)(n+1)/2<=100 (this function transform is done with arithmetic series aka sum of an arithmetic sequence), now if you solve for n (wolframalpha: Reduce[Floor[n + n^2] >= 200, n] ) you get 14. Now you know that the first floor where you need to make the drop is 14th floor, next will be (14+14-1)th floor and whole sequence:
14; 27; 39; 50; 60; 69; 77; 84; 90; 95; 99; 100
If you break the first egg, you go back to the last one and linearly check all options until you break the second egg, when you do, you got your answer. There is no magic.
The answer would be 14.
Take the first egg and then identify the drop locations as 14 , 27 (14+13) , 39 (27+12) , 50 (39+11) , 59 (50+9) ...and so on till you reach 100.
Now start dropping the first egg on these drop locations in an ascending order.
Whenever it breaks , take the second egg and start dropping it from the previous location to that location successively.
Eg. Suppose the first egg breaks at 50th floor.
So no. of drops of first egg till the 50th floor = 4 (14,27,39,50)
Now start from 39 (previous drop location) and start dropping the second egg on successive floors . For this the max no. of drops would come out to be 10.
So 4+10 =14 (Max no. of drops)
The answer is the same when you calculate for any location.
I'm afraid people are over thinking the solution and not in fact reading the question posed.
The question asked is;
"* You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.
* Now the question is how many drops you need to make."
At no point in the question itself is there any requirement, for example, to drop the egg out of a window onto the ground below.
Therefore you take an egg up to the 100th floor of the building, let it drop 2 or 3 millimetres, it doesn't break and you have your answer.
you stupid idiots, the answer is 100 floors with 1 broken egg ...it asks....You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.....so go to the 100th floor and drop either egg,it will drop 100 floors and wont break, when it hits the concrete it will break but it has travelled 100 floors without breaking....so stick your binary where it hurts dummies.
Since you can only break two eggs trees would not help to find the solution. Say the egg breaks even at 20. Worst case that would mean you would have to go up by 1 from the first floor up until you until you break the second egg worst case 19 + 1 = 20. By throwing the egg at increments of 10, then incrementing by 1 you get worst case 10 + 10 = 20, but accounting for the fact that you know after the 9th throw of the egg not breaking that it is between 90-100 and in that case you have not broken any eggs. Then you throw one at the 95 floor. If it breaks throw from 91 to 94 worst case 9 + 5 =14. If it doesn't break throw from the 98th floor, if it breaks increment by one from 96-97 worst case 9 +4 =13. If it doesn't break throw from 99th floor if breaks worst case 9 + 3 -= 12. Which gets fairly close to root n
Try with 7th floor.. if breaks then 1 to 6th (1+6 iterations)
if it does not break,
then with 12th .. if breaks then 8-11th floor (2+4 iterations)
then with 16th floor (3+3 iterations)
then with 19th floor (4+2 iterations)
if still it does not break.. then 20th floor is the answer.. in that case total 4 iterations.
So, Maximum no. of iterations is 7.
Generalized answer is :
Whenever in this sort of situation , use the following approach:
so first we have to choose a point , where we want to drop our glass let say 6 floor so iteration would be 1+(6-1)
Next step we want want to the floor at a distance of (6-1) from first time floor so our total iteration still remain same so we will take one count from previous drop and 6-2 from this one so again 1+1+(6-2)
and so on .....
so now u can see the pattern that is 1+2+...................+n = 20
so n(n+1)/2 = 20
which comes n = 6(approx)
Our first drop should be from floor 14, if egg survives we step up 13 floors to floor 27, then up 12 floors to 39 …
The optimal strategy is to work our way through the table until the first egg breaks, then back up to one floor higher than the line above and then proceed floor-by-floor until we find the exact solution.
This complete table is shown in here on the left.
The maximum of 14 drops is a combination first egg drops (made in steps), and second egg drops (made in ones). For every drop we take hopping up the tower, we reduce the worst-case number of single drops we’d have to take so that no solution is an outlier.
In the given set of egg there are two type of egg very hard or very fragile. so provability of hard is 50% & provability of fragile is 50%.
highest floor of a 100-storey building an egg can be dropped without breaking. = 100
how many drops you need to make. You are allowed to break 2 eggs in the process.=infinite
Why can't it be 12 drops? Try it at every 13th floor, the worst case should be 90 floors. If you try 13,26,39,52,65,78,91. That is a total of 7 attempts, assuming the answer is 97 floors. At this point, on your 7th try, your first egg has cracked from the 90th floor. You can try with your second egg on the floors 80,82,84,86,88. If you try at every 2 floors, if the egg cracks on that floor, the floor before it is the threshold, if the egg survives, try x+2 floors. You can try in 2 increments instead of 1 increments because if the egg cracks, the threshold is the floor before.
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<title>The life and death of egg1 & egg2</title>
<script> // Eggs are delicious why would you drop them... consider the bacon!!
function eggsBreakEasily(eggs) {
food = "Yummy";
}
var eggs = {
gift: "egg 1",
prize: "egg 2"
};
// I'm getting hungry writing this... ** in the unlikely event that 1 + 1 =! 2 the eggs are dropped and now we're both hungry.
var oops = 2;
if (1 + 1 === 2) {
alert("Are those egglands best?? Follow me to the kitchen :)");
}
else {
console.log("Wonderful... now we don't have any more eggs :/")
}
// Any arguments? Any nay sayers? lol
</script>
</head>
<body>
Don't forget the bacon!
</body>
</html>
There you have it folks!
The answer is in the question itself....our job is to find out highest floor of the building and they say its 100 floors so we dnt need to drop any egg to find out highest floor,ans is 0 drops!!
drop the egg from 1st floor if it break 1 st floor will be the first from where it break, if it doesnt break take it to the 2nd floor if it break 2nd floor will be the lowest floor from where it break. repeat the whole process until the egg doesnt break, and save another egg and have a omlete :P
This one is classy problem :
- Punit Jain May 06, 2012classic-puzzles.blogspot.in/2006/12/google-interview-puzzle-2-egg-problem.html