Google经典面试题: 鸡蛋应该怎么扔？

发表于 2026-03-06 更新于 2026-06-08 分类于 Data Structures and Algorithms Waline：阅读次数：本文字数： 4.9k 阅读时长 ≈ 4 分钟

By Long Luo

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

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

这道题的原文如下：

You work in a \(100\) floor building and you get \(2\) identical eggs. You need to figure out the highest floor an egg can be dropped without breaking. Find an algorithm that is minimizing number of throws in the worst-case scenario.

你站在一栋 \(100\) 层高的大楼里，手中有 \(2\) 个完全相同的鸡蛋。有一未知的临界楼层，鸡蛋从临界楼层以下扔下去，一定不会碎；从临界楼层以上丢下去，一定会碎。已知未碎的鸡蛋可以重复使用，碎了的鸡蛋就不能再往下扔了。要求即便在最坏情况下，尝试次数也要尽可能少。请问最少需要尝试多少次能够找到这个临界楼层？

一个鸡蛋

如果只有 \(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\) 次。

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

递归

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

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}\) 是个天文数字，我们可以缓存下每个楼层的最小值，优化算法，代码如下所示：

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\) 至 \(x - 1\) 层，总尝试次数恰好为 \(x\) ；
鸡蛋没碎，下一次就在第 \(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\)）扔下鸡蛋：

鸡蛋摔碎：说明最高安全楼层在 \(k\) 层以下，问题简化为 \(k - 1\) 枚鸡蛋、 \(k - 1\) 层楼，对应解为 \(V(e - 1, k - 1)\) ；
鸡蛋完好：说明最高安全楼层在 \(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} \]

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

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\) 时，需要在动态规划计算过程中额外记录信息，依靠这些记录逆向推导，还原出完整的最优测试步骤。

总结

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

一个鸡蛋

两个鸡蛋

递归

到底怎么扔呢？

多个鸡蛋

总结

参考文献