Microsoft Highbridge Capital Interview Question
Software Engineer / Developers Financial Software DevelopersI know it can be done with fourteen, but my friend (who won't divulge but has credibility) says it's 12. The key is to assume that the minimum needed steps are equal at every step of the way.
Suppose we drop an egg from the 10th floor, then the 20th, …
»» In 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 1 through 100, then 91 through 99).
»» That’s pretty good, but all we’re considered about 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. eg, 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.
Assuming that 1 <= N <= 100...
Well, you could do it by twos. You start by dropping an egg off the second story. If it breaks, drop it off the first story. If it breaks there, N=1; otherwise, N=2. If it doesn't break on the second story, drop it off the fourth story; it'll work the same way, because you know N!=1 and N!=2. That would take, at worst, 51 drops.
Read all below replys..
they have not taken into
consideration that we have
only two eggs to find out N.
Nex3 seems right to me.
After the first break, there is no other way to continue other than bottom up. So, the first egg can be used find the out break floor as close as possible to N and the last known no-break floor. The best approach will be to start from the level of m where integer ceiling of |lg(M - m)| = m-1 where M initally is 100. This will come up with m=8. Which means, start from 8th floor. Then, if not break, second try is at a new m recusively of |lg(M-m)| = m-1 where M = 92. So, the second m is still 8 which means second try floor is 16th. Reursively, then, the worst case is 18 tries when N=96.
Drop egg from floor1. it it does not break, drop it from floor2, it it does not break drop it from floor3. you will eventually find N.
and for 3 eggs:
use 100/k_1 windows of size k_1, each of which is then broken into k_1/k_2 windows of size k_2, each of which is broken into k_2 windows of size 1.
-> #drops, y <= 100/k_1 + k_1/k_2 + (k_2-1)
minimizing gives k_1 = (100)^(2/3) which is around 21.5, and k_2 = sqrt(k_1).
so y <= 3 (100)^(1/3) < 13
Answer is 14. Use arithmetic progression.
Start from 14 : If it breaks, use the second egg and try 1 to 13 floors one by one.
If it does not break then, try dropping from 14+13=27th floor and if it breaks then try one by one from 15 to 26 floors
else next try is from 14+13+12=39th floor and so on...
In general : If you have K floors, the solve for N in the
equation : N(N+1)/2 >= K. ( Obviously the least N )
In this case N(N+1)/2 >= 100, so N=14.
So in the worst case scenario, you can figure out the
threshold floor in 14 drops using 2 eggs.
I got the same solution as you, but my friend says the real answer is 12. Not sure why though, but he was the one who gave me the same problem...
I guess we can reduce the number of tries further. if the egg breaks at 14th floor then instead of going one floor each time we can go two floors.
so worst case would be 12 on 100th floor.
Damn. I got this question and the interviewer claimed the correct answer was 10. I guess he was either lying, or just plain didn't know this answer (which makes more sense).
Related to the egg dropping puzzle. The link to the thread:
http://www.careercup.com/question/?q=010FED04-42D4-4DE5-B6B8-DB1BEA4F911E#bd818754afec468f8488dfcc09ec1d5a
Go to the top floor, drop them down the stairwell space between rails calculate 1. speed per second based on mass and gravity and 2. height of building then 3. measure time from release until breakage. calculate distance traveled divided by number of floor hieghts and you'll know the floor of breakage.
I think the problem can be reduced to a binary search problem where the matching case equals to not breaking the egg.
We start with floor 49[(0+99)/2].
If egg breaks then we make upper = 49 and try from floor no. (49+0)/2 = 24 and so on.
when lower = upper we stop the search and the required floor is lower-1
The maximum throws will be ceil(log100) = 7.
ok they'd break on the way to the top, so use the above but shoot them from cannon's up the stairwell
even easier. you stick them in the elevator, and hit the button for 100. then you take a seat at the security desk in the lobby and watch them burst on the security camera.
think its 10(ish).
here goes:
try from floor 10:
->if it breaks go up from 1 until you find the floor it breaks on.
->>if it doesnt break, go to 20:
->>>if it doesnt break, go to 30 etcs.
In all of these if it breaks, test from lowest floor of the current decade, until you get a break.
haven't counted,but max should be 10ish ?
moscovita: the correct answer is 14. why would the interviewer say 10? i don't nderstand why he/she would do that. that shows that the interviewer simply did not understand even his own question.
it would be funny if the interviewer tried to verify his own claim and go "oops! i meant 14. i am glad i am interviewing you and not the other way around."
moscovita: i figured out where the number "10" is coming from.
look at: http[colon]//www[dot]ryanbyrd[dot]net/techramble/?p=16
this says the optimal number is 10. but this is simply wrong.
if you look at the equation he is using:
f(x) = 100/x + (x-1)
the variable x denotes the size of interval, not the number of trials.
the answer 10 is interval size 10, which leads to 19 trials which is worse than the arithmatic series answer 14.
thus, your interview probably did not understand the answer and picked up that magic number somewhere off the web.
The answer is 10.
The main condition you want to satisfy is that the nomatter what happens you take the same number of drops to find the answer.
## Start
- Floor 10 (+10)
+ Breaks (Increment 1-9) ### Total 10 ###
+ Survives
- Floor 19 (+9)
+ Breaks (Increment 11-18) ### Total 10 ###
+ Survives
- Floor 27 (+8)
+ Breaks (Increment 20-27) ### Total 10 ###
+ Survives
- Floor 34 (+7)
+ Breaks (Increment 28-33) ### Total 10 ###
+ Survives
......
So as 10! >50 we know it satifies.
While reading all these answers, I was thinking, wouldn't it be the easist to take both orbs up the elevator going to the top floor. As soon as they break, hit the emergency stop button on the elevator panel. There's your floor.
Somehow I feel that there's more to this question than what's been typed. Is there some restrictions or starting point missing?
The answer should be 13.
Let's assume x is the optimal number of times to try.
1st drop: f1 <= x+1 (because if fails you can use the other egg from the 2nd floor to x)
2nd drop: f2-f1 <= x (again worst case is fail and drop the other egg from f1+1 to f2-1)
3rd drop: f3-f2 <= x-1
...
...
xth drop: fx-fx-1 <= x+2 - x = 2
Add all the inequality up, left side = fx, right side = x(x+1)/2 + x
so fx <= x(x+1)/2 + x
and the xth drop should be >= 100, thus
x(x+1)/2+x >= 100
Solving the equation, you can get x>= 13
Any solution less than 13 can be proved wrong.
It does not prove anything, because there are min 3 mistakes in the solution. The main mistake is that fx cannot be >= 100, since we have only 100 floors. fx <= 100.
Sorry, I was initially wrong because I did not understand some of your statements. I started to solve it in the similar way and understood that You are right, our last drop should be done from a floor which is at least = 100 or greater than 100. Otherwise we cannot prove that we cover all 100 floors with our algorythm.
In my calculations I get:
m(m+1)/2 >= 100
m>= 14. If you start from 13 floor or below - we will not be able to reach the top in the case if N close to 100.
I assume anser is 14.
We cannot start from floor > 14 because if the 1st egg is broken - then we will have to go floor by floor and use more than 14 tries.
If we start from floor <= 13, then we are not able to get to the top. E.g. f1=13,f2=25,f3=36...f13=91.
Min num of drops is 12 because in the worst case its going to be the 100th floor,
start from floor 14 , then 27 , then 39 and so on until u reach floor 99....you would have exhausted 11 tries and then the only floor left is 100 .....therefore 11 + 1 = 12 tries
I can drive this to min count = 12, here is the explanation.
Let's think abt worst case, which is 100th floor
Take 15 floor difference,
15, 30, 45, 60, 75, 90, 105
First egg will break @ 7th try
Now, i know another egg will break from 91 to 100.
start with 92, 94, 96, 98, 100
if it breaks at 92, we know the answer is 91.
So total try = 7 (15, 30, 45, 60, 75, 90, 105) + 5 (92, 94, 96, 98, 100) = 12
You are wrong, if no breaks on 90th floor and breaks on 92th floor, how can you know it does not beak on 91th floor?
The following is the procedure that minimizes the drops.
Using the first egg to do a binary search to narrow down the search scope. The first try is to drop the first egg from floor 100/2, it it does not break, the exact N is in the upper half (with a length 100/2), then try floor 100/2 + (100/2)/2, and so on. Suppose the first egg breaks after k tries, then the search is narrowed down to a range of 100 / (2^k) floors. Using the second egg to find out the exact N by starting from the lowest point of that particular range.
Suppose after j drops, the second egg breaks (the exact N is found), then the total drops is k + j with 1 <= j <= 100 / (2^k) and 1 <= k <= log(100).
The worse case number of drops is 50. In other words, if we are not luck (N is 49), the first egg breaks at the first drop (from floor 50), and then we have to try from floor 1 to floor 49 to find out the exact N.
If we are lucky, the minimum try is log(100) = 7.
by Jimmy
Here is the solution for worst case 10.
1st egg drop --> 2nd egg tests until breaks -------worst case
1. 20--------------> 2,4,6,8,10,12,14,16,18 ---- 1+9 = 10
2. 38 -------------> 22,24,26,28,30,32,34,36 -- 2+8 = 10
3. 54 -------------> 40,42,44,46,48,50,52 ------- 3+7 = 10
4. 68 -------------> 56, 58,60,62,64,66 ---------- 4+6 = 10
5. 80 -------------> 70,72,74,76,78 ---------------- 5+5 = 10
6. 90 -------------> 82,84,86,88 -------------------- 6+4 = 10
7. 98 -------------> 92,94,96 ------------------------- 7+3 = 10
8. 100 ---------------------------------------------------- 8 = 8
You guys are assuming that you can use the broken eggs!!
- Pico January 20, 2007Eg in axmt's case If the egg breaks on the 50th level and the second broke on 25th then there is no was of knowing if the egg broke on lower floors...
Here's my algo:
1)Divide the floors in X interval and drop egg A once from each interval.
2)If A breaks in a particular interval, drop B from each floor in that interval in upwards direction.
3)Total drops will be (100/X)+X-1... minimize this function (differentiating and equating to 0) and we'll get X=10.
==> We'll get the value of N in 19 drops
Am I missing something here?