现在的位置: 首页 > 综合 > 正文

谷歌笔试题整理(二)

2017年08月03日 ⁄ 综合 ⁄ 共 2598字 ⁄ 字号 评论关闭

谷歌是不少IT人都想去的企业,笔试和面试是必经之路,现在校园招聘的季节,突击和整理IT名企经典笔试题是拿到offer的捷径!为此在网络上整理了些非常经典的笔试题目和答案,仔细阅读必有帮助!!

1.谷歌笔试题:如何拷贝特殊链表

有一个特殊的链表,其中每个节点不但有指向下一个节点的指针pNext,还有一个指向链表中任意节点的指针pRand,如何拷贝这个特殊链表?

拷贝pNext指针非常容易,所以题目的难点是如何拷贝pRand指针。

假设原来链表为A1 -> A2 ->... -> An,新拷贝链表是B1 -> B2 ->...-> Bn。

为了能够快速的找到pRand指向的节点,并把对应的关系拷贝到B中。我们可以将两个链表合并成

A1 -> B1 -> A2 -> B2 -> ... -> An -> Bn。

从A1节点出发,很容易找到A1的pRand指向的节点Ax,然后也就找到了Bx,将B1的pRand指向Bx也就完成了B1节点pRand的拷贝。依次类推。

当所有节点的pRand都拷贝完成后,再将合并链表分成两个链表就可以了。

2.谷歌笔试题

如果在高速公路上30分钟内看到一辆车开过的几率是0.95,那么在10分钟内看到一辆车开过的几率是多少?(假设为常概率条件下)

假设10分钟内看到一辆车开过的概率是x,那么没有看到车开过的概率就是1-x,30分钟没有看到车开过的概率是(1-x)^3,也就是0.05。所以得到方程(1-x)^3 = 0.05

解方程得到x大约是0.63。

3.谷歌笔试题:从25匹马中找出最快的3匹

最少需要7次。

首先将马分成a,b,c,d,e 5个组,每组5匹,每组单独比赛。然后将每组的第一名放在一起比赛。假设结果如下

a0,a1,a2,a3,a4

b0,b1,b2,b3,b4

c0,c1,c2,c3,c4

d0,d1,d2,d3,d4

e0,e1,e2,e3,e4

其中a, b,c,d,e小组都是按照名次排列(速度a0>a1>a2>a3>a4, b0>b1....)。并第6次比赛的结果为a0>b0>c0>d0>e0。

那么第6次比赛结束后,我们知道最快的一匹为a0。

我们知道第2名的马一定是a1或者b0,所以在接下来的比赛中要包含这两匹马。如果a1快,那么第3名是a2或者b0,如果b0快,那么第3名是a1,b1或者c0。也就是说第2名和第3名一定在a1,a2,b0,b1和c0当中,所以在第7场比赛中包括这5匹马就可以得到第2名和第3名。

所以7次比赛就可以获得前3名的马。 

4.谷歌笔试题:海盗分金问题

有5个海盗,按照等级从5到1排列。最大的海盗有权提议他们如何分享100枚金币。但其他人要对此表决,如果多数(所有人中的多数)反对,那他就会被杀死。他应该提出怎样的方案,既让自己拿到尽可能多的金币又不会被杀死?

分配方案是98,0,1,0,1。

5级海盗会不会被杀死,取决于5级海盗死后其他海盗是否会获得更多的利益。如果可以获得更多的利益,则肯定会反对,如果会获得更少的利益,则肯定会支持,如果利益没有变化,则反对或支持都可以。

如果5级海盗死了,则有4级海盗分配,4级海盗面临同样的问题,需要看自己死后的利益分配变化。然后是3级海盗,2级海盗。

2级海盗无论提出什么方案,都不会有多数人反对(自己支持,另一个人反对不能构成多数反对)。所以2级海盗肯定会提出100,0的分配方案,自己独享所有金币。

猜到2级海盗的分配方案后,3级海盗会提出99,0,1的分配方案。这样1级海盗因获得了比2级海盗方案中更多的金币,所以会支持3级海盗的方案。

猜到3级海盗的分配方案后,4级海盗会提出99,0,1,0的分配方案。这样2级海盗获得了比3级海盗方案中更多的金币,所以会支持4级海盗的方案。

猜到4级海盗的分配方案后,5级海盗会提出98,0,1,0,1的分配方案。这样1级海盗和3级海盗获得了比4级海盗方案中更多的金币,所以会支持5级海盗的方案。

5. 谷歌笔试题:4人过桥问题

4 个人晚上要穿过一座索桥回到他们的营地。可惜他们手上只有一支只能再坚持17分钟的手电筒。通过索桥必须要拿着手电,而且索桥每次只能撑得起两个人的份量。这四个人过索桥的速度都不一样,第一个走过索桥需要1分钟,第二个2分钟,第三个5分钟,最慢的那个要10分钟。他们怎样才能在17分钟内全部走过索桥?

1)第一个和第二个一起过去,用掉2分钟;

2)第一个回来,用掉1分钟;

3)第三个和第四个一起过去,用掉10分钟;

4)第二个回来,用掉2分钟;

5)第一个和第二个一起过去,用掉2分钟。

总共用掉17分钟。

6. 谷歌笔试题:如何从8只球中找出比较重的一个

你有8个一样大小的球,其中7个的重量是一样的,另一个比较重。怎样能够用天平仅称两次将那个重一些的球找出来。

解答:

先取6个,天平上一边3个,同重则称剩余2个即可;不同重,则取重的3个中的2个来称。

分析:

此题可以通过倒推法来解决。

如果我们知道重球在某两个球中,则可以通过天平两边各放一个,比较重量发现重球。

如果我们知道重球在某三个球中,则可以通过天平两边各放一个,如果一样重,则第三个球是重球,否则天平上较重的即是重球。

如果我们知道重球在大于等于四个球中,则不能通过一次称重发现重球。

所以通过第一次称重,我们必须将重球限定在某两个或三个球当中。另外,天平两端放的球数应该相等,否则结果基本没有意义。

满足两端球相等的所有可能的比较方法

左,右

1, 1

2, 2

3, 3

4, 4

再考虑到必须将重球限定在2或3个球中,第一次只能采取3,3的比较方法。

此题还可以扩展一下:在m只大小相同的球中,m-1只重量相同,另外一只比较重。问需要用天平称多少次才能将重球找出来?

从上面的分析中可以知道,称一次最多可以

- 将重球从3个球中找出来。

- 将重球从9个球中限定在3个球中。

- 将重球从27个球中限定在9个球中。

.....

所以,称n次最多可以将重球从3^n中找出来。倒推回去也就可以获得m个球需要称多少次。

或者

我们用i+表示第i个球比较重。

共有8种可能性:1+; 2+; 3+; 4+; 5+; 6+; 7+; 8+;

将1 2 3 与4 5 6 放在天秤上称,如果左边中,则可以将重球确定在1 2 3中,

即可能性为:1+ 2+ 3+ 然后将1和2放在天秤两边称,如果左边重则重球为1,如果右边重,重球为2,如果平衡重球为3。

如果平衡:7+ 8+ 将7和8放在天秤两边称,可以判断重球为7还是8

如果右边重:4+ 5+ 6+ 同球1 2 3的情况

抱歉!评论已关闭.