Google面试笔试题

《Google面试笔试题》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、Google面试笔试题　　　　谷歌笔试题：将无向无环连通图转换成深度最小的树　　　　已知一个无向无环连通图T的所有顶点和边的信息现需要将其转换为一棵树要求树的深度最小请设计一个算法找到所有满足要求的树的根结点并分析时空复杂度　　　　最简单直接的方法就是把每个节点都试一遍：　　　　假设某个节点为根节点计算树的深度当遍历完所有节点后也就找到了使树的深度最小的根节点　　　　但这个方法的复杂度很高如果有n个节点则时间复杂度为O(n^2)　　　　树的深度取决于根节点到最深叶节点的距离所以我们可以从叶节点入

2、手　　　　叶节点会且只会和某一个节点连通(反之不成立因为根节点也可能只和一个节点连通)所以我们很容易找到所有可能的叶节点　　　　题目可以等价于找到了两个叶节点使得两个叶节点之间的距离最远根节点就是这两个叶节点路径的中间点(或者中间两个点的任意一个)　　　　我们可以每次都将连接度为1的节点删掉直到最后只剩下1个或2个节点则这一个节点或者两个节点中的任意一个就是我们要找的根节点　　　　谷歌笔试题：将字符串中的小写字母排在大写字母的前面　　　　有一个由大小写组成的字符串现在需要对它进行修改将其中的所有

3、小写字母排在大写字母的前面(大写或小写字母之间不要求保持原来次序)　　　　初始化两个int变量A和B代表字符串中的两个位置开始时A指向字符串的第一个字符B指向字符串的最后一个字符　　　　逐渐增加A的值使其指向一个大写字母逐渐减小B使其指向一个小写字母交换AB所指向的字符然后继续增加A减小B....　　　　当A>=B时就完成了重新排序　　　　i指向最后一个小写字符j寻找小写字符　　　　voidswapString(char*str,intlen){inti=1;intj=0;for(j=0;j='

4、a'){i++;swap(str[i],str[j]);}}}　　　　谷歌笔试题：在重男轻女的国家里男女的比例是多少?　　　　在一个重男轻女的国家里每个家庭都想生男孩如果他们生的孩子是女孩就再生一个直到生下的是男孩为止这样的国家男女比例会是多少?　　　　还是1：1　　　　在所有出生的第一个小孩中男女比例是1：1;在所有出生的第二个小孩中男女比例是1：1;....在所有出生的第n个小孩中男女比例还是1：1　　　　所以总的男女比例是1：1　　　　谷歌笔试题：如何拷贝特殊链表　　　　有一个特殊的链表其

5、中每个节点不但有指向下一个节点的指针pNext还有一个指向链表中任意节点的指针pRand如何拷贝这个特殊链表?　　　　拷贝pNext指针非常容易所以题目的难点是如何拷贝pRand指针　　　　假设原来链表为A1>A2>...>An新拷贝链表是B1>B2>...>Bn　　　　为了能够快速的找到pRand指向的节点并把对应的关系拷贝到B中我们可以将两个链表合并成　　　　A1>B1>A2>B2>...>An>Bn　　　　从A1节点出发很容易找到A1的pRand指向的节点Ax,然后也就找到了Bx将B1的p

6、Rand指向Bx也就完成了B1节点pRand的拷贝依次类推　　　　当所有节点的pRand都拷贝完成后再将合并链表分成两个链表就可以了　　　　classListNode{intvalue;ListNode*pnext;ListNOde*prand;publicListNode(intv,ListNode*next,ListNode*rand):value(v),pnext(next),prand(rand){}};ListNode*copyList(ListNode*p){if(p=null){/

7、*构建交叉数组p0>q0>p1>q1>p2>q2...*/ListNOde*ppre=p;ListNode*post=>next;while(pre=null){pre>next=newListNode(pre>value,post,pre>prand>pnext);pre=last;lastlast=last>pnext;}/*拆分成被拷贝数组和拷贝数组p0>p1>p2....;q0>q1>q2....*/ppre=p;ListNode*res=p>pnext;while(res>pnext=

8、null){p>pnext=res>pnext;res>pnext=res>pnext>pnext;}returnres;}else{returnp;}}　　　　如果在高速公路上30分钟内看到一辆车开过的几率是0.95那么在10分钟内看到一辆车开过的几率是多少?(假设为常概率条件下)　　　　假设10分钟内看到一辆车开过的概率是x那么没有看到车开过的概率就是1x30分钟没有看到车开过的概率是(1x)^3也就是0.05所以得到方程(1x)^3=0.05　　　　解方程得到x大约是0.63　　　　谷歌笔