Google’s Two Egg’s Problem

floor-n-drop-eggs

It is said a Google Interview Question: You are given two eggs to test the minimal height (from 1 to 100) the egg will break if dropped at that height. If the egg does not break, it can be reused to test another height. So what is your strategy to minimize the number of tests at worst cases? Two eggs are exactly identical.

What is the worst case? It means that you take a maximum number of tests to figure out the maximum safe height e.g. n that eggs won’t break if dropped at that height i.e. the eggs break if dropped at height n+1. If you have only 1 egg, you will need worst case 100 tries to figure out the answer.

The naive solution is to test from height 1 and then 2, and then onwards.. If the egg does not break at height n but breaks at height n+1, we know the safe height is n. However, this only makes use of only 1 egg and the worst case is 100 if the safe height is 100.

How about we try first height 50? If the egg breaks at height 50, we know the answer is from 1 to 49 otherwise the answer is from 51 to 100. If the egg breaks at 50, we only have one egg left (and we must try 1, 2, … ), therefore, the worst case will be 49 + 1 = 50 times if the safe height happens to be 49. Under such circumstances, it is worse than the above naive solution, which takes 49 times. If the answer is from 51 to 100, we have a smaller size problem, which is 2 eggs and 50 heights to check. We can then try at height 75 …the worst case in this will be larger than 50. The overall worst case will then be 50.

How about we try first height 33? If the egg breaks at height 33, we know the answer is from 1 to 32 otherwise the answer is from 34 to 100. The worst case if first egg breaks is 32 + 1 = 33. If the first egg does not break, we have a sub-problem: 2 eggs and 67 heights to check.

Do you see this going to some direction? If we have f(n) meaning the worst case if we drop the egg at height n.

Given n heights, If the egg breaks at height i in [1, n], we have i-1 tries. Otherwise, we have two eggs, and we have n – i heights to try, which is the sub problem. So put these two cases together, we have

f(n) = min(1 + max(i – 1, f(n – i))) where i is from 1 to n and
obviously, we have f(1) = 1

Translated to C++:

// cached results;
vector<int> cache(101, 0);

int f(int n) {
    if (n == 1) {
        return 1;
    }
    if (cache[n] > 0) { // if we have computed sub problem...
        return cache[n];
    }
    auto v = n + 1; 
    for (auto i = n - 1; i >= 2; -- i) {
        v = min(v, 1 + max(i - 1, f(n - i)));
    }
    cache[n] = v;  // cache the smaller size problem.
    return v;
}

We cache the intermediate result in the STL::vector otherwise it will take forever to find the answer. The computer problem prints answer 14. Caching the intermediate results is one simple step to transform recursion into dynamic programming.

See also: Egg Drop With 2 Eggs and N Floors

You may also like: 谷歌的扔鸡蛋问题

–EOF (The Ultimate Computing & Technology Blog) —