Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 转载 » 

死理性派教你做谷歌面试题

长久以来,谷歌都因为拥有世界上最自由和优越的环境,让全人类羡慕不已。不过,谷歌这样一个以创造力为生的神奇地方,对应聘对象来说,想成为其中一员可是有着不小的难度。想进谷歌,先试试这些早已遍布互联网的谷歌面试题吧。

本文转载自果壳网,原文请点击 死理性派教你做谷歌面试题

平分被有缺失的蛋糕

三个人打算分一个矩形的蛋糕,可是有一个人已经偷偷地切走了一小块矩形的部分。如果只能直直地切一刀,那么另外两个人应该怎么切才能体积均匀地分掉剩下的部分呢?

解答: 也许有人会说:横着切,将蛋糕分成两个等高的部分就好了嘛。但是一般蛋糕上层是奶油,下层只有干巴巴的面包,所以我们不准备把这个作为答案之一。

如果这个蛋糕没有被切走一部分,应该如何平分呢?方法当然有很多,但是所有的切法都有一个共同点,那就是这一刀一定经过矩形的中心点。反之亦然,所有经过中心点的直线都能将矩形平均分成两部分。带着这个结论回到开始的问题上,如果一刀经过大小两个矩形中心点,就能将大矩形 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 ) 的时间内完成了。

上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论