google 笔试题汇总 (转载).doc

google 笔试题汇总 (转载).txt跌倒了，爬起来再哭低调！才是最牛B的炫耀！不吃饱哪有力气减肥啊？真不好意思，让您贱笑了。我能抵抗一切，除了诱惑老子不但有车，还是自行的google 笔试题汇总 (转载) 2008-10-07 1726 (分类默认分类) 一、单选1、80x86中，十进制数-3用16位二进制数表示为？00100002、假定符号-、$分别代表减法、乘法和指数运算，且1)三个运算符优先级顺序是：-最高，其次，$最低；2)运算符运算时为左结合。请计算3-24$12$3的值：(A)4096，(B)-61，(C)64，(D)-80，(E)512算符3、下列伪代码中，参数是引用传递，结果是？calc(double p, double q, double r)q=q-1.0;r=r+pmain()double a = 2.5, b = 9.0;calc(b-a, a, a);print(a);(A)1.5 (B)2.5 (C)10.5 (D)8 (E)6.54、求输出结果：int foo(int x, int y)if(x =0 y = 0) return 1;return 3 foo(x - 1, y 2);printf(%dn, foo(3, 5);(A)81 (B)27 (C)9 (D)3 (E)15、下列哪个数据结构在优先队列中被最广泛使用？a(A)堆 (B)数组 (C)双向链表 (D)图 (E)向量6、以下算法描述了一个在n国元素的双向链表中找到第k个元素的方法（k = 1且k = n）：如果k = n - k，从链表开始往前进k-1个元素。否则，从终点出发，往回走n - k个元素。这个算法的时间代价是？(A)(nlogn) (B)(maxk, n - k) (C)(k + (n - k) (D)(maxk, k - n) (E)(mink, n - k)7、有一个由10个顶点组成的图，每个顶点有6个度，那么这个图有几条边？30(A)60 (B)30 (C)20 (D)80 (E)908、正则表达式L = x(xyx+)。下列哪个字符串不符合L b(A)x (B)xyxyx (C)xyx (D)yxx (E)yx9、为读取一块数据而准备磁盘驱动器的总时间包括e(A)等待时间 (B)寻道时间 (C)传输时间 (D)等待时间加寻道时间 (E)等待时间加寻道时间加传输时间二、算法1、打印出一个二叉树的内容。2、在一个字符串中找到第一个只出现一次的字符。如abaccdeff，输出b。3、给定一个长度为N的整数数组（元素有正有负），求所有元素之和，最大的一个子数组。分析算法时空复杂度。不必写代码。附上动态规划做法的答案最大子序列问题：给定一整数序列A1， A2，. An （可能有负数），求A1An的一个子序列AiAj，使得Ai到Aj的和最大例如：整数序列-2, 11, -4, 13, -5, 2, -5, -3, 12, -9的最大子序列的和为21。对于这个问题，最简单也是最容易想到的那就是穷举所有子序列的方法。利用三重循环，依次求出所有子序列的和然后取最大的那个。当然算法复杂度会达到O(n3)。显然这种方法不是最优的，下面给出一个算法复杂度为O(n)的线性算法实现，算法的来源于Programming Pearls一书。在给出线性算法之前，先来看一个对穷举算法进行优化的算法，它的算法复杂度为O(n2)。其实这个算法只是对对穷举算法稍微做了一些修改：其实子序列的和我们并不需要每次都重新计算一遍。假设Sum(i, j)是Ai . Aj的和，那么Sum(i, j+1) = Sum(i, j)+ Aj+1。利用这一个递推，我们就可以得到下面这个算法：int max_sub(int a,int size)int i,j,v,max=a0;for(i=0;isize;i+)v=0;for(j=i;jsize;j+)v=v+aj;Sum(i, j+1) = Sum(i, j) + Aj+1if(vmax)max=v;return max;那怎样才能达到线性复杂度呢？这里运用动态规划的思想。先看一下源代码实现：int max_sub2(int a, int size)int i,max=0,temp_sum=0;for(i=0;isize;i+)temp_sum+=ai;if(temp_summax)max=temp_sum;else if(temp_sum0)temp_sum=0;return max;在这一遍扫描数组当中，从左到右记录当前子序列的和temp_sum，若这个和不断增加，那么最大子序列的和max也不断增加(不断更新max)。如果往前扫描中遇到负数，那么当前子序列的和将会减小。此时temp_sum将会小于max，当然max也就不更新。如果temp_sum降到0时，说明前面已经扫描的那一段就可以抛弃了，这时将temp_sum置为0。然后，temp_sum将从后面开始将这个子段进行分析，若有比当前max大的子段，继续更新max。这样一趟扫描结果也就出来了。 三道大题第一个还蛮简单，是向双向列表插入一个节点，第二个问题比较恶心，判断A字符串中的各个字符数目是否不大于B字符串中的各个字符数目，由于没时间了就没写完，第三题更是相当及其以及特别的恶心，找到整数数组中满足AB=C的元素，而且要更优的，算了半天的时间复杂度还是没写出来。 1、假设在n进制下，下面的等式成立，n值是（）567456=150216a、 9 b、 10 c、 12 d、 182、文法GS-uvSvuw所识别的语言是：（）a、uvwvu b、（uvwvu） c、uv(uv)wvu(vu) d、(uv)w(vu)3、如下程序段输出是：（）char str10=Hello,Google;char p=str0;countstrlen(p+10);a、0 b、5 c、6 d、104、cnt=0while(x!=1)cnt=cnt+1;if(x&1=0)x=x2;elsex=3x+1;countcntend1;当n=11时，输出：（）a、12 b、13 c、14 d、155、写一段程序判断一个有向图G中节点w是否从节点v可达。（如果G中存在一条从v至w的路径就说节点w是从v可达的）。以下算法是用C+写成的，在bool Reachable函数中，你可以写出自己的算法。class Graphpublicint NumberOfNodes();返回节点的总数bool HasEdge(int u,int v);u,v是节点个数，从零开始依次递增，当有一条从u到v的边时，返回true；bool Reachable(Graph&G, int v, int w)请写入你的算法6、给定一棵所有边的长度均为整数的树，现要求延长其中某些边，使得从根到任意节点的路径长度相等。问满足要求的树的边长度之和最小是多少请写出你的算法，并分析时间复杂度。 longest leaf欢迎回复，给出你的解答。回来说说昨天的笔试。题目的量并不大，除了几个单选题，剩下就是三个编程或算法题。单选就不说了，考得比较基础，涉及C语言常识、数据结构、文法、操作系统，主要说说大题。大题虽然题型不一，但都有一个重要特点：考递归。精确点说，我每一题都用到了递归。第一个的题目（嗯，记的不是很完整）：在一棵（排序？）二叉树中搜索指定值，数据结构定义为（唉唉，数据结构的具体名字都不记得了，my god）：struct Node Node lnext; Node rnext; int value;函数定义为（情况同上，啥都记不清了）：Node search(Node root, int value)实现这个search函数。用递归，经典的树的遍历，pass先。第二个的题目：计算Tribonaci队列（嗯，九成九记错了那个单词），规则是T(n) = T(n - 1) + T(n - 2) + T(n -3)，其中T(0) = T(1) = 1，T(2) = 2。函数定义：int Tribonaci(int n) 备注，不考虑证整数溢出，尽可能优化算法。这一题我一看就知道要考什么，很显然的递归定义，但也是很显然的，这里所谓的优化是指不要重复计算。简单的说，在计算T(n)的时候要用到T(n - 1)、T(n - 2)和T(n - 3)的结果，在计算T(n -1)的时候也要用到T(n - 2)和T(n -3)的结果，所以在各项计算的时候必须把以前计算的结果记录下来，去掉重复计算。这里用到的一点小技巧就是要新写一个函数用来做这种事情，嗯，看看我写的代码吧！ Get the value of T(n - 1), and retrieve the result of T(n - 2) and T(n - 3). paramin n The n in T(n). paramout mid Value of T(n - 2). paramout right Value of T(n - 3). return Value of T(n - 1). int find_trib(int n, int & mid, int & right) if (3 = n) mid = 1; right = 1; return 2; else int temp; mid = find_trib(n - 1, right, temp); return mid + right + temp; Find value of T(n). paramin The n in T(n). return Value of T(n). note T(n) = T(n - 1) + T(n - 2) + T(n - 3) (n 2) T(0) = T(1) = 1, T(2) = 2. int tribonaci(int n) if (n 0) Undefined feature. return 0; if (0 = n 1 = n) return 1; if (2 = n) return 2; int mid, right; int left = find_trib(n, mid, right); return left + mid + right;啊啊，对了，答卷的时候我可没心情写注释刚才到VC.Net 2003上测试了一下，貌似没有啥问题。唉，看来我多少还是懂一点算法的第三个的题目：在一个无向图中，寻找是否有一条距离为K的路径，描述算法即可，不用实现，分析算法的时间和空间复杂度，尽量优化算法。 dfs 计数好容易等到 Google 来了。几个月来一直在看 AIC，但是临场的时候，脑子里所有的排序算法的复杂度都变成了 O(nlg(n)，全忘了！勉强写完，考得稀里糊涂的。感觉希望不大。虽然 Google 把保密工作做的很好，要求我们在笔试完后把草稿也上交。但是我忍不住想把今天的题目记下来，记下来！笔试被分为两部分，前一部分为选择题，后一部分为问答题。和预料的一样，大多是数据结构和算法的题目。堆排序、快速排序、归并排序等几种经典排序算法是否 stablegarbage collection 使用从根节点遍历，如果没有引用到，则认为可以清除。下面哪些不属于根节点正在运行的函数的参数寄存器中的值在堆上动态分配的空间全局变量局部变量最差情况下找出第7大元素，需要的时间复杂度为 O(nln(n) 的数据结构为双向链表已排序的数组平衡二叉树两个函数 g(x), f(x) 相互递归调用，问 f(x) 随 x 增长，其计算的时间复杂度为何编写程序计算两个 NN 矩阵相乘不用递归，打印一棵二叉树设有正实数序列 S，求最大的 C，满足 C = A + B，且 A、B、C 都存在于 S 中，给出算法的时间复杂度、空间复杂度的分析。不用代码实现。后面三道题就是这次笔试所有的问答题。前面的选择题中其他几题都是给程序，让推算计算结果，或者判断循环不变式（即在循环中恒成立的等式）的。这里就不提了，况且我也记不清楚了。就谈谈后面几题。矩阵相乘，学过矩阵论的同学想来都不成问题。这个题目的关键是提高程序的性能。我看过 CSAPP，这本书对程序优化有着不错的介绍。当时我能想起来的就是 code motion 和 loop un-folding。前者很方便，把cij += aikbkj 变成 sum += aikbkj，最后再把 sum 赋给aij 能减少存储器的引用。而后者则需要判断 N 是否能被并行数（即循环展开的级数）整除，以及处理剩下的 aik 和bkj 的问题。当时觉得太麻烦，就没有做了。现在看来也不太麻烦。打印二叉树。我用的是经典的借助栈的办法。其实这种算法也有可以改进的空间。比如说，每次压栈的内容都会在下一次弹出，这就很没有必要。可以在循环里面直接更新 node指针。但是当时觉得有些繁琐，而且害怕把算法改错，就没有把改进的算法写完。这些改进的方式在 AIC 里都说得很清楚。是我学艺不精。这个题目作为压轴，Google 肯定是有充分的考虑的。不过我没有想出比较精妙的算法。只是先用 quick sort 将 S 排序再从取数组最后一个元素作为 C 的候选人，在前面 n-1 个元素中找能匹配的A和B。如果找不到，C后向前移动。在前面 n - 1 个元素中找能匹配的 A 和 B 有一个需要注意的就是：从后往前移动 B 顺序找的话，只需要找到 ceil(C2)就可以了，因为剩下的候选者的和都是小于 C 的。确定 B = Sb 之后，找 A 可以在S0.b-1之间使用二叉搜索查找。整个算法的时间复杂度为 O(n2ln(N) 另外，如果 S 很小的话， quick sort 可以换成 selection sort如果 S 元素的取值范围很小，而且均为整数的话，可以使用定长的数组 TMaxN 来辅助排序和查找，比如，排序可以这样 for i in S Ti += 1 搜索则可以 return Ti 可以看出，排序的复杂度降到了为 O(n)，搜索则降到了 O(1)。整个算法的时间复杂度为 O(n2) 1、（a）双向链表，无序 （b）从小到大升序排列的数组 （c）均衡的二分树在上述3项里找出第7个大的数的最坏情况时间复杂度是logN的是哪个？ 2、对一个数列进行排序，若排序完后该队列中相同的数字的相对位置没有改变的称为稳定排序问：下列算法哪些是稳定排序？ a b c ea 基数排序 b 插入排序c 桶排序d 选择排序e 归并排序 3、写出一个可以做矩阵乘法的程序（这个很简单。可是我做了件傻事情。） 4、打印一棵二叉数，节点下有左子女，右子女、父母、和值。（我不知道在没有标志位的情况下如何进行遍历，书上遍历也用到标志位啊，结果就只能修改值了。） 5、对于一个正数数组，找出一个最大的值C，让C = A + B，A，B，C都是队列里不同的数（这个貌似以前做到过，但结果还是忘记了。） 数据结构面试大全 1.判断链表是否存在环型链表问题：判断一个链表是否存在环，例如下面这个链表就存在一个环：例如N1-N2-N3-N4-N5-N2就是一个有环的链表，环的开始结点是N5这里有一个比较简单的解法。设置两个指针p1，p2。每次循环p1向前走一步，p2向前走两步。直到p2碰到NULL指针或者两个指针相等结束循环。如果两个指针相等则说明存在环。 struct link int data; link next; bool IsLoop(link head) link p1=head, p2 = head; if (head =NULL head-next =NULL) return false; do p1= p1-next; p2 = p2-next-next; while(p2 & p2-next & p1!=p2); if(p1 = p2) return true; else return false;2,链表反转 单向链表的反转是一个经常被问到的一个面试题，也是一个非常基础的问题。比如一个链表是这样的： 1-2-3-4-5 通过反转后成为5-4-3-2-1。最容易想到的方法遍历一遍链表，利用一个辅助指针，存储遍历过程中当前指针指向的下一个元素，然后将当前节点元素的指针反转后，利用已经存储的指针往后面继续遍历。源代码如下： struct linka int data; linka next; void reverse(linka& head) if(head =NULL) return; linkapre, cur, ne; pre=head; cur=head-next; while(cur) ne = cur-next; cur-next = pre; pre = cur; cur = ne; head-next = NULL; head = pre;还有一种利用递归的方法。这种方法的基本思想是在反转当前节点之前先调用递归函数反转后续节点。源代码如下。不过这个方法有一个缺点，就是在反转后的最后一个结点会形成一个环，所以必须将函数的返回的节点的next域置为NULL。因为要改变head指针，所以我用了引用。算法的源代码如下： linka reverse(linka p,linka& head) if(p = NULL p-next = NULL) head=p; return p; else linka tmp = reverse(p-next,head); tmp-next = p; return p; 3,判断两个数组中是否存在相同的数字 给定两个排好序的数组，怎样高效得判断这两个数组中存在相同的数字？这个问题首先想到的是一个O(nlogn)的算法。就是任意挑选一个数组，遍历这个数组的所有元素，遍历过程中，在另一个数组中对第一个数组中的每个元素进行binary search。用C+实现代码如下： bool findcommon(int a,int size1,int b,int size2) int i; for(i=0;isize1;i+) int start=0,end=size2-1,mid; while(start=end) mid=(start+end)2; if(ai=bmid) return true; else if (aibmid) end=mid-1; else start=mid+1; return false;后来发现有一个 O(n)算法。因为两个数组都是排好序的。所以只要一次遍历就行了。首先设两个下标，分别初始化为两个数组的起始地址，依次向前推进。推进的规则是比较两个数组中的数字，小的那个数组的下标向前推进一步，直到任何一个数组的下标到达数组末尾时，如果这时还没碰到相同的数字，说明数组中没有相同的数字。 bool findcommon2(int a, int size1, int b, int size2) int i=0,j=0; while(isize1 & jsize2) if(ai=bj) return true; if(aibj) j+; if(aibj) i+; return false;4,最大子序列 问题：给定一整数序列A1， A2，. An （可能有负数），求A1An的一个子序列AiAj，使得Ai到Aj的和最大例如：整数序列-2, 11, -4, 13, -5, 2, -5, -3, 12, -9的最大子序列的和为21。对于这个问题，最简单也是最容易想到的那就是穷举所有子序列的方法。利用三重循环，依次求出所有子序列的和然后取最大的那个。当然算法复杂度会达到O(n3)。显然这种方法不是最优的，下面给出一个算法复杂度为O(n)的线性算法实现，算法的来源于Programming Pearls一书。 在给出线性算法之前，先来看一个对穷举算法进行优化的算法，它的算法复杂度为O(n2)。其实这个算法只是对对穷举算法稍微做了一些修改：其实子序列的和我们并不需要每次都重新计算一遍。假设Sum(i,