Google面试笔试题
谷歌笔试题：将无向无环连通图转换成深度最小的树
已知一个无向无环连通图T的所有顶点和边的信息，现需要将其转换为一棵树，要求树的深度最小，请设计一个算法找到所有满足要求的树的根结点，并分析时空复杂度。
最简单直接的方法就是把每个节点都试一遍：
假设某个节点为根节点，计算树的深度。当遍历完所有节点后，也就找到了使树的深度最小的根节点。
但这个方法的复杂度很高。如果有n个节点，则时间复杂度为O(n^2)。
树的深度取决于根节点到最深叶节点的距离，所以我们可以从叶节点入手。
叶节点会且只会和某一个节点连通(反之不成立，因为根节点也可能只和一个节点连通)，所以我们很容易找到所有可能的叶节点。
题目可以等价于找到了两个叶节点，使得两个叶节点之间的距离最远。根节点就是这两个叶节点路径的中间点(或者中间两个点的任意一个)。
我们可以每次都将连接度为1的节点删掉，直到最后只剩下1个或2个节点，则这一个节点，或者两个节点中的任意一个，就是我们要找的根节点。
谷歌笔试题：将字符串中的小写字母排在大写字母的前面
有一个由大小写组成的字符串，现在需要对它进行修改，将其中的所有小写字母排在大写字母的前面(大写或小写字母之间不要求保持原来次序)。
初始化两个int变量A和B，代表字符串中的两个位置。开始时A指向字符串的第一个字符，B指向字符串的最后一个字符。
逐渐增加A的值使其指向一个大写字母，逐渐减小B使其指向一个小写字母，交换A，B所指向的字符，然后继续增加A，减小B....。
当A>=B时，就完成了重新排序。
i指向最后一个小写字符，j寻找小写字符。
void swapString(char* str, int len) { int i=-1; int j=0; for(j=0; j<len; str[j]="" &&="" if(str[j]<="z">='a') { i++; swap(str[i], str[j]); } } }
谷歌笔试题：在重男轻女的国家里，男女的比例是多少?
在一个重男轻女的国家里，每个家庭都想生男孩，如果他们生的孩子是女孩，就再生一个，直到生下的是男孩为止。这样的国家，男女比例会是多少?
还是1：1。
在所有出生的第一个小孩中，男女比例是1：1;在所有出生的第二个小孩中，男女比例是1：1;.... 在所有出生的第n个小孩中，男女比例还是1：1。
所以总的男女比例是1：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都拷贝完成后，再将合并链表分成两个链表就可以了。
class ListNode { int value; ListNode* p_next; ListNOde* p_rand; public ListNode(int v, ListNode* next, ListNode* rand): value(v), p_next(next), p_rand(rand) { } }; ListNode*copyList(ListNode*p) { if(p!=null) { /*构建交叉数组 p0->q0->p1->q1->p2->q2...*/ ListNOde*ppre=p; ListNode*post=->next; while(pre!=null) { pre->next=newListNode(pre->value,post,pre->p_rand->p_next); pre=last; lastlast=last->p_next; } /*拆分成被拷贝数组和拷贝数组 p0->p1->p2....;q0->q1->q2....*/ ppre=p; ListNode*res=p->p_next; while(res->p_next!=null) { p->p_next=res->p_next; res->p_next=res->p_next->p_next; } returnres; }else { returnp; } }
如果在高速公路上30分钟内看到一辆车开过的几率是0.95，那么在10分钟内看到一辆车开过的几率是多少?(假设为常概率条件下)
假设10分钟内看到一辆车开过的概率是x，那么没有看到车开过的概率就是1-x，30分钟没有看到车开过的概率是(1-x)^3，也就是0.05。所以得到方程(1-x)^3 = 0.05
解方程得到x大约是0.63。
谷歌笔试题：从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名的马。
谷歌笔试题：将无向无环连通图转换成深度最小的树
已知一个无向无环连通图T的所有顶点和边的信息，现需要将其转换为一棵树，要求树的深度最小，请设计一个算法找到所有满足要求的树的根结点，并分析时空复杂度。
最简单直接的方法就是把每个节点都试一遍：
假设某个节点为根节点，计算树的深度。当遍历完所有节点后，也就找到了使树的深度最小的根节点。
但这个方法的复杂度很高。如果有n个节点，则时间复杂度为O(n^2)。
树的深度取决于根节点到最深叶节点的距离，所以我们可以从叶节点入手。
叶节点会且只会和某一个节点连通(反之不成立，因为根节点也可能只和一个节点连通)，所以我们很容易找到所有可能的叶节点。
题目可以等价于找到了两个叶节点，使得两个叶节点之间的距离最远。根节点就是这两个叶节点路径的中间点(或者中间两个点的任意一个)。
我们可以每次都将连接度为1的节点删掉，直到最后只剩下1个或2个节点，则这一个节点，或者两个节点中的任意一个，就是我们要找的根节点。
谷歌笔试题：将字符串中的小写字母排在大写字母的前面
有一个由大小写组成的字符串，现在需要对它进行修改，将其中的所有小写字母排在大写字母的前面(大写或小写字母之间不要求保持原来次序)。
初始化两个int变量A和B，代表字符串中的两个位置。开始时A指向字符串的第一个字符，B指向字符串的最后一个字符。
逐渐增加A的值使其指向一个大写字母，逐渐减小B使其指向一个小写字母，交换A，B所指向的字符，然后继续增加A，减小B....。
当A>=B时，就完成了重新排序。
i指向最后一个小写字符，j寻找小写字符。
void swapString(char* str, int len) { int i=-1; int j=0; for(j=0; j<len; str[j]="" &&="" if(str[j]<="z">='a') { i++; swap(str[i], str[j]); } } }
谷歌笔试题：在重男轻女的国家里，男女的比例是多少?
在一个重男轻女的国家里，每个家庭都想生男孩，如果他们生的孩子是女孩，就再生一个，直到生下的是男孩为止。这样的国家，男女比例会是多少?
还是1：1。
在所有出生的第一个小孩中，男女比例是1：1;在所有出生的第二个小孩中，男女比例是1：1;.... 在所有出生的第n个小孩中，男女比例还是1：1。
所以总的男女比例是1：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都拷贝完成后，再将合并链表分成两个链表就可以了。
class ListNode { int value; ListNode* p_next; ListNOde* p_rand; public ListNode(int v, ListNode* next, ListNode* rand): value(v), p_next(next), p_rand(rand) { } }; ListNode*copyList(ListNode*p) { if(p!=null) { /*构建交叉数组 p0->q0->p1->q1->p2->q2...*/ ListNOde*ppre=p; ListNode*post=->next; while(pre!=null) { pre->next=newListNode(pre->value,post,pre->p_rand->p_next); pre=last; lastlast=last->p_next; } /*拆分成被拷贝数组和拷贝数组 p0->p1->p2....;q0->q1->q2....*/ ppre=p; ListNode*res=p->p_next; while(res->p_next!=null) { p->p_next=res->p_next; res->p_next=res->p_next->p_next; } returnres; }else { returnp; } }
如果在高速公路上30分钟内看到一辆车开过的几率是0.95，那么在10分钟内看到一辆车开过的几率是多少?(假设为常概率条件下)
假设10分钟内看到一辆车开过的概率是x，那么没有看到车开过的概率就是1-x，30分钟没有看到车开过的概率是(1-x)^3，也就是0.05。所以得到方程(1-x)^3 = 0.05
解方程得到x大约是0.63。
谷歌笔试题：从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名的马。
【Google面试笔试题】相关文章：
2017年Google的面试流程03-28
给学弟学妹的求职笔面试总结03-18
面试笔试题03-22
有关面试的笔试题03-19
护士面试笔试题03-19
华为硬件面试题08-22
华为面试笔试题08-19
人事面试笔试题08-14
小升初面试笔试及面试题目03-17
面试热点：精准扶贫面试试题及答案03-26