死理性派教你做谷歌面试题
长久以来，谷歌都因为拥有世界上最自由和优越的环境，让全人类羡慕不已。不过，谷歌这样一个以创造力为生的神奇地方，对应聘对象来说，想成为其中一员可是有着不小的难度。想进谷歌，先试试这些早已遍布互联网的谷歌面试题吧。
平分有缺失的蛋糕
三个人打算分一个矩形的蛋糕，可是有一个人已经偷偷地切走了一小块矩形的部分。如果只能直直地切一刀，那么另外两个人应该怎么切才能体积均匀地分掉剩下的部分呢?
解答： 也许有人会说：横着切，将蛋糕分成两个等高的部分就好了嘛。但是一般蛋糕上层是奶油，下层只有干巴巴的面包，所以我们不准备把这个作为答案之一。
如果这个蛋糕没有被切走一部分，应该如何平分呢?方法当然有很多，但是所有的切法都有一个共同点，那就是这一刀一定经过矩形的中心点。反之亦然，所有经过中心点的直线都能将矩形平均分成两部分。带着这个结论回到开始的问题上，如果一刀经过大小两个矩形中心点，就能将大矩形 ABCD 和小矩形 AGFE 都分成面积相等的两部分，这样，我们的问题也就解决了。
在上图中，矩形AEFG是被偷偷挖走的部分。H和I是大小两个矩形的中心，直线JLK经过这两个中心点。可以看出四边形AJLG和JLFE的面积是相等的，而四边形AJKD和JKCB的面积也是相等的，因此剩下的深蓝色与绿色的面积也是相等的。
重男轻女的地方男女的比例是多少
假设一个村子里，村民们都有重男轻女的观念，每一对夫妻都会不断地生产，直到生出一个男孩。如果生男生女的概率是一样的，那这个村子最终的男女比例应该是多少?
解答： 如果这个村子里有C对夫妻，那最后就有C个男孩。而女孩的数量呢?这是一个数学上求期望值的问题。
不妨任选一户人家来分析，设这户人家有n个女孩。如果 n = 0 ，也就是说这户人家第一次就生了个男孩，那么这个概率便是1/2。 n = 1 时，便是先女后男，概率是 1/2 * 1/2 = 1/4 。n = 2 时，便是前两次生了两个女孩，第三次生了男孩，概率是 1/2*1/2*1/2 = 1/8 。以此类推，一户人家出现n个女孩的概率是 1/2n+1 。由此可以算出一户人家女孩数量的期望值是 0 + 1/4 + 2/8 + 3/16 + … = 1 。因此，C户人家的女孩数量的期望值便是C，女孩和男孩的数量在期望上是相等的。也就是说，即使是在一个重女轻男的地方，男女比例仍然是 1 : 1 。
怎么测鸡蛋的强度最方便
现在你在一栋 100 层高的大楼门口，手头上有两颗完全一样的神奇鸡蛋。如果你想知道这两个鸡蛋最高能从多少楼摔下而不破碎，用什么策略能保证你的尝试次数尽可能少呢?
解答： 在只有一个鸡蛋时，保险起见，我们只能从一楼开始，一层一层地试验，看看鸡蛋有没有被摔烂。这样最精确，但是消耗的时间也最久。如果我们事先就知道这个鸡蛋不被摔碎的最高落下点在30层到75层之间，我们最多也只要尝试45次就能知道结果。现在我们手上有两个鸡蛋，根据上面的分析，一个合理的策略就是用第一个鸡蛋确定出一个较小的楼层范围，然后在这个范围里用第二个鸡蛋从下往上逐层尝试。
比如说让第一个鸡蛋每隔5层试验一次。当它在某一层被摔烂时，也就意味着确定了一个4层的待测试宽度(为什么是4层呢?假如鸡蛋在5楼的时候没破，10楼的时候破了，那么我们就只需要知道鸡蛋在 6 , 7 , 8 , 9 层的结果)。这时候，用第二颗鸡蛋一层一层地尝试，就能用较少的次数找出鸡蛋刚好摔不烂的高度。
需要注意的是，如果想留给第二颗鸡蛋较小的.测试宽度，就要缩短第一个鸡蛋的测试跨度。相应的，也就增加了尝试次数。为了确定合适的跨度，使得总试验次数之和尽可能小，我们可以采取如下的办法。
设跨度是L，第一颗鸡蛋的尝试次数就是[ 100/L ]，第二颗鸡蛋的尝试次数就是 L - 1，因此尝试次数总和就是 [ 100/L ] + L - 1 。根据这个公式，我们可以列出下面这个表格：
可以看出，我们只需要选 8 - 13 之间的一个宽度，都能使得总尝试次数是19次。
但问题是，这已经是最优策略了吗，有没有更好的方法呢?
有的。上面的方法固定了第一颗鸡蛋的测试跨度，如果我们灵活变动，就能使得总尝试次数变得更少。首先，我们选择从14楼丢下第一颗鸡蛋。如果它破碎了，我们就从1楼开始，逐层丢第二颗鸡蛋，最多试14次便能得到答案。如果它没有破碎，那我们往上走 13 层，在 27 楼第二次丢下第一颗鸡蛋。此时如果鸡蛋碎了，那我们只需要在 15 层到 26 层之间用第二颗鸡蛋进行最多12次试验即可，加上第一颗鸡蛋的两次尝试，仍然是14次。类似的，依次减小测试跨度，如果鸡蛋足够顽强，那我们丢下第一颗鸡蛋的楼层就分别是 14 ， 27 ， 39 ， 50 ， 60 ， 69 ， 77 ，84 ， 90 ， 95 ， 99 以及最后的100层。因为第一颗鸡蛋每多尝试一次，第二颗鸡蛋需要尝试的最大次数就减少一次，因此，总尝试次数的最大可能值一直是不变的，保持在14次。用这种方法，我们只需要不超过14次的尝试就能够找出答案。有没有更优的策略了?感兴趣的读者可以自行思考。
http://www.cnrencai.com/【死理性派教你做谷歌面试题】相关文章：
谷歌的面试题目04-11
谷歌工程师的面试题04-11
怎样回答名师哲理性面试题09-23
销售技巧：教你做人做事10-17
谷歌薪酬最高十职位10-28
教你做好面试前的准备08-01
久坐会死，椅子要命！02-10
青春派观后感05-13
圣诞美食派的做法12-11
青春派经典台词05-29