谷歌算法面试题

❶ 3道有意思的逻辑思维面试题

从小到大做了无数道智力题，工作之后接触到程序员逻辑思维面试题，也曾经饶有兴致的研究过。这些智力题，表面上是考智力水平，实际上是考察逻辑思维能力，而从更一般的意义而言，是在考察解决问题的能力。

一个人学习、研究、工作，其实无时无刻不是在训练或使用解决问题的能力。解决问题的能力，在我看来，有很多方面，其中很重要的一方面就是逻辑思维能力。很多人对于逻辑思维的理解是存在误区的，总以为逻辑思维只是理科生和工程师用的东西，与文科生甚至普通人没有什么关系。而实际上， 逻辑思维所涉及的范围远远不止以数学为基础的理工科，而是一种涵盖各种学科、各种工作的通识能力 。

比如说，大学学文科专业的罗振宇，几年前开了一个节目叫“罗辑思维”，强调用逻辑思维来理解世界，节目的内容涉及社会、历史、经济、人文、理工等各方面，俘获了几百万乃至上千万的粉丝。后来罗打造得到APP成为最知名的知识付费应用，就是以罗辑思维这个品牌栏目为底子做的。

最近看了一些大的科技公司（比如谷歌、微软等）等招聘员工的面试题，很有意思，在这里与大家分享，并共同探讨。

这是微软非常知名的一道面试题，曾经难倒无数学霸才子：不是说好的考程序题或者智力题吗，怎么来了一个社会基础建设问题？

为什么是圆的？方的不行吗？圆的究竟优势在哪里？

这就是在考察面试者的逻辑思维了。其实认真思考之后，不难得出“标准答案”：

如果面试者能够这样回答，说明他的逻辑思维不错，或者至少生活经验比较丰富。

那么这是唯一的正确答案吗？没有这么简单。我从一些优秀者的回答中，还发现了其它也很有道理的答案：

如果面试者能够在所谓“标准答案”的基础上，多给出几个原因，那么说明不仅逻辑思维很好，工程思维也非常棒，善于运用生活中的知识。这道题基本上给考官的印象应该是满分了。

但是，关于这道题的讨论并非到此为止。 下水道井盖一定是圆的吗？有没有可能是方的或者其它形状的？

传说有一位面试者，在被问到该问题的时候，坚持说也可以用方的井盖，并给出了合理的理由，最终成功说服了考官。下面是传说的面试过程：

这位面试者不仅逻辑思维和工程经验丰富，说服人的能力也非常强，让考官觉得他是不可多得的人才，被推荐到更需要综合技能的销售部门工作。

其实，像这样的逻辑思维面试题并没有所谓的标准答案，考官的真实目的是 考察面试者的逻辑思维能力 ，更一般的讲，是 解决问题的能力 。下水道盖也可以是方的，只要你能给出合理的理由，自圆其说。

这是Google的一道面试题：

有一栋100层高的大楼，给你两个完全相同的玻璃球。假设从某一层开始，丢下玻璃球会摔碎。那么怎么利用手中的两个球，用什么最优策略知道这个临界的层是第几层？

最笨的办法谁都能想到：

可是这个办法，最坏的情况下要试99次，平均意义上要试49次。而且只用了一个球，另一个球没利用上。显然不是最优的策略。

计算机专业的学生很容易想到更高级的办法——二分法。具体是：

用这种方法，需要log100，也就是大约7次，能够找到答案。

面试者如果能这样回答，说明对计算机专业基本算法是有了解的。但是，仔细想想，这个方法对吗？

这个方法显然是有毛病的。比如说我举一个反例，第10层是临界层的情况。按照二分法来执行，第一次试验第50层将摔碎，第二次试验第25层又将摔碎，此时两个玻璃球都摔碎了，将没有办法继续进行试验！

注意最多有两个球，也就是最多可以摔碎两次。尽管上述二分法不可行，我们是否可以借鉴其思路，先大致确定一个小的范围，然后逐个试验呢？根据这样的思路，可以提出下面的方法：

这种方法最坏的情况出现在临界层为100时，将需要试验10+10=20次；最好的情况出现在临界层为2时，只需要试验2次。而平均意义上大约需要试验10次。怎么样，是不是有效的利用了两个球呢？

