| [Job Interview] | |
Computer Science Interview Question - Two Eggs And 100 Story BuildingHere is the main point of this problem. If you broke one egg, you will need to do a linear search to find the floor. So you pretty much have to go from the lowest to the highest, and the worst is the total number of floors in the linear search with the second egg plus the drops you have done with the first egg. So the whole question grinds up to how to make use of the first egg to reduce the linear testing using the second egg. This problem can be solved by thinking backwards from the answer. So, here are the steps: 1. Take N for the answer 2. The best choice will be to start with floor N first. - if the egg breaks, do a linear search starting from 1 to N-1, guaranteeing a solution in N attempts. - else go to N + (N-1) floor. 3. Continuing in this way, with N attempts, we can cover sum(N + N-1 + N-2... 2 + 1) floors. Thus we will need to cover 100 floors, so N *(N + 1) / 2 > 100 N = 14, so the answer is 14 maximum drops and we can find the floor. The computer algorithm would be like this. Drop first egg from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100... (i.e. move up 14 then 13, then 12 floors, etc) until it breaks (or doesn't at 100). Lastly, to prepare for algorithm/data structure interviews, here are some books I would highly recommend, if you can read them all in detail, you are gold in getting any jobs at Google/Amazon/Microsoft/Facebook/Twitter, etc. or any software company: My Recommendation On Algorithm Interview Books | |
| posted by Jian | |
| comments (4) |
| 1# visitor 2011-03-26 04:59 | |
| The solution to this problem is sort of tricky. Well, for someone who see it for the first time. This is a classical problem. It used to be a Goldman Sachs interview question. | |
| 2# Morten Lærkedal 2011-10-29 12:59 | |
| And what if you have 3 eggs ? | |
| 3# Jian 2011-10-30 22:57 | |
| In fact, I need to think twice again. If there are 3 eggs, then you probably would need less than 14 tries... | |
| 4# Jian 2011-11-03 23:11 | |
| @Morten, With 3 eggs, you could use the extra egg for binary divide-and-conquer. Here is my thoughts: 1) Use the first egg to drop from floor 50. The worst case is it will be broken. 2) Now we try with the remaining 2 eggs, for floor 1 to 49, using the same algorithm above. N *(N + 1) / 2 > 49, so N = 11. Since we already used one egg in 1), so, the maximum drops would be 12. So, with 3 eggs, it is slightly better than 2 eggs. It seems there is a diminishing return on using more eggs. Overall, in terms of solving a computer science problem, certain optimization is better, but too much would be overkill. | |
 |