平分被有缺失的蛋糕
三个人打算分一个矩形的蛋糕，可是有一个人已经偷偷地切走了一小块矩形的部分。如果只能直直地切一刀，那么另外两个人应该怎么切才能体积均匀地分掉剩下的部分呢？
解答： 也许有人会说：横着切，将蛋糕分成两个等高的部分就好了嘛。但是一般蛋糕上层是奶油，下层只有干巴巴的面包，所以我们不准备把这个作为答案之一。
如果这个蛋糕没有被切走一部分，应该如何平分呢？方法当然有很多，但是所有的切法都有一个共同点，那就是这一刀一定经过矩形的中心点。反之亦然，所有经过中心点的直线都能将矩形平均分成两部分。带着这个结论回到开始的问题上，如果一刀经过大小两个矩形中心点，就能将大矩形 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 。根据这个公式，我们可以列出下面这个表格：
间隔 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
次数 100 51 35 29 25 21 20 19 19 19 19 19 19 20 20 21
可以看出，我们只需要选 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次的尝试就能够找出答案。有没有更优的策略了？感兴趣的读者可以自行思考。
孩子多大了
两个数学家在某次会议上又见面了——他们是老朋友，可是有十几年没见了。
老张：这些年怎么样啊。
小王：挺好的，我结婚了，现在都是三个孩子的爸爸了。
老张：那很幸福啊，孩子们多大了？
小王：他们年龄乘积是72，年龄的和与你的出生日期一样（8月的某号）。
老张：我还是猜不出来。
小王：我的大儿子刚开始学钢琴。
老张：哦，我知道了！
问：小王的三个儿子分别多大呢？
解答： 这道题的思考比较繁琐，让我们一步一步地分析。
三个孩子年龄的乘积是72。年龄的和是8月份的某一号，也就是是在 1 ~ 31 之间。我们首先把符合所有上面两个条件的数列出来。
72 = 2 * 2 * 2 * 3 * 3，考虑最小的孩子，年龄只可能是1,2,3，然后穷举另外两个孩子，找出满足年龄和条件的所有情况：
1 3 24, sum = 28
1 4 18, sum = 23
1 6 12, sum = 19
1 8 9, sum = 18
2 2 18, sum = 22
2 3 12, sum = 17
2 4 9, sum = 15
2 6 6, sum = 14
3 3 8, sum = 14
3 4 6, sum = 17
这是根据小王的一句话所能得到的信息。虽然我们不知道老张的生日是几号，但老张自己肯定知道，所以他只要找出哪个数对的和与自己的生日相同便能确定。可是他却说“我还是猜不出来”，那就表明和等于他自己生日的数对不止一个。因此可筛选出如下两组数：
2, 6, 6
3, 3, 8
这两组数的和都是14，所以老张无法判断。这时小王说“我的大儿子刚开始学钢琴”。在 2 , 6 , 6 和 3 , 3 , 8 中，能确定大儿子的是第二组。所以到这里，老张就知道了小王三个孩子的年龄。这个问题本身并不算难，但如果被当面问这个问题并要求很快答出来，那就需要一定能力了。
货真价实的谷歌面试题
不同于上面的“流传”，下面两道是已被确认了的google面试题。
第一题，给你一个长度为 N 的链表。N 很大，但你不知道 N 有多大。你的任务是从这 N 个元素中随机取出 k 个元素。你只能遍历这个链表一次，且必须保证取出的元素是完全随机的（出现概率均等）。
第二题，给你一个数组 A [ 1 .. n ] ，请你在 O ( n ) 的时间里构造一个新的数组 B [ 1 .. n ] ，使得 B [ i ] = A [ 1 ] * A [ 2 ] * … * A [ n ]／A [ i ] 。你不能使用除法运算。
这两道题目看起来很专业，但有趣的是，即使没有学过信息学的人也可以想到答案。
第一题的意思就是有一大串物品，它们能且仅能逐个经过你眼前一次。你不知道它们的个数，要求你从中随机地抽取 k 个物品，同时必须保证取出的元素是完全随机的（出现概率均等）。
第二题给出了一个数列 A [ 1 .. n ] ，要求在较短的时间内不用除法构造一个新数列 B [ 1 .. n ] ，使得 B [i] = A [ 1 ] * A [ 2 ] * … * A [ n ]／A [ i ] 。 n是这个数组的长度。而 O ( n ) 是评判计算方法速度的标准。如果一个解答方法在n任意变化的情况下，都能满足总共的计算次数相当于是 n 乘以一个常数C这个条件，那么就称这个解答方法是 O ( n ) 的；如果这个解答方法能满足总共的计算次数是 n 2 乘以常数C，那么这个解答方法就被称作是 O ( n 2 ) 的。
第一题没有告诉我们物品的个数N，所以我们没法算出 k／N，连最基本的每样物品被选中的概率都不知道，还怎么继续操作呢？既然我们不知道一共有多少个物品，那我们就应该在所有的物品都经过我们眼前之后再做抉择。当每个物品经过我们眼前的时候，可以设法对应地给它生成一个 0 到 1 之间的随机数。等到我们见过了所有的物品之后，只需要选择对应的随机数最大的前 k 个物品就行了。
第二题不允许用除法增加了不少难度。 B [ i ] 不用除法来表示的话就是： B [ i ] = A [ 1 ] * … * A [ i - 1 ] * A [ i + 1 ] * … * A [ n ] 。若按照这个表达式进行计算，生成每个 B[ i ] 的时候要进行n – 1次乘法，这样一来完全生成 B [ 1 .. n ] 就需要 O ( n 2 ) 的时间了。我们需要通过减少重复的运算来提高效率。
注意到 B [ i ] 可以看作是两个部分的乘积， A [ 1 ] * … * A [ i - 1 ] 和 A [ i + 1 ] * … * A [ n ] 。同理 B [ i + 1 ] 就由 A [ 1 ] * … * A [ i - 1 ] * A [ i ] 和 A [ i + 2 ] * … * A [ n ] 组成。计算 B [ i ] 时的许多乘法在计算 B [ i + 1 ] 的时候又进行了一遍，因此可以重复利用上一次运算的结果，以避免无谓的运算。从这点出发，我们构造两个新的数列：
S [ i ] = A [ 1 ] * … * A [ i – 1 ]
T [ i ] = A [ i + 1 ] * … * A [ n ]
因为生成完整的 S [ 1 .. n ] 和 T [ 1 .. n ] 都能在 O ( n ) 的时间内完成，那么根据 B [ i ] = S [ i ] * T [ i ] 这条式子，生成整个 B [ 1 .. n ] 便也能够在 O ( n ) 的时间内完成了。
Read full article from 死理性派教你做谷歌面试题 » NoAlGo博客
