## Microsoft Highbridge Capital Interview Question for Software Engineer / Developers Financial Software Developers

• 0

Comment hidden because of low score. Click to expand.
1
of 3 vote

You guys are assuming that you can use the broken eggs!!
Eg 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?

Comment hidden because of low score. Click to expand.
0

gr8 somebody is on the same wavelength as i am :). I think this is the right answer

Comment hidden because of low score. Click to expand.
0

I 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.

Comment hidden because of low score. Click to expand.
0

This seems the best answer.

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

why do we need to drop B in upward direction?????

Comment hidden because of low score. Click to expand.
0

why do we need to drop B in upward direction?????

Comment hidden because of low score. Click to expand.
0

why do we need to drop B in upward direction?????

Comment hidden because of low score. Click to expand.
0

why do we need to drop B in upward direction?????

Comment hidden because of low score. Click to expand.
0

why do we need to drop B in upward direction?????

Comment hidden because of low score. Click to expand.
0

why do we need to drop B in upward direction?????

Comment hidden because of low score. Click to expand.
0

why do we need to drop B in upward direction?????

Comment hidden because of low score. Click to expand.
0

why do we need to drop B in upward direction?????

Comment hidden because of low score. Click to expand.
0

why do we need to drop B in upward direction?????

Comment hidden because of low score. Click to expand.
0

why do we need to drop B in upward direction?????

Comment hidden because of low score. Click to expand.
0

why do we need to drop B in upward direction?????

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0

anonymous this is the exactly right solutions and what it thought too

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

they have not taken into
consideration that we have
only two eggs to find out N.

Nex3 seems right to me.

Comment hidden because of low score. Click to expand.
0

Start at Floor 10 then 20 then 30 etc when the first egg breaks move down nine floors and go bottums up. Worst case 19 drops foor floor 99 being the breaker.

Comment hidden because of low score. Click to expand.
0
of 0 vote

i did it in 14 drops. hint - use sqrt(N), 10, drop one egg each 10*k - th floor ... and try to equalize number of drops for all cases.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I don't think use sqrt(n) works. Let's say you drop at 10th floor first, then it breaks. Then you drop from sqrt(10) which is 3rd floor. If it breaks, so we know that n is 1 0r 2, but we dont know exactly what it is

Comment hidden because of low score. Click to expand.
0
of 0 vote

N = 7 i.e. ceiling of lg 100 (lg = log to base 2)
e.g. if N = 4 then this is how to do it..
start at mid i.e. 50 then 25,12,6,3,4 Hence proved!

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

let's suppose that u r right, if the egg will break in the fifth interval( x=5 ), so u dont have to count the remaining intervals, i mean sixth .....and u just try to count inside that interval witch is the fifth.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

In that case why do you need two eggs ?

Comment hidden because of low score. Click to expand.
1
of 1 vote

Our dear friend movaali will take d other egg home fry it and eat it..

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

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...

Comment hidden because of low score. Click to expand.
0

Ask him how he got to 12 and get him to verify it manually
in the worst case scenario.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

sorry not on 100th it will be on 96th.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

Comment hidden because of low score. Click to expand.
0

I am pretty sure and convinced that 14 is the correct answer. If somebody gives a better answer than this, then
I would like to verify that manually for the worst case scenario.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Related to the egg dropping puzzle. The link to the thread:

http://www.careercup.com/question/?q=010FED04-42D4-4DE5-B6B8-DB1BEA4F911E#bd818754afec468f8488dfcc09ec1d5a

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the problem can be reduced to a binary search problem where the matching case equals to not breaking the egg.
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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

but we have only 2 eggs

Comment hidden because of low score. Click to expand.
0
of 0 vote

ok they'd break on the way to the top, so use the above but shoot them from cannon's up the stairwell

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

I love that answer

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

In this case, the worst case value will be 19. eg the required floor is 99. 10-90(9 attempts), then u have to proceed in linear manner to reach uptill 99. Knowing the fact that we have only 2 eggs.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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."

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I cogitate the interval 10 is right.

``www.ryanbyrd.net/techramble/?p=16``

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

Follow your process and we reach only upto 55 floors without breaking ( if 10 is the optimal num ber of the drops )...
Try out manually yourself and see if the number 10 works for if the required threshold floor is for example 75...

Thanks

Thirumalai
------------------

Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Whats the crap about.. An orb breaks when u drop it from certain floor.. Its not that there is some mechanism which causes the orb 2 burst as soon as it reaches its floor..
Refer 2 the egg dropping problem..

Comment hidden because of low score. Click to expand.
0
of 0 vote

---If the size of each step is constant, then N=10, the worst case is 19 (10+9). As "Vamsi " said.

---If these is no such constraint on the step size, that being said, the size of each step can change, the worst case is 15. As "Thirumalai" said.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Keep doing binary search till the first egg breaks. Once done, do a linear search from the opposite side till the second egg breaks. Once the second egg breaks, you know the answer.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

But if it breaks on floor 14, you still have to check floors 1 through 13. That's 13 drops.

The sequence is 14, 27, 39, 50, 60, 69, 77, 84, 90, 95. 99. At floor 99, you've dropped it 11 times. Plus you have to check 96, 97, 98 if it breaks. That's still 14.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
0

if it breaks on 15th ( @ 1st try only ), you have to start from 1 through 14th to see if the 2nd egg breaks on 14th or below. If it does not break in 14 drops, which means 15th floor is the floor where it starts breaking, so total will exceed 14.

Comment hidden because of low score. Click to expand.
0
of 0 vote

the same old dropping ball problem...

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

N=0. why are you guys wasting your brains so much on breaking eggs and calculating them?
have you ever seen an egg surviving after falling from even the 1st floor? save both your eggs and go home gentlemen!

Comment hidden because of low score. Click to expand.
0
of 0 vote

Why 2 eggs? I think there should be 'n' number of eggs. Answer is 14 as thirumalai said.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

Suppose the answer is 3rd floor ...
so as per your solution
this is what is going to happen
first egg will break on floor 20th
second will break on floor 4th
so you still dont know is 4th floor your answer or 3rd

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.