By Long Luo

微软、Google 等科技公司的面试题库中，流传着许多经典问题。小时候在杂志上看过微软那道著名的面试题 ——“为什么下水道井盖是圆的？”，当时觉得这类问题十分有趣，因为它考察的往往不是知识储备，而是分析问题的思维方式。

最近，我又重新翻到了 Google 的一道经典面试题 —— 双蛋问题（ \(\textit{Two Eggs Problem}\) ）或者说鸡蛋掉落问题（ \(\textit{Egg Dropping Puzzle}\) ）。与井盖问题不同，这道题更偏向数学推导与算法优化，但同样充满巧思。乍看之下，它只是一个简单的试验设计问题；深入分析后却会发现，其中隐藏着相当优美的最坏情况分析思想，是一道非常值得细细品味的经典题目。

这道题的原文如下：

一个鸡蛋

如果只有 \(1\) 个鸡蛋，问题解法非常简单。我们别无选择，只能从一楼开始逐层测试。用这种方法一定能找到鸡蛋安全掉落的最高楼层：该楼层就是鸡蛋摔碎楼层的楼下一层。

那么在最坏情况下，最少需要尝试多少次？答案就是 \(100\) 次。因为最坏的情况就是临界楼层为第 \(100\) 层。如果鸡蛋在第 \(100\) 层摔碎，则临界楼层为 \(99\) 层。

两个鸡蛋

如果有 \(2\) 个鸡蛋，那么问题就变得有趣起来。此时我们允许试错一次，大家很自然会想到二分查找，但在这里并不是最优方案。如果最高安全楼层是 \(49\) 层，一开始就在 \(50\) 层扔下第一枚鸡蛋，鸡蛋直接摔碎，之后只能逐层测试 \(49\) 次才能得到答案，总计尝试 \(50\) 次。

既然一开始从 50 层扔下不可行，那么很容易想到隔少一点楼层扔下行不行呢？如果我们每隔 \(10\) 层测试一次的话，那么依次在 \(10, 20, 30, 40, 50\) 层扔鸡蛋，鸡蛋在 \(50\) 层摔碎后，再逐层测试 \(41 - 49\) 层即可得出答案，全程仅需 \(14\) 次尝试。由此可见，每隔 \(k\) 层测试一次是可行的思路。在这种策略下在最坏情况下的尝试次数：最坏场景是连续跳层直到鸡蛋摔碎，之后只能用仅剩的一个鸡蛋，在最后一段长度为 \(k - 1\) 的区间内逐层排查。

那么尝试次数计算公式为：\(\lfloor \dfrac {100}{k} \rfloor + (k - 1)\) 。注意到 \(\dfrac {100}{k}\) 和 \(k - 1\) 是此消彼长的关系，在大概 \(k = 10\) 左右有极值，当 \(k = 8, 9, 10, 11, 12, 13\) 时，计算得到最坏尝试次数为 \(19\) 次。

那这个问题的正确答案是扔多少次呢？

递归

如果我们只是想知道鸡蛋最少要扔多少次的话，我们可以通过写程序来得到答案。类似汉诺塔问题，解决此类问题的最佳方法就是递归法，同一楼层我们取最小值就行，代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

private static int eggDropping(int eggs, int floors) {
    if (eggs == 1) {
        return floors;
    }

    if (floors == 0 || floors == 1) {
        return floors;
    }

    int minTries = Integer.MAX_VALUE;

    for (int i = 1; i <= floors; i++) {
        minTries = Math.min(minTries, 1 + Math.max(eggDropping(eggs, floors - i), eggDropping(eggs - 1, i - 1)));
    }

    return minTries;
}

这个递归法非常耗时，在个人电脑上运行了很长时间也没有执行完。因为递归法的时间复杂度是 \(O(2^n)\) ，显然 \(2^{100}\) 是个天文数字，我们可以缓存下每个楼层的最小值，优化算法，代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

static Map<Long, Integer> memoMap = new HashMap<>();

private static long getKey(int eggs, int floor) {
    return ((long) eggs << 32) | floor;
}

private static int eggDroppingWithMemo(int eggs, int floors) {
    if (eggs == 1) {
        return floors;
    }

    if (floors == 0 || floors == 1) {
        return floors;
    }

    long key = getKey(eggs, floors);
    if (memoMap.containsKey(key)) {
        return memoMap.get(key);
    }

    int minTries = Integer.MAX_VALUE;

    for (int i = 1; i <= floors; i++) {
        int worst = Math.max(eggDroppingWithMemo(eggs, floors - i), eggDroppingWithMemo(eggs - 1, i - 1));
        minTries = Math.min(minTries, 1 + worst);
    }

    memoMap.put(key, minTries);

    return minTries;
}

计算得到 \(100\) 层楼 \(2\) 个鸡蛋的情况下，答案是 \(14\) 次。这个 \(14\) 次是怎么扔出来的呢？显然不是刚才每隔 \(k\) 层扔鸡蛋法，那么这个问题的解法到底是怎么样的呢？

到底怎么扔呢？

假设对于 \(n\) 层大楼，在最优解法下，最坏情况也只需要尝试 \(x\) 次就可以覆盖所有楼层，那第一次就应该在第 \(x\) 层扔鸡蛋，这样产生 \(2\) 种情况：

