Sunday, July 24, 2011

A classical puzzle: 2 eggs

This is frequently asked by Goldman and Sachs: You are given 2 eggs.You have access to a 100-story building. Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100th floor. Both eggs are identical. You need to figure out the highest floor of a 100-story building an egg can be dropped without breaking. The question is how many drops you need to make. You are allowed to break 2 eggs in the process.

Solution:

1st attempt: linear search. 100 tentatives, why 2 eggs?

2nd attempt: binary search, if it breaks go linear with the second one. this means 1+ 49

3rd attempt:

start at floor x, if it breaks make a sequential search 1.. x -1, else go to x+x-1 because you have already used one egg (-1) --> x + x - 1 + x - 2 + ... + 1 = x ( x + 1 ) / 2 = 100 --> x = 14

No comments:

Post a Comment