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




Comment hidden because of low score. Click to expand.
2
of 2 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?

- Pico on January 20, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- sam on February 03, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- segue on February 17, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This seems the best answer.

- Manu on June 07, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good answer !

- Ashish on February 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- kumar on March 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- kumar on March 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- kumar on March 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- kumar on March 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- kumar on March 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- kumar on March 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- kumar on March 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- kumar on March 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- kumar on March 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- kumar on March 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- kumar on March 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous on July 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- monika.agarwal712 on January 05, 2013 | Flag
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.

- Nex3 on December 13, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- avic on January 03, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- The Paul on January 14, 2008 | Flag
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.

- wykurz on December 13, 2006 | Flag Reply
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

- huyminh92 on December 16, 2006 | Flag Reply
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!

- axmt on December 30, 2006 | Flag Reply
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.

- i2h on January 05, 2007 | Flag Reply
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.

- hammou on January 24, 2007 | Flag Reply
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.

- movaali on January 29, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In that case why do you need two eggs ?

- Thirumalai on February 15, 2007 | Flag
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..

- Anonymous on September 05, 2008 | Flag
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

- andytwigg on February 15, 2007 | Flag Reply
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.

- Thirumalai on February 15, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- segue on February 17, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Thirumalai on February 20, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- vijay on January 21, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- vijay on January 21, 2008 | Flag
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).

- moscovita on February 22, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Thirumalai on February 22, 2007 | Flag
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

- Anonymous on February 22, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- J.O. on April 11, 2007 | Flag
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.
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.

- Li Ze on March 19, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

but we have only 2 eggs

- ah on March 19, 2007 | Flag Reply
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

- Anonymous on April 11, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- jborb on September 11, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I love that answer

- Anonymous on October 09, 2007 | Flag
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 ?

- sjk on April 14, 2007 | Flag Reply
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.

- Sukku on April 17, 2007 | Flag Reply
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."

- nunbit romance on June 09, 2007 | Flag Reply
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.

- nunbit romance on June 09, 2007 | Flag Reply
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

- Vamsi on December 04, 2007 | Flag Reply
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.

- Yo on December 12, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Thirumalai on January 03, 2008 | Flag
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?

- HF wanna be on March 13, 2008 | Flag Reply
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.

- Alex on April 02, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- muld4 on September 23, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- muld4 on September 23, 2008 | Flag
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..

- Anonymous on September 05, 2008 | Flag Reply
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.

- XYZ on September 17, 2008 | Flag Reply
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.

- NITW Guy on October 26, 2008 | Flag Reply
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

- Anonymous on November 11, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Raja on November 11, 2008 | Flag
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

- SV on February 16, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- anonymous on April 25, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- rajatknit on January 16, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

the same old dropping ball problem...

- Anonymous on July 17, 2009 | Flag Reply
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

- Junqiang Jimmy Liu on July 10, 2010 | Flag Reply
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!

- kabir on July 12, 2012 | Flag Reply
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.

- Sujith on September 13, 2012 | Flag Reply
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

- akshay on May 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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: on June 12, 2012 | Flag


Add a Comment
Name:

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

Books

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

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More