按照吴军老师的说法，这种解题方法其实体现了 一种典型的工程思维：粗调和精调 。其中第一个球用于粗调，确定一个大致的范围；第二个球用于精调，在大致的范围内确定精确的值。

其实，粗调和精调的工程思维在生活和工程中都很常见：

从这几个例子，我们可以对粗调和精调的优点及注意事项进行简单的总结：

了解了粗调和精调的概念之后，我们回过头来，再次考察这道玻璃球题目。如果有3个玻璃球呢，是否有更好的方法？

当然是有的，标准的答案是采取三步试验：

细心的读者会发现，这三步试验分别把答案的可能范围缩小了4、4、5倍，最终确定了答案。

为什么是这几个数呢？而且，回过头来想想，为什么两个小球的情况下，两步试验缩小的范围分别是10、10呢？

这几个数的选择，当然绝非巧合。实际上，2个和3个玻璃球的情况下，缩小倍数分别是按照根号下100（也就是10）、3次根号下100（大约是5）来选择的。 推广到n个玻璃球的情况下，每步试验的范围缩小倍数应该是n次根号下100。 具体证明，我们在这里不做讨论。

这绝不仅仅是一个小小的逻辑题， 考官想考察的是面试者的逻辑思维，包括工程思想、分析能力以及举一反三的归纳概括能力 。知道标准答案不算什么，吃透这道题并弄清背后的深刻原理，才是本事。

这道题相对前两道来说要简单一些。据说Google过去面试产品经理的时候会问到这个问题。什么数据都不给，直接就这么问。

有些中国面试者可能不乐意了：你又不告诉我高尔夫球多大，也不告诉我这个房间的尺寸，什么数据都没有，我怎么算啊？

但是这个题没错，考官考察的就是不给数据你怎么计算！要不然小学生都能算出来了。

有些人一看没给数据，可能就会胡猜：一间普通办公室，又不是很大，高尔夫球直径大概几厘米，直观感觉应该能装几千个或者几万个吧？

然而答案恰恰违反我们的直觉：至少能装几十万个，甚至能装上百万个。

我们来算算：

一个房间竟然能装这么多高尔夫球？是不是大的出乎我们的意料呢？

有人可能会怀疑，这道题如此简单，小学生都能做，侮辱人智商吗？然而这道题实际考察的，是我们解决问题的方式。Google对产品经理的要求是：

有的面试者在没给数据的情况下可能会根据直觉乱猜，这是做事的大忌，因为很多东西其实是反直觉的，乱猜可能导致完全错误的结论，这是很危险的。最准确的做法是拿工具量一下会议室的长宽高以及高尔夫球的直径，然后进行计算。不过，在没有准确数据的情况下，合理的估算也是可行的，甚至也是必要的，估算能够帮助我们大致知道答案的范围，这在很多情况下已经足够支持决策！

❷ 如何解读微软、谷歌和苹果公司的智力面试问题

有栋建筑物高100层。若从第N层或更高的楼层扔下来，鸡蛋就会破掉。若从第N层以下的楼层扔下来则不会破掉。给你2个鸡蛋，请找出N，并要求最差情况下扔鸡蛋的次数为最少。

我们发现，无论怎么扔鸡蛋1（Egg 1），鸡蛋2（Egg 2）都必须在“破掉那一层”和下一个不会破掉的最高楼层之间，逐层扔下楼（从最低的到最高的）。例如，若鸡蛋1从5层和10层楼扔下没破掉，但从15层扔下时破掉了，那么，在最差情况下，鸡蛋2必须尝试从11、12、13和14层扔下楼。

具体做法

首先，让我们试着从10层开始扔鸡蛋，然后是20层，等等。

q 如果鸡蛋1第一次扔下楼（10层）就破掉了，那么，最多需要扔10次。

q 如果鸡蛋1最后一次扔下楼（100层）才破掉，那么，最多要扔19次（10、20、…、90、100层，然后是91到99层）。

这么做也挺不错，但我们只考虑了绝对最差情况。我们应该进行“负载均衡”，让这两种情况下扔鸡蛋的次数更均匀。

