A Practical Guide To Quantitative Finance Interviews 收录了一些量化面试中的经典题目. 本文介绍的是来自第二章的「Glass Balls」.

Glass Balls #

Problem #

You are holding two glass balls in a $100$-story building. If a ball is thrown out of the window, it will not break if the floor number is less than $X$, and it will always break if the floor number is equal to or greater than $X$. You would like to determine $X$. What is the strategy that will minimize the number of drops for the worst case scenario?

Solution 1 #

著名的 “扔鸡蛋问题” , 更一般的问题是有 $k$ 个鸡蛋和 $n$ 层楼, 找到任意情况下都能确定临界楼层的最小尝试次数. 这个问题可以使用动态规划解决, 记 $f(n, k)$ 为目标值, 有如下状态转移方程: $$ f(n, k) = \underset{1\leq i\leq n}{min}{max(f(i - 1, k - 1), f(n - i, k))} + 1 $$

• “最坏情况下至少需要…” 这种问题中, $max$ 和 $min$ 的使用原则:
  • 决策: $min$ , 因为这是可控的, 我们寻找最优决策;
  • 结果: $max$ , 因为这是不可控的, 对于每种可能发生的情况, 要做好应对最坏情况的准备.

对于本题, 也就是 $n = 100$ , $k = 2$ 的特殊情况, 有一些更加直接的解法. 现在考虑扔 $m$ 次, 最高可以确定多少层. 在第 $n$ 层扔下第一个球, 如果它碎了, 那么第二个球可以从 $1$ 楼开始扔, 确定 $1 - n$ 中的临界楼层; 如果第一个球没碎, 我们还有 $m - 1$ 次机会, 从 $n + (n - 1)$ 层开始扔即可; 如此考虑, 有 $m$ 次机会时, 至多可以确定 $1 + 2 + … + m = \frac{m(m + 1)}{2}$ 层. 令 $\frac{m(m + 1)}{2} \geq 100$ , 解得 $m = 14$ , 也就是说, 至少需要 $14$ 次才能确定临界楼层.