现在的位置: 首页 > 综合 > 正文

解答Google的一道面试题 收藏

2014年01月04日 ⁄ 综合 ⁄ 共 5366字 ⁄ 字号 评论关闭

 解答Google的一道面试题 收藏
这几天有一道Google的面试题在论坛炒得很火,题目如下:“有一个100层高的大厦,你手中有两个相同的玻璃围棋子。从这个大厦的某一层扔下围棋子就会碎,用你手中的这两个玻璃围棋子,找出一个最优的策略,来得知那个临界层面。”下面给出我的分析和解答。

 

为了得到两个棋子的最优策略,我们先简化问题,看看一个棋子的情况。如果手中只有一个棋子,为了得知临界层面,你只有一种选择:从2楼开始,一层一层地试,直到棋子被打碎,此时你站的楼层就是所求的临界层面。在最差的情况下,我们需要投掷99-2+1=98次,你可能奇怪为什么不是100-2+1=99次,那是因为题目已经告诉我们“从这个大厦的某一层扔下围棋子就会碎”,所以在99层扔下来还没碎的话就不用去100层了——从那里扔它一定会碎。

 

从一个棋子的策略我们可以看出,一个棋子就足以解答这个问题了。现在又多了一个棋子,该如何利用它呢?很自然地,我们希望能通过这个棋子缩小这种一层一层查找的范围。为了缩小范围,我们将整个大厦的层数分成x段,在这x段中查找那个临界段,然后在临界段中再一层一层地找临界层。比如可以将大楼分成4段,我们分别在25层、50层、75层投掷棋子,以确定临界段;如果临界段在25层到50层,我们再从26层开始一层一层查找临界层。

 

分析到这里,问题就转化成了如何确定分段数x使棋子投掷的次数最少的问题。在最差的情况下,要确定临界段,我们需要投掷100/x-1次;确定了临界段之后要确定临界层,我们需要再投掷x-1次。因此,问题就成了求函数f(x)=(100/x-1)+(x-1)的最小值问题。先对f(x)求导,f’(x)=1-100/x2,令f’(x)=0求出驻点x=10(x=-10舍去)。由于f(x)存在最小值且只有一个驻点,所以当x=10时f(x)取得最小值,最小值为18。这样就解答了这个问题。

 

其实10这个结果也很容易直接看出来。在只有一个棋子时,我们相当于把整个大厦分成了一段,这一段有100层。在有两个棋子时,我们有很多分法,但无论怎么分,如果分成k1段,每段有k2层,那么就有k1k2=100。在最坏的情况下,我们需要投掷(k1-1)+(k2-1)次。因此问题也可以表述成在k1k2=100的条件约束下,如何让函数f(k1,k2)= k1+k2最小。在初等数学中,我们知道在矩形面积一定的情况下,正方形的周长最小。利用这个结论,我们可以直接得出结论k1=k2=10。

 

现在问题已经完满解决,但我还想把这个问题扩展一下,把它变成“m层楼n个棋子”的情况。首先来看这样一个问题,给定m层楼,多少个棋子就“足够”了,也就是说,再多的棋子也不能加快查找的过程。在我所能想到的方法里,二分法应该是最优的,如果按二分法来查找,则需要ceiling(log2m)个棋子(ceiling是向上取整函数),超过这个数再多的棋子也无益。

 

如果n>=ceiling(log2m),那就采用二分法,现在考虑n< ceiling(log2m)的情况。前面已经看到,当n=2时,问题可以表述成在k1k2=100的条件约束下,求函数f(k1,k2)= k1+k2的最小值。类似地,在n个棋子的情况下,问题可以表述成在k1k2…kn=m的条件约束下,求函数f(k1,k2,…,kn)=k1+k2+…+kn的最小值。利用拉格朗日乘数法,我们可以很容易地求出:当k1=k2=…=kn=n√m时,这个多元函数取得最值。n√m有可能不是整数,因此这只是一个理论上的结果。

 

我们换一个思路考虑,m层楼n个棋子的问题其实就是如何将m分解成n个因子相乘,从而让各个因子之和最小。如何分解m使得策略最优就成了问题的关键。前面得出的结论提示我们尽量让各个因子相等或者相差较小,它们相加的结果才会较小。比如,100层楼3个棋子的情况,5,5,4应该是一个最优的选择。

 

考虑到这里,又有一个问题出现了:是不是将m分解的越多越好呢?比如,将100分解成10,10好呢,还是2,5,10好?这个问题其实就是在问,两个大于1的整数,它们的和大呢还是积大。很明显,当然是积大,因此将m分解的越多越好。

 