我们的目标是设计一种扔鸡蛋的方法，使得扔鸡蛋1时，不论是在第一次还是最后一次扔下楼才破掉，次数越稳定越好。

(1) 完美负载均衡的方法应该是，扔鸡蛋1的次数加上扔鸡蛋2的次数，不论什么时候都一样，不管鸡蛋1是从哪层楼扔下时破掉的。
(2) 若有这种扔法，每次鸡蛋1多扔一次，鸡蛋2就可以少扔一次。
(3) 因此，每丢一次鸡蛋1，就应该减少鸡蛋2可能需要扔下楼的次数。例如，如果鸡蛋1先从20层往下扔，然后从30层扔下楼，此时鸡蛋2可能就要扔9次。若鸡蛋1再扔一次，我们必须让鸡蛋2扔下楼的次数降为8次。也就是说，我们必须让鸡蛋1从39层扔下楼。
(4) 由此可知，鸡蛋1必须从X层开始往下扔，然后再往上增加X-1层……直至到达100层。
(5) 求解方程式X + (X-1) + (X-2) + … + 1 = 100，得到X (X + 1) / 2 = 100 → X = 14。
我们先从14层开始，然后是27层，接着是39层，依此类推，最差情况下鸡蛋要扔14次。

正如解决其他许多最大化/最小化的问题一样，这类问题的关键在于“平衡最差情况”。

❸ 15个变态的谷歌面试问题的答案

