Interview Question for Software Development Engineer Intern at Amazon.com:

I figure out a O(x) solution, where x is n/2, but it's still O(n) theoretically.
My interviewer insist there exists a better answer (in terms of time complexity). But he refuse to tell me the answer nor hint, for example, what will that time complexity be in this solution. I wish someone can help on this problem.

I am thinking if you have 2 bottles you
1. use the O(log n) approach until the bottle breaks to find better bounds
2. use linear search on those new bounds to find the answer

So worst case is O(n/2) best case is O(log n)

The best solutio with two bottles is radical N.

Well you could keep doubling the height 1,2,4,8... so on till the first bottle breaks. Then start the linear increment for the next bottle from the point before the previous bottle broke. Say it broke at 32, then use 16 as the new start and use linear increments of 1ft 17,18,19..so on.

Increase height by squareroot of N with first bottle
linear search with second bottle
O(n^1/2) complexity

I have had this question before.
Assume you have a number, D, that is the max bottle drops you can use to find the answer.

To do this you would start at floor D and drop the bottle. If it breaks, then you do a linear search from floor 0 to D with the other bottle (thus finding the solution in, at most, D attempts).

If it doesn't break, move up D-1 floors. It must be D-1 because if the bottle breaks, you will only have D-1 attempts left to do the linear search. This is because you used one attempt back at the previous floor. If it breaks you do the linear search from floor D to your current floor.

You repeat this process (always moving up one less floor) until you run out of attempts.

If you write out this in an equation, the highest floor you can get to is given by the sum:
D(D+1)/2 >= N

Solve for whatever particular N, and you get the best possible D.

For example, on a 100 story building you can find the highest floor with at most 14 drops.

Use Binary search until 1 bottle breaks then perfrom linear search.