数论告诉我们,质数是整数的基础,所有整数都可以分解成若干个质数的乘积。因此,如果将上面的方法发挥到极致,那就要求我们把m分解成质数的乘积。当然,如果棋子足够多,这并不是最优的方法,对质数层楼的段,你仍然可以采用二分法。

------------------------------------------------------------------------------------------------------

上文贴出之后,我又在CSDN和ChinaUnix的论坛看了一些网友的解法,发现上述方法并非最优。将大楼分段以缩小查找范围的想法是没错的,问题在于是否应该均匀分段。

题目要求我们总的投掷次数要最少。在分段之后,总的投掷次数就等于确定临近段的次数加上确定临界层的次数。如果我们均匀分段,则确定临界层的最坏投掷数是固定的(9次),随着我们确定临近段的投掷次数增加,总的投掷次数也在增加。这样一来,随着临界段的不同,投掷次数也不同。

这也就是为什么上述方法不是最优的原因:投掷次数分布不均。按最坏情况估计,这种方法就多做了几次。为了使最坏情况的投掷数最小,我们希望无论临界段在哪里,总的投掷数都不变,也就是说将投掷数均匀分布。

接下来的解决方案就很容易想出了:既然第一步(确定临界段)的投掷数增加不可避免,我们就让第二步(确定临界层)的投掷数随着第一步的次数增加而减少。第一步的投掷数是一次一次增加的,那就让第二步的投掷数一次一次减少。假设第一次投掷的层数是f,转化成数学模型,就是要求f+(f-1)+...+2+1>=99,即f(f+1)/2>=99,解出结果等于14。

这种方法要推广到n(n>2)个棋子的情况比较困难。我初步的想法是,先用均匀分段求出一个解,然后修正这个解使投掷次数均匀分布。如果你对此有兴趣,不妨思考一下具体的解法。
发表于 @ 2006年12月08日 19:07:00 | 评论( 21 ) | 编辑| 举报| 收藏

新一篇:Bloom Filter概念和原理guogangj 发表于2006年12月13日 20:20:15  IP:举报
嗯,确实如此。liuxiaolin21 发表于2006年12月14日 13:50:02  IP:举报
只有一个棋子的话,为什么不用二分法来扔呢?想不明白,高手指点jiaomeng 发表于2006年12月14日 13:59:41  IP:举报
To liuxiaolin21: 只有一个棋子的话,从50楼扔下去碎了,你如何判断临界层?platform 发表于2006年12月14日 14:51:49  IP:举报
我也赞成2分发,虽然说只有两个棋子,这个问题是求一个最优答案,而不是一定答案。二分发最优,虽然说二分未必能最快找到临界面注意要求的是最优而不是最快jiaomeng 发表于2006年12月14日 15:05:08  IP:举报
To platform: 题目要求在得知临界层的前提下求最优策略。liuxiaolin21 发表于2006年12月14日 16:04:02  IP:举报
to jiaomeng:如果50楼碎了,说明临界层在50楼以下啊,50楼以上肯定也碎,然后接着从25开始扔jiaomeng 发表于2006年12月14日 16:51:54  IP:举报
To liuxiaolin21: 唯一的棋子在50楼摔碎了,25楼的棋子从哪儿来?liuxiaolin21 发表于2006年12月14日 17:46:46  IP:举报
一下子明白拉...多谢platform 发表于2006年12月14日 23:02:02  IP:举报
哈哈,我也明白了,原来目的是一定要找出临界层面。理解成求二分法求最优路径了 platform 发表于2006年12月14日 23:12:27  IP:举报
考虑了一下,在保障一定要找出临界面的话,每隔4楼作为一个段,来扔这个棋子。或许俺对于题意还是有理解问题。mybandari 发表于2007年7月17日 21:40:42  IP:举报
不错!
最有是14
好题目BreaKing 发表于2007年7月21日 13:32:13  IP:举报
大厦 m 层,棋子 n 颗
if n>=log(m) then 用二分法
else 设最坏情况下需要扔 x 次,x 需要满足下面的两个不等式
(x+1)! >= n!(x-n+1)!m
x! < n!(x-n)!m
注意到 x 是整数,解出上面两个不等式就可以得到 x 了jiaomeng 发表于2007年7月21日 15:29:55  IP:举报
Re BreaKing: 能否解释一下你的结论?BreaKing 发表于2007年7月22日 17:12:14  IP:举报
用 p 表示棋子数,用 q 表示扔的次数,用 f(p,q) 表示 p 颗棋子最多允许扔 q 次,可以确定的最

