【引用】腾讯的面试题(很有科技含量)(2)
luyued 发布于 2011-01-03 22:26 浏览 N 次但是思前想后,最终我还是没能理出具体头绪,无奈只好求助于百度了。
找到题目出处很简单,当我看到原帖第6楼网友“OO”回复的答案后,我彻底拜服了,也自此绝了进腾讯等大公司的念想。
-=================================================================-
下面请看网友“OO”的解法:
把狗从0-9编号;
把药水按1-1000编号;
把药水编号按二进制,如果第i位(因为最大1000,所以bit位为0-9)bit位为1,则分给编号为i的狗狗喝;
最后得一二进制数,如果编号为i的狗狗死了,该数的第i bit位为1,该数就是有毒的药水编号。
他说的比较专业,下面我用实例给解析一下:
用 0、1、2、3、4、5、6、7、8、9 给小狗编号;
而药水按1-1000编号;
我们把每瓶药水的编号转换为二进制数,由于2的10次方=1024,所以我们将二进制数定为有10个数位,如:
1=0000000001
13=0000001101
214=0011010110
对二进制转换不熟悉的朋友可以用“开始-程序-附件-计算器-查看-科学型”来轻松转换。
这样转换以后,每个药水编号的二进制数的每一位都分别对应一只小狗;
我们定义每瓶药水要喂给其二进制编号位数为“1”的那位对应的小狗喝;
由于2的10次方=1024>1000,所以这些二进制编号组合都是唯一的;
当我们用不到4小时的时间将1000瓶药水分别喂给相应的小狗喝后,就可以去看看书,上上网,听听歌来打发剩下的20小时;
20小时候,在一个合理的药效发作时间后,我们统计有中毒症状小狗的编号,中毒的定为“1”,正常的定为“0”;
然后依照编号顺序排列,我们就可以得到一个10位的二进制数,而将这个二进制数再转换为十进制数后,这个数值就是有毒的药水的编号了;
例如,最终结果是编号为 2、4、6、7、9 的小狗有中毒症状,我们就将一个十位二进制数的2、4、6、7、9位设为“1”,其余各位设为“0”,即:0010101101;
而0010101101对应的十进制数=173,所以第173瓶药水就是有毒药水!
当然,如果都无毒,10只小狗就会都是活蹦乱跳的。
-=================================================================-
相信通过上面的解释,大家基本上都能理解这个解题思想的过程了吧。
回过头来反思为什么老王没能想出这么具体的解法呢?
最主要的一点还是思想不够活,没能将早就学过的计算机知识应用到实际解题过程中,这也就决定了我和OO等高手之间的差距。
介绍这种解题方法当然不等于没有其他更好的解法,只是我觉得这种解法就是出题者想要达成的目的。
而且在我看来,其他类似时间分块方法的可操作性和实现的科学性,照这个方法也确实是差的太多。
不过有一种现象很有趣,在原帖中,OO在第6楼就发布了他的解法,但下面还有数十上百个回帖在积极地发表和探讨各种漏洞百出的解法。看来人的思维的确很复杂,创新思想和求胜心理使很多人怀疑一个已经很不错的结论。不过我倒觉得适时肯定别人的成果并消化掉对自己的经验积累也很有用。
-=================================================================-
附言:
虽然我没能想出具体的解决方案,但是我很坚定的是不能沿着设时间点试毒的思路走。之所以这样,主要是我觉得,这种思路基本上每个人都能想到。
试想,随便找个人来问,是不是绝大多数人看到题目后最先想到的,都是把 24 - 20 = 4(小时) = 240(分钟) = 14400(秒) 分为1000份,然后每隔14秒给小狗依次试药,等到最后4个小时内观测小狗的中毒时间点呢?
所以,如果答案大家都能想到,也就失去了题目考察应聘者综合能力的效果。
- 06-10· [推荐]网易财经会客厅:对
- 06-10· 网易娱乐
- 06-10· 从网易用户体验谈开去
- 06-10· 网易一卡通充值(看了笑喷
- 06-02· 濮青松与新浪网友一起关
- 06-02· 新浪博客
- 06-02· 新浪微博登陆首页i美股投
- 06-02· 董思阳做客新浪
- 06-02· 新浪SHOW【每周要闻播报】
- 06-02· 新浪精华买房文章
- 06-02· 新浪
- 06-02· 别的—中超联赛新浪体育
- 06-02· [转载]教你一招_xue花漂_新
- 06-01· Google Ranking Tips
- 05-31· www.iisun.cn阿里巴巴第一季
- 05-31· 阿里巴巴上市创造的神话
- 05-31· 阿里巴巴马云经典语录
- 05-31· 阿里巴巴的盈利模式
- 05-31· [推荐]“真假开心网”尘埃
- 05-29· [恶搞]网易财经:段永平谈