## Microsoft Interview Question for Software Engineer / Developers

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

There are several strategies in solving this problem.
But Throw the first ball every 10 stories gives the best minimum number of throws, it guranteen that within 20 times, the target story can be found.

Suppose every K floors we will throw the first ball,
the maximum throws needed is bounded by 100/K+K,
the minimum reaches when K=10.

Other strategies might be more powerful, but they can't promise a minimum number of throws.

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

u can do it in min. of 14 throws
throw the ball 1st ball from 14th floor if it breaks thn use other ball n start throwing starting frm 1st floor
if it doesn't break, thn throw the 1st ball from 27th, if it breaks thn start throwing other ball from 15th floor
and so on keep throwing 1st ball from 39th, 50th, 60th, 69th, 77th, 84th, 90th, 95th, 99th floor.

so even in worst case comparisions r 14

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

bansal.abhi is right.

Assuming the minimum number of throwing is x, we have to begin throwing from x floor. Then if the glass is not broken(worst case), to make the minimum throw x, we can only begin from x + (x-1) floor. Keep throwing until xth throwing, at this time, no floor should be left. So, we have x + (x-1) + (x -2) + ... + 2+1 >= 100. That is, x*(x+1)/2 >= 100. We can get minimum x = 14.

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

How about trying from least floor upwards?

E.g: 2, 4, 8, 16, 32, 64, 100.

On the lower end it is now possible to find the least floor the 2nd egg breaks with minimal try.

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

VIgorous:
In your strategy, it should be: 100/k + (K-2) right? Because we covered, 100 and 90 which are multiples of 10. In case if the ball breaks on 100th story, then we keep trying from 91st floor onwards to 99th floor, which amounts to 8.

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

Is this cheating?

Stand on the first floor.
Throw it upwards as hard as you can.
Sell the other glass ball
Return

Minimum throws =1

:D

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

The solution to the above problem is as follows:
You have to divide the total no of floors into groups in such a way that the worst case never increases across the groups. For e.g. lets say u decide to have the first group as floors 1 to 14. In the worst case this will take 14 trials. Now you have to choose the second group if you choose the second group of the same size as of the first group then the worst case will have 15 trials. So you have to chose the next group with size less by one than the size of first group. So you will end forming groups of sizes 14,13,12----1 which is nothing but a series. So what should be the optimum size of the first group. That should be equal to the no. of groups you can divide all the floors into. With 14 groups you can include all the 100 floors. If you think of 13 as the solution then its not possible as you can not divide 100 floors in 13 groups and ensuring that each group size is less by one than the previous group.

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

Can't we try binary search? Throw the ball from the 50th floor. If it breaks try from the floor set below it an recurse, else throw from the floorset above it and recurse. Ultimately, you will find a floor at which the recursion terminates but the ball does not break. It neighbouring higher floor is the correct answer. This takes only O(logn) time

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

I agree with your solution rspate. But atleast floor(logn) balls should be broke before you arrive at the correct floor.
However, we are given only 2 balls.

Is the solution appropriate to this question ?

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

guys the solution is simple ...and the answer is 14. this is the old question...can some one explain me the generalized solution for this porblem i.e Say we have n eggs and d-floor building then in how many drops we can find the max floor...plz help!

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

Hey friends the answer is 14 bcoz the minimum "m" turned out to be 14 in m(m+1)/2 >=100
so if u have n eggs u can use them to divide the inetrval into 2 wid each egg until the last 2 eggs remain. with which u can use the above formula m(m+1)/2 >= d/(n-2) to find the minimum m. So the answer would be a maximum of m+n-2 eggs.
Plz correct if i am wrong.
:)

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

http://www.thecareerplus.com/?page=resources&cat=150&subCat=10&qNo=2

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

100 storey building and glass balls,what are the minimum number of balls required to decide the floor from which the glass ball will not break

Add a Comment
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.

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