大楼层数目,换句话说,能在 f(p,q) 这么多层数中确定哪一层是临界层,为了描述的简明下面我

们把这样的事件称为“覆盖”,因此也可以说 p 颗棋子最多允许扔 q 次可以覆盖 f(p,q) 层。

没有棋子,一次都不能扔,可以覆盖 1 层:f(0,0)=1。这个结论再推广一下,即使允许扔若干次

,但手上已经没有棋子了,也只能覆盖 1 层:f(0,q)=1,其中 q=0,1,2,3,...。类似的,即使有若干

颗棋子,但却不允许扔,也只能覆盖 1 层:f(p,0)=1,其中 p=0,1,2,3,...。实际上,上面的结论可

以合并为一条。当 pq=0 时,f(p,q)=1。

当 pq>0 时,则将所有棋子编号为 1,...,p,每次从号码最大的那颗棋子开始用。首先考虑 p 号棋

子,假设它在某一层扔下去(我们现在还不知道它应该在哪一层扔,不过这没关系),有两种情

况:碎了与没碎。不管怎样,p 号棋子把楼层分为了上下两段区间,我们根据 p 号棋子的破碎与

否来决定之后在哪一段区间继续作业。
下半区间(p 号棋子碎了):现在还剩下 p-1 颗棋子,还允许扔 q-1 次,你一定看出来了,这段

区间最大就是 f(p-1,q-1)。
上半区间(p 号棋子没碎):现在还剩下 p 颗棋子,还允许扔 q-1 次,这段区间最大是 f(p,q-1)


于是 f(p,q)=f(p-1,q-1)+f(p,q-1),其中 pq>0。

综合以上,我们有:
(1) 当 pq=0 时,f(0,0)=1;
(2) 当 pq>0 时,f(p,q)=f(p-1,q-1)+f(p,q-1)。

根据递推式,可以得出 f(p,q)=(p+q)!/(p!q!)。容易看出来这是一个组合数。

现在回头看看题目:大厦 m 层,棋子 n 颗,问最坏情况需要扔几次能把临界层找到?

把 n 代入得 f(n,q)=(n+q)!/(n!q!)>=m,即找到满足该不等式的最小的 q 值。BreaKing 发表于2007年7月22日 18:29:20  IP:举报
抱歉,21号回复的解答有误,请以22号的解答为准。若有误或者有更好的解答请继续与我讨论:)BreaKing 发表于2007年7月23日 9:02:14  IP:举报
sorry,昨天的也是有误的,就是根据递推式得出的通项是错的,但是思路应该没有错,如果算出来了我会尽快贴出来BreaKing 发表于2007年7月23日 23:27:12  IP:举报
通项比较复杂,希望这次是对的 :)
(1) p>=q 时,f(p,q) = 2^q
(2) p<q 时,f(p,q) = q!/(q-0)!0! + q!/(q-1)!1! + q!/(q-2)!2! + ... + q!/(q-p)!p!jiaomeng 发表于2007年7月24日 9:40:20  IP:举报
Re BreaKing: 我没有详细验证你的结论,不过我觉得你的思路很好。一颗棋子扔下去,就把大楼分成了两段,根据棋子碎与不碎,就能将查找范围缩小到其中一段。这个规律满足了应用分治法的条件,下来的工作只是列递归方程和解方程了。bitzilla 发表于2007年9月13日 10:09:19  IP:举报
BreaKing 的解答很好,描述的是算法。哈哈。yike5460 发表于2008年4月11日 14:57:20  IP:举报
接下来的解决方案就很容易想出了:既然第一步(确定临界段)的投掷数增加不可避免,我们就让第二步(确定临界层)的投掷数随着第一步的次数增加而减少。第一步的投掷数是一次一次增加的,那就让第二步的投掷数一次一次减少。假设第一次投掷的层数是f,转化成数学模型,就是要求f+(f-1)+...+2+1>=99,即f(f+1)/2>=99,解出结果等于14。

不好意思,这个是什么意思,是说临界段分得越多,确定临界层投掷的次数就越小?列出的f+(f-1)+...+2+1>=99代表什么意义呢?谢谢解答!hansion3406 发表于2008年7月14日 16:22:38  IP:168.3.1.*举报
牛。。。kay wei 发表于2008年11月5日 17:13:35  IP:举报
早年对哈希进行了一定的应用,略微了解其中的微妙,看了你的文章,赞佩你的专研精神

本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/jiaomeng/archive/2006/12/08/1435226.aspx

抱歉!评论已关闭.