Number of drops

This is the updated/correct solution.  Thank you to several community members for pointing this out.


Problem:  You are given two identical cell phones and told to test them to see what is the highest floor of a hundred story building that they can be dropped from before they break.  What is the strategy for the minimum number of drops required and what is that number?


Solution:
Let's start by asking some clarifying questions to ensure that we don't go off down the wrong path.  - First, are all the floors the same height?  Yes
- Do we have to account for that the cell phone may land differently, in a different spot with a different hardness, or in different atmospheric conditions (like wind)?  No.  Assume that the only variable that will influence whether a cell phone breaks or not is the floor it is dropped from
- Can we retest a broken cell phone for any additional information?  No, once a cell phone is broken it can no longer be used usefully


These are good questions to ask.  They show your interviewer that you're thoughtful, do not necessarily assume conditions not stated and do not want to try to solve a problem without fully understanding it.


Now that we have a better view of the problem, let's try to think of a potential solution to this problem.


Well, we could start at the bottom floor and go up one floor and drop the phone. When the phone broke, we would know that we were at the top.  In the worst case, this would take up to 100 floors and 100 drops.  O(n).


It's good to get a working solution, but this is clearly non-ideal.  For starters, we didn't use our second phone.  


A simple optimization that we could imagine when starting this is to skip by 2s:  test on floor 2, 4, 6, 8,...


If the phone breaks, we can then test the phone on one floor lower.  Then, the answer is one lower, else if it survives, the answer is that floor.


This results in a max number of drops of potentially 51 if the top floor is the answer.  Still O(n), but much better.  


At this point, think more about the optimization.  We skipped floors, and then went back and tested some we had skipped once we found a range of a not-broken floor and a broken floor.


Previously, we only skipped one floor, but we could skip more.  Let's try for an example, skipping 3 floors:  We start by testing on floors:  3, 6, 9, 12...


Well, the worst case here is floor 90, which would be 34 drops potentially.  So, it seems that skipping more floors, then going back and testing one-by-one from the last good floor is a good strategy.


It appears that skipping more floors reduces the number of drops, so let's try skipping 50 floors.  Here, the worst case is now 51 floors (floor 99).  So, clearly, skipping too many is not always good.


So, there seems to be an optimal number of floors to skip.  If you work from here using math or simply trying bigger and smaller numbers, you'll get to an answer of about 10 (11 and 9 yield similar answers).


This gives a worst case of 19, which would be if the 99th floor were the fail floor.  


It's tempting to stop here, and frankly, I have egg on my face for previously publishing an answer where I did.


There is a better solution.


Let's try to figure it out by doing some examples where we establish the min/max range by skipping 10 floors each time.  Try 9.  


We would test:
10:  fail
1: pass
2: pass
...
8: pass
9: fail.


This would be a total of 10 tests.


Essentially, if we skip 10 floors each time, the worst case is always the number ending in 9, and the worst case floors take one more test each time:


9:  10 tests
19:  11 tests
29:  12 tests
...
99:  19 tests


Well, think about one of the assumptions that we had earlier -- always skip the same number of floors to establish a min/max range.  There is no proof that this is the right solution.  In fact, it looks like by doing this, we always have essentially one more test as we go higher.  However, what if we used the fact that we essentially have 'tests' we can do early in a bigger range as we have not used them up to establish the range.  In fact, on each subsequent upping of the potential min/max range, we lose 1 test, to establish the range.


Now, what if we accepted a larger min/max initially and then narrowed it as we went up.  This would get around the problem of always having to get worse as we go higher.  This hints at an optimization to our initial strategy.


As an example, let's try skipping 17 floors and then reducing the range by one each time (one better than our current best result).  Note we should try 17, not 18, so that we are never worst than 18.  This way, the highest range of the min/max will always yield 18, but that is better than our current best result


We could establish min/max ranges of:
1...17
18...33
34..48
....


Well, this works and we can get better than 19.


Now, keep trying smaller min/max ranges to start out with initially.  If you go too small, you can't get to the top.


If you keep trying, or use math, you'll eventually narrow in on skipping 13 floors initially, which gives you a worst case of 14.  This is quite a bit better than our initial case of 19.


/* Thank you to the community for help getting this right.  Apologies for my previous incorrect answer.  Noah */