标签分类:面试

面试题:猜奖品问题

一个猜测游戏中,某一个瓶子中装有奖品。游戏者需要猜出奖品在哪个瓶子中,并且在m次结束游戏。(即m次猜中)
有n个黑色的瓶子(以至于游戏中看不到瓶中是否有东西)设从0到n-1编号,一字排开。每一次如果游戏者猜错了,那么奖品会各以50%的概率移动到左边或者右边的瓶子中。当奖品位于最左边或者最右边,游戏者猜错时,奖品必然右移或者左移。

问题:请设计一个满足n和m的策略,帮助游戏者完成游戏。

最多需要m=2n次 必能猜中
第一轮 先从0开始顺序往右猜,即0,1,…n-1,这样 如果奖品初始位于偶数位置处 必定能猜中
如果奖品初始是位于奇数处,则需要第二轮
如果n为偶数 则第一轮结束后奖品仍在奇数处
这样第二轮从1开始往右,即1,2,…,n-1 这样必中
如果n为奇数 则第一轮结束后奖品已经跳到偶数处
这样第二轮从0开始往右,即0,1,…,n-1 必中

二进制相关智力问题

题目1:有 1000 个一模一样的瓶子,其中有 999 瓶是普通的水,有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在,你只有 10 只小白鼠和一星期的时间,如何检验出哪个瓶子里有毒药?

个人解答:显然需要参考二进制的表示方法,但是腾讯面试当时纠结在时间只有一个星期,而喝下毒药死亡也需要一个星期,似乎只能验证一次。实际上,这个限制正说明我们确实只能利用这10只小白鼠验证一次。于是问题就简单了。将1000瓶水按照二进制编码的顺序给对应的小白鼠喝,比如编号3的水(二进制表示为11)就喂给编号1与编号2小白鼠喝。这样,一星期后看哪几只小白鼠死亡就可以判断哪个编号的水有毒。这个结论成立的前提是只有一瓶毒药,这样只有对应编号的小白鼠才会不幸死亡。

进一步题目:如果你有两个星期的时间,为了从 1000 个瓶子中找出毒药,你最少需要几只老鼠?注意,在第一轮实验中死掉的老鼠,就无法继续参与第二次实验了。

个人解答:有两个星期就可以进行两次实验,每个没死成的小白鼠就能再喝一次,也就是说一个小白鼠可以表示3个状态:第一周死,第二周死,最终也没死。显然就是参考三进制,于是需要3^7 > 1000,即最少7只。方法与之前类似,先给三进制表示为2的位对应的小白鼠喝,再实验三进制表示为1的位对应的小白鼠即可。

 结论:类似地,我们可以证明, n 只小白鼠 t 周的时间可以从 (t+1)^n 个瓶子中检验出毒药来。
题目2:100个开关控制100个灯,开关在一个房间灯在一个房间,最少走几趟能够确定他们的一一对应关系
个人解答:据说3的情况,只要一次即可(需要引入热这种状态。。。即存在亮,热,不亮三种状态)

腾讯面试总结

在腾讯终于突破了一面进入二面,本来很期待二面能多问下项目方面或是前端方面的知识。哪知天不我与,碰到个无语的面试官(也可能是故意这么安排)继续问基础,于是莫名奇妙的溃败。 一面也表现不算很好,但是估计考官人比较好,每次都会问本人的思路,顺便进行引导,也会给些小hint,然后本人不负众望的答对,可能这种快速学习的能力给考官比较好的印象吧,一下面了本人近两个半小时,最后也放本人过关。虽然其实最后本人已经 …

阅读全文

金山网络面试总结

金山网络算是本人第一个面试对口方向的公司,无奈再次失败,失败的主要原因不是技术上而是人士方向上。没有从公司方向思考是这次面试失败最主要的原因。 1.金山网络属于再创业公司,尽管宣称招暑期实习生,但实质仍是为快速发展的公司招人。所以面试侧重点都在询问面试者能为公司做些什么,结果本人面试过程完全没有察觉这一点,应该说自己还没有从淘宝实习面试的思维中脱离出来。自己说出自己已经保研的事实就是失败的开始。保 …

阅读全文