## Microsoft Interview Question for Software Engineer / Developers

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

My solution is 11.

Suppose the solution is dropping the egg from k. If the egg breaks, then we use the second egg to do binary search. Then the maximum number of drops would become 1 + k/2. Knowing this number, we follow the same idea as dropping two eggs.

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

here, suppose N = 100

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

How about dropping it from 10, 20, 30....so on...If it breaks at 20 and not at 10...Do a linear between 10 and 20...
Minimizes the eggs broken to 2.

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

This is not working. Suppose the egg is broken in 90's level. Then you will have to throw 9 + 4 + 1 = 15 times to detect the lowest level that could break the egg.

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

11

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

I can think of 14 tries can you please tell me more about solution of 11 tries.

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

matrix[i][j] = min(max(matrix[i-1][m], matrix[i][N-m])), 1 < m < N

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

Assume N = 100, mine requires 9 times. The first egg is tried on 36, 64, 85, 100. Depending on the result of first egg drop, the second egg is tried on (8, 15, 21, 26, 30, 33, 35), (43, 49, 54, 58, 61, 63), (70, 75, 79, 82, 84), (90, 94, 97, 99). The third egg is just for linear search. The worse case is 9 drops, though it might be possible to reduce to 8 times.

The idea follows from the two-egg dropping problem and this problem is reduced to solving the following inequality: sum_{k=1}^{n} k + sum_{k=1}^{n-1} k + ... + sum_{k=1}^{1} k > 100.

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

right!!

for the case of N-stories building, one has to find a
minimal x satisfiying the following equation:

sum_{i=1}^x (i*(i+1))/2 = x^3/6 + x^2/2 + x/3 > N

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

log2(N) tries are needed normally... but what is the trick of 3 eggs, i did not understand that...

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

Friend ur solution is not clearer to me could u plz throw more light on it.

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

Following are the key thoughts of mine:
1. this problem is a search algorithm. For a stable algorithm, my beliefe is the equal spliting is the best approach
2. Say D is the difference between each search step. For 3 eggs scenaio, the worst cases are:
a. O(Step1) = N/D (ceiling)
b. O(Step2) = O(Step1) = N/D (ceiling)
c. O(Step3) = D/O(Step1) = D/(N/D) = D^2/N (ceiling)
then: O(Step1)+O(Step2)+O(Step3) = 2*N/D + D^2/N
Calculate the D which make the total cost function min.

Detail:
First derivative = 0
=> -2*N/D^2 + 2*D/N = 0
=> D^3 = N^2

In case N = 100 => D = 22

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.