十二题可是初三上学期的物理题啊,关于天平的!
答案是:把八个硬币其中3个放左盘,在选另外3个放右盘,其余两个先不管,如果两个盘一样重,则重的硬币在剩下的两个硬币中,在称这两个硬币,ok.若其中一个盘较重,就把这个盘的三个硬币,其中一个放左盘,另一个放右盘再测,如果相等,则重的是剩下的1个硬币,如果天平不平衡,则重的硬币在较重的盘上.
第五题则是关于数学几何图形,大概是初二初三接触过的,要知道井盖在路上,肯定是有东西在井盖的边缘托住他,井盖才不会掉下去,而这个边缘是很小的.那么井盖是圆的话,半径相等,如果井盖因某种原因而打侧放的话由于直径比边缘要长,不至于令井盖掉下去.如果井盖是矩形的话,一打侧他就会掉下去了,因为矩形由两个直角三角形组成,而直角三角形的斜边较长.如果照这样说等边三角形也应该可以啊,一些不规则图形也可以,可能也有美观这一因素在吧,又或者是井盖作者先想到圆井盖,后来全世界都圆井盖了,就没人在意去计较为什么不用等边三角形井盖了...由于所学知识有限,当时我问老师为什么不能用等边三角形,老师没答我.不能给你证明,抱歉.
第七题,首先思考一下,每一秒分针时针都在转动,那么在重合的时候的下一秒,时针分针会不会再重合一次?想深一层,我觉得应从圆的度数方面考虑,通过计算得知,分针每走一小格(一分钟),走了6度,而时针走了0.5度.那么,假如现在是十二点,时针分针都指在了"12"上,这时重合了一次,但每走一秒,分针都有微妙的转动,而时针也是,那么一秒分针转动了6/60=0.1度,时针转动了0.5/60=0.008333度,即是说,在重合时的下一秒,分针就已经超越了时针,所以一小时只重合一次!(个人认为,本人仅是初三学生,这可能不是正确答案).我觉得,一天24小时,自然是24次.
第十一题属于推理题目,我不知道(呵呵),不过在网上有类似这道题的:海盗分金币,有五个海盗,一号首先开始分金币,如果他的分配方法得不到半数的同意就处死并让下一位去分,这题已有详细答案(很久前就看过了),答案是:逆向思维。
假设每一个海盗都是绝顶聪明而理性，他们都能够进行严密的逻辑推理，并能很理智的判断自身的得失，即能够在保住性命的前提下得到最多的金币。同时还假设每一轮表决后的结果都能顺利得到执行，那么抽到1号的海盗应该提出怎样的分配方案才能使自己既不被扔进海里，又可以得到更多的金币呢？
此题公认的标准答案是：1号海盗分给3号1枚金币，4号或5号2枚金币，自己则独得97枚金币，即分配方案为（97，0，1，2，0）或（97，0，1，0，2）。现来看如下各人的理性分析：
首先从5号海盗开始，因为他是最安全的，没有被扔下大海的风险，因此他的策略也最为简单，即最好前面的人全都死光光，那么他就可以独得这100枚金币了。
接下来看4号，他的生存机会完全取决于前面还有人存活着，因为如果1号到3号的海盗全都喂了鲨鱼，那么在只剩4号与5号的情况下，不管4号提出怎样的分配方案，5号一定都会投反对票来让4号去喂鲨鱼，以独吞全部的金币。哪怕4号为了保命而讨好5号，提出（0，100）这样的方案让5号独占金币，但是5号还有可能觉得留着4号有危险，而投票反对以让其喂鲨鱼。因此理性的4号是不应该冒这样的风险，把存活的希望寄托在5号的随机选择上的，他惟有支持3号才能绝对保证自身的性命。
再来看3号，他经过上述的逻辑推理之后，就会提出（100，0，0）这样的分配方案，因为他知道4号哪怕一无所获，也还是会无条件的支持他而投赞成票的，那么再加上自己的1票就可以使他稳获这100金币了。
但是，2号也经过推理得知了3号的分配方案，那么他就会提出（98，0，1，1）的方案。因为这个方案相对于3号的分配方案，4号和5号至少可以获得1枚金币，理性的4号和5号自然会觉得此方案对他们来说更有利而支持2号，不希望2号出局而由3号来进行分配。这样，2号就可以屁颠屁颠的拿走98枚金币了。
不幸的是，1号海盗更不是省油的灯，经过一番推理之后也洞悉了2号的分配方案。他将采取的策略是放弃2号，而给3号1枚金币，同时给4号或5号2枚金币，即提出（97，0，1，2，0）或（97，0，1，0，2）的分配方案。由于1号的分配方案对于3号与4号或5号来说，相比2号的方案可以获得更多的利益，那么他们将会投票支持1号，再加上1号自身的1票，97枚金币就可轻松落入1号的腰包了 .但是google的这道题无明确条件,只说如果得不到同意就死,没其他的了,如果船员不管三七二十一全让你死,那你怎么办?或许这题不应用逻辑分析,而是从社会现实角度,例如巴结好熟人之类的呵呵~~
第十题好像在某本书上看过,不过没有写答案,我是这样想的,既然要让他不知道号码,就不能够在纸上写,那么就只能够用手机确认了:让鲍伯拨打我的手机号码.
第十五题,我想出的答案有很多,这种脑筋急转弯式的题在大家眼中有无数答案,但出题人只看他手中的正确答案,所以我把我最雷的一个给你参考吧:如果只有硬币这么小,从平面看搅拌器一般成接近四边形五边形的形状,搅拌刀片转动时是圆,吗么就直接站在搅拌刀片切不到你的死角位置不就ok了?
第三题,生物学解释,生男生女比例1比1,因为概率问题只是大概估算,并无准确答案,考方只想看你的解题思路罢了,我是这样解的:既然是一比1,那么就是要么先生男,要么先生女,由于是大概估算,那么看作每生两次就有一男一女(现实是不可能),即是:先生男的话就不再生,如果生女的话就会在生一个男,把他认作只有这两种情况,且概率都是一比一,就是说两男一女,所以比例就是二比一.
第八题,我不会,不过网上有网友的见解:对于一个软件工程师来说，是要尽量避免在软件中“死牛肉”出现。它不但对软件本身没有好处，还会给整个软件带来破坏。死牛肉不但不能吃还会引来许多仓蝇之类的害虫。
其他题大多属于主观题,没绝对答案,出题人只想看你的思路.不过我已经把能说的都给你说了,只看答案没有用关键是分析,希望我用了1小时的长篇大论对你有帮助

参考资料： 网络大神,老师的谆谆教导

❹ android 面试，算法题。

final int size = data.length;
for(int i = 0; i< size; i++){
if(data[i] == 0xffffffff)
data[i] = 0x80ffffff;
}

不知道你是不是这个意思。