How to interpret the intelligence interviews of Microsoft, Google and Apple?

There is a 100-storey building. If you drop it from the nth floor or higher, the egg will break. It won't break if you fall from the floor below the nth floor. Here are two eggs for you. Please find out N, and it is required to throw the eggs at least in the worst case. ?

We found that no matter how eggs 1 (eggs 1) are thrown, eggs 2 (eggs 2) must be thrown down between the "broken floor" and the next unbreakable highest floor, layer by layer (from lowest to highest). For example, if the egg 1 was dropped from the 5th floor and 10 floor, but it was dropped from 15 floor, then in the worst case, the egg 2 must be dropped from 1 1, 12,/kloc.

Specific practices

First, we try to throw eggs from the 10 floor, then from the 20th floor, and so on.

Q If the egg 1 is broken after being thrown downstairs for the first time (10 floor), it needs to be thrown 10 times at most.

Q If the egg 1 is broken after being dropped for the last time (100 floor), it should be thrown 19 times at most (10,20, …, 90, 100 floor, and then 9/kloc-0.

That's not bad, but we only considered the absolute worst case. We need to carry out "load balancing" to make the number of eggs thrown out more evenly in these two cases.

Our goal is to design a method of throwing eggs, so that when throwing eggs 1, it will be broken whether it is thrown downstairs for the first time or for the last time. The more stable the times, the better.

(1) The perfect load balancing method should be that no matter which floor the egg 1 is thrown from, the number of times of throwing the egg 1 plus the number of times of throwing the egg 2 at any time is the same.

(2) If there is such a throwing method, every time you throw a little more eggs 1, you can throw a little less eggs 2.

(3) Therefore, every time the egg 1 is thrown, it is necessary to reduce the number of times that the egg 2 may need to be thrown downstairs. For example, if the egg 1 is thrown from the 20th floor and then from the 30th floor, then the egg 2 may be thrown 9 times. If we throw eggs 1 again, we must reduce the number of times we throw eggs 2 downstairs to 8 times. In other words, the egg 1 must fall from the 39th floor.

(4) Therefore, the egg 1 must be thrown down from the X layer, and then the X- 1 layer is added up ... until it reaches the 100 layer.

(5) solve the equation x+(x-1)+(x-2)+…+1=100 to get x (x+1)/2 =100 → x = 6544.

Let's start with layer 14, then layer 27, then layer 39, and so on. In the worst case, we have to throw eggs 14 times.

Just like solving many other maximization/minimization problems, the key to such problems lies in "balancing the worst case". ?