There is a building with 36 floors. It is known that, starting from the floor "x", if a coconut is dropped it breaks.
A boy is given 2 coconuts. Using these 2 coconuts, he is supposed to find the least floor "x" from which it starts breaking, when dropped down. Note :- The boy can break both the coconuts.No problem. But his aim is to find the floor "x" using the minimum drops !!
Example :-
A gut-feel-approach tells you that :-
Let the boy goto floor 1. Then let him drop the coconut. It breaks ! Then x is found and x = 1.
If it doesnt break goto floor #2. Then let him drop the coconut. It breaks ! Then x is found and x = 2.
:
:
If it doesnt break goto floor #36. Then let him drop the coconut. It breaks ! Then x is found and x = 36.
Bigger clue :- Think binary search.
Biggest clue :- n-nary.
5 comments:
am too non-computer sciene for algos ;-)
This is typicall given with eggs instead of coconuts; but well, I'd prefer it this way anyday.
Yeah, n-ary is the way to go.
There is another related problem in the same vein. Given an infinite array (or an array of unknown size) with zeros in the beginning, and ones in the end, you have to find out the place where the zero to one transition happens.
Google had the egg-building questions in it's interviews here, and also generalized it to N floors and M eggs, whose solution I have been told is Mth root of N.
Oye zeeds, I think it is time to insert a MBA joke here. But MS is even easier pickings :D, or say MTech.
I was asked the generalized question that Teju mentions, during my interview in Y!. Didn't get the Mth root of N, that should be interesting to derive.
Doesnt Teju sound Geekish here :) WOWWWW I love it this way :)
Well Richie, I think its time to loot some HK casinos
paapu nice photo, especially the broken coconut...
richie does that qualify as an MBA joke ;-)
Post a Comment