两道ebay面试题

突然想起了一个多月前在ebay面试的场景，那时第一次正八经的到公司去面试，由于准备不充分吧，面试的时候被狠狠的鄙视了一次，现在想想还十分不甘心。所以这里把之前面试到的两道题目记录一下，也把我当时面试的过程记录一下。

100层楼2个鸡蛋的问题

两个软硬程度一样但未知的鸡蛋，它们有可能都在一楼就摔碎，也可能从一百层楼摔下来没事。有座100层的建筑，要你用这两个鸡蛋确定哪一层是鸡蛋可以安全落下的最高位置。可以摔碎两个鸡蛋。 最少需要几次测试，才能得到摔碎鸡蛋的楼层？方案如何？

非常朴素的想法

非常朴素的想法一：我一层一层，从一楼开始扔上去就是了……

非常朴素的想法二：如果我从\(n\)层开始仍第一个鸡蛋。如果这个鸡蛋没有碎，那么我再向上\(n\)层，即到第\(2n\)层扔鸡蛋；如果鸡蛋碎了，我就从第1层/第\(n+1\)层开始扔鸡蛋，一层层向上扔上去。那么这个想法当中的\(n\)值应当如何取值呢？我们考虑在这个题目当中有一个100层楼的前提条件。按照我们的这种方法，在最坏的情况下就是当第一个鸡蛋扔到100层才碎掉，这样第二个鸡蛋就需要从倒数第二次扔鸡蛋的上面一层的位置开始扔，这样需要扔鸡蛋的次数最多。考虑清楚这一点，我们可以列出方程：\(c = \frac{{100}}{n} + n - 1\)，其中\(c\)表示需要扔的次数。这是高中学过的一种函数形式，很容易求得取得最小值时，\(n=10\)，最少\(c=19\)。

动态规划

我们将这个问题转换成：如果给定2个鸡蛋，\(n\)次抛鸡蛋实验，可以保证测出多少层。

在这个问题中，我们需要注意的是可以保证测出多少层。为了保证能够在有限的\(n\)词测试当中测出需要的层数，我们首先要考虑最坏的情况，也就是如果第一次抛鸡蛋鸡蛋就碎了的情况。如果第一次鸡蛋就碎了，那么我们为了测出楼层就只能从最底层开始一层层网上抛了（因为倘若不是这样，比如我从碎了的下一层开始抛，那如果鸡蛋也碎了这就说不清楚了）。这样，我们就确定了每次试验鸡蛋的起抛位置，那就是\(n\)层，因为在\(n\)层抛，即使碎掉了也可以保证在剩下的\(n-1\)次试验当中，让鸡蛋覆盖这所有的\(n\)层楼。倘若高于\(n\)这个数字就不可能了。

那么如果我们的第一次抛鸡蛋没有碎呢？那么这个问题就很自然的转化成了：在最多\(n-1\)抛鸡蛋试验中，可以保证测出多少层。可以看出，这就是一个典型的动态规划问题了。

我们就针对这个题目来详细说明。

• 抛1次：只能测出一层，毫无疑问
• 抛2次：从2楼起抛，如果碎了，在1楼抛；没碎，转化成一个2个鸡蛋抛1次的问题（上面这个问题），所以抛2次可以测出2+1=3层
• 抛3次：从3楼起抛，如果碎了，从1楼开始向上抛；没碎，转化成一个2个鸡蛋抛2次的问题（上面这个问题），所以抛3次可以测出3+3=6层
• 抛4次：从4楼起抛，如果碎了，从1楼开始向上抛；没碎，转化成一个2个鸡蛋抛3次的问题（上面这个问题），所以抛4次可以测出4+6=10层
• 抛5次：……

这样我们就已经看出规律了。以此类推，在我们抛14次的时候可以保证测出105层，所以最佳的抛鸡蛋次数是14次。

关于这个问题还有人从数学角度进行分析：http://blog.sina.com.cn/s/blog_6c813dbd0101bh98.html

100对夫妻丈夫出轨问题

村子里有100对夫妻，其中每个丈夫都瞒着自己的妻子偷情。村里的每个妻子都能立即发现除自己丈夫之外的其他男人是否偷情，唯独不知道她自己的丈夫到底有没有偷情。村里的规矩不容忍通奸。任何一个妻子，一旦能证明自己的男人偷情，就必须当天把他杀死。村里的女人全都严格照此规矩办事。一天，从村外来了一个人说，村里至少有一个丈夫偷情。请问接下来会发生什么事？

这个题目正向硬想还是很乱脑子的，但这其实是一个递归问题。

递归

首先我们考虑递归的终止条件，就是只有一个丈夫偷情会怎么样？很显然，妻子在听了村外人的话之后，看到其他的丈夫都没有偷情，那么就是自己的丈夫偷情了。所以会将自己的丈夫杀掉。

接着，我们考虑如果只有2个丈夫偷情会怎么样。这两个妻子先假定不是自己的丈夫偷情，那么她们俩就以为只有一个丈夫在偷情。但是根据上面的只有一个丈夫的情况，这个丈夫会被杀掉，但是这两个妻子发现没有丈夫被杀掉，便同时知道其实自己的丈夫在偷情，所以都把自己的丈夫傻掉了。

那么如果只有三对夫妻呢？同样，假定自己的丈夫没有出轨，期待的是只有两个丈夫出轨了。但是事情没有按照只有两个丈夫出轨的剧本发展，也就是说这两个丈夫没有被杀掉。所以最终意识到自己的丈夫出轨了，所以这三个丈夫就都被杀掉了。

以此类推……

所以最后的结果就是这个村子里面所有的男人被杀光了。

最后的话

这两道题表面上看起来是智力题，但实际上却是地地道道的算法题。当初没有答出来，还是跟自己的算法功底薄弱和逻辑思维不够习惯有关。日后还是需要多多练习才行啊。