I have a fun riddle for you that I was asked in a job interview onece. “There is a frog at the bottom of a flight of 10 steps. (he is on the ground, step 0, not step 1). This frog can traverse the stairs in steps of 1 or 2 or any combination thereof. He may only travel up, never down. In how many different ways can the frog traverse the stairs assuming that he must land exactly on the 10th step at the end of his journey? (ie, he cannot overshoot 10 and try for 11, and he must climb all 10 stairs)” The answer is…. ]]>

“There is a building with 100 stories. You have one plate right now and you want to determine the marginal floor from which if you dropped the plate out the window it would break. Obviously you cant start at the top, buecause if it breaks at the 100th floor then you don’t know the marginal case (ie. it may have cracked at the 43rd floor but not the 42nd floor and the 43rd floor is then the marginal case). So with one plate you have to start at 1 and move up until it breaks, thus the worst case is 100 trials.

“Now assume that you have 2 plates, what is the optimal method such that you minimize your worst case # of trials, while ensuring that you will eventually find the answer?

“Secondly, assume you have an unlimited number of plates, What is the minimum worst case # of trials?”

]]>