1. 鸡蛋摔碎，就只能逐层测试 \(1\) 至 \(x - 1\) 层，总尝试次数恰好为 \(x\) ；
2. 鸡蛋没碎，下一次就在第 \(x + (x - 1)\) 层测试。如果此时鸡蛋摔碎，再逐层排查中间 \(x + 1, x + 2, \dots, x + (x - 1) - 1\) 楼层，这样总尝试次数依旧是 \(x\) 。

逆向思维下，我们可以先假设最坏情况的尝试次数固定为 \(x\) ，再反推怎么才能不超过 \(x\) 次测试完所有楼层。

于是我们就得到了最优策略：

设在最优策略下，最坏情况最少尝试次数为 \(x\) 。按照上述规则，第一次测试第 \(x\) 层（覆盖 \(x\) 层楼），第二次测第 \(x + (x - 1)\) 层（再覆盖 \(x - 1\) 层），第三次测第 \(x + (x - 1) + (x - 2)\) 层（再覆盖 \(x - 2\) 层）。依此类推，该策略总共能覆盖的楼层数为等差数列求和：

\[ x + (x - 1) + (x - 2) + \cdots + 2 + 1 = \frac {x(x + 1)}{2} \]

若大楼共 \(n\) 层，只需找到满足 \(\dfrac{x(x + 1)}{2} \geq n\) 的最小整数 \(x\) 。

显然有：

\[ x^2 + x - 2n = 0 \implies x = \frac{-1 + \sqrt{1 + 8n}}{2} \]

由于 \(x\) 必须为整数，需要向上取整：

\[ x = \left \lceil \frac{-1 + \sqrt{1 + 8n}}{2} \right \rceil. \]

回到我们的问题，\(n = 100\) , 代入上述方程可得： \(\lceil 13.65 \rceil = 14\) 。

我们也可以轻松写出如下代码：

1
2
3

public static int twoEggDrop(int n) {
    return (int) Math.ceil((Math.sqrt(1 + 8 * n) - 1) / 2);
}

多个鸡蛋

上一节我们已经了 \(2\) 个鸡蛋情况下的最优解法，那么 \(3\) 个、 \(4\) 个乃至任意 \(k\) 个鸡蛋应该如何求解呢？

假如有足够多鸡蛋的话，很显然我们可以使用二分法，对于 \(n\) 层大楼，那么至多 \(\left \lceil \log_{2}{n} \right \rceil\) 个鸡蛋和尝试即可。

如果鸡蛋不够多呢？

和刚才推理2个鸡蛋最佳算法一致，可以使用动态规划算法。设大楼共 \(n\) 层，有 \(k\) 枚鸡蛋。假设已经求出了 \(k - 1\) 个鸡蛋对应某个楼层 \(t\) 的解，即已知 \(V(k - 1, t)\) ( \(t \in [1, n]\) ) 。对于 \(k\) 枚鸡蛋的场景，我们任选第 \(k\) 层（ \(1 \leq k \leq n\)）扔下鸡蛋：

1. 鸡蛋摔碎：说明最高安全楼层在 \(k\) 层以下，问题简化为 \(k - 1\) 枚鸡蛋、 \(k - 1\) 层楼，对应解为 \(V(e - 1, k - 1)\) ；
2. 鸡蛋完好：说明最高安全楼层在 \(k\) 层以上，问题简化为 \(k\) 枚鸡蛋、 \(n - k\) 层楼，对应解为 \(V(e, n - k)\) 。

可以得到贝尔曼方程( \(\textit{Bellman Equation}\) )递归关系式：

\[ \begin{aligned} V(e, n) = & \min_{k} \left( 1 + \max \{ V(e - 1, k - 1), V(e, n - k) \} \right) \\ &k = 1, 2, \dots, n \end{aligned} \]

根据动态规划递推表达式，我们可以写出如下的动态规划算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public static int superEggDrop(int k, int n) {
    int[][] dp = new int[k][n + 1];

    for (int i = 0; i <= n; i++) {
        dp[0][i] = i;
    }

    for (int i = 1; i < k; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = Integer.MAX_VALUE;
        }
    }

    for (int i = 1; i < k; i++) {
        for (int j = 1; j <= n; j++) {
            for (int m = 1; m <= j; m++) {
                dp[i][j] = Math.min(dp[i][j], 1 + Math.max(dp[i - 1][m - 1], dp[i][j - m]));
            }
        }
    }

    return dp[k - 1][n];
}

当然这个算法只能计算最坏情况下的最少尝试次数。对于 \(2\) 个鸡蛋 \(100\) 层的情况，第一次在 \(14\) 层测试，鸡蛋摔碎就从 \(1\) 楼开始逐层排查；鸡蛋完好，下一次就在 \(14 + 13 = 27\) 层测试，再之后是 \(27 + 12 = 39\) 层，以此类推。当鸡蛋数量大于 \(2\) 时，需要在动态规划计算过程中额外记录信息，依靠这些记录逆向推导，还原出完整的最优测试步骤。

总结

经典有经典的价值！这道题对思维的考察非常全面，通过假设一个鸡蛋情况只能逐层试探，双蛋情况则考察了递归、动态规划思想，是一道难得的好题！

参考文献

1. Google经典面试题《100层楼测试两个鸡蛋》剖析
2. 动态规划 \(O(n^2)\) + 数学推导 \(O(1)\)
3. 鸡蛋掉落-两枚鸡蛋
4. 鸡蛋掉落
5. 双蛋问题
6. The Two Egg Problem
7. Bellman equation 贝尔曼方程