Google笔试题整理.doc

上海毕业生找IT职位就上 才智尚招聘网Google笔试题整理（超全！）附部分答案，希望能帮到有需要的人！写出这样一个函数 ,输入一个 n, 输出从1到这个数字之间的出现的1的个数,比如f(13)等于6; f(9)等于1; 网上有很多这道题的解法，大多采用穷举法。这把这个算法题变成了程序设计，这道题，我认为是总结一个递推公式，然后用递推法实现，比较好。后来在网上考证了一下，这道题本来也是让总结一个数学函数即可，无需编程。既然写了，就贴出来，发表一下自己的解法。这道题还有另一半,当f(n)n是，最小的n是多少？本人还没有好的方法，所以就不贴了。 下面的程序是上半部java实现的。 /* 可以推出下列递推公式: * f(n)=(a1?s:n-s*a+1)+a*f(s-1)+f(n-s*a)当n9时; * L是n的位数 * a是n的第一位数字 * s是10的L1次方 * n-s*a求的是a后面的数. * 公式说明： * 求 0-n 由多少个数字1，分三部分，一是所有数中第一位有多少个1，对应(a1?s:n-s*a+1) * 当a大于1是,应该有a的L1次， a小于1是有n-s*a+1。 * 如n是223 所有数中第一位有1是100;n是123所有数中第一位是1的有24 * 二是 对应a*f(s-1） 如n是223应该有2*f(99)个1 * 三是 对应f(n-s*a) 如n是223应该有f(23)个1。 */ long f(long n) if (n0?1:0; int L=(int)(Math.log10(n)+1);/求n的位数l long s=(long)Math.pow(10, L-1);/求10的l1次方，方便求后面n的第一位数字，及其后面的数。 long a=(long)(n/s);/求n的第一位数字 return (a1?s:n-s*a+1)+a*f(s-1)+f(n-s*a); google笔试题：A+B=C在一个集合S中寻找最大的C使A+B=C且A,B,C均在集合当中解答(原创)1，将集合S中的数排序X1=X20;i-)for(j=0,k=i-1;kj;)if(Xj+XkXi) k-; cotinue;if(Xj+Xk 2)T(0) = T(1) = 1, T(2) = 2.*/int tribonaci(int n)if (n uvSvu|w所识别的语言是：（）a、uvw*vu 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=x/2;elsex=3*x 1;countcntend1;当n=11时，输出：（）a、12 b、13 c、14 d、155、写一段程序判定一个有向图G中节点w是否从节点v可达。（假如G中存在一条从v至w的路径就说节点w是从v可达的）。以下算法是用C 写成的，在bool Reachable函数中，你可以写出自己的算法。class Graphpublic:int NumberOfNodes();/返回节点的总数bool HasEdge(int u,int v);/u,v是节点个数，从零开始依次递增，当有一条从u到v的边时，返回true；bool Reachable(Graph&G, int v, int w)/请写入你的算法6、给定一棵所有边的长度均为整数的树，现要求延长其中某些边，使得从根到任意节点的路径长度相等。问满足要求的树的边长度之和最小是多少?请写出你的算法，并分析时间复杂度。=Google笔试题1、 两个二进制数的异或结果2、 递归函数最终会结束，那么这个函数一定（不定项选择）：1. 使用了局部变量2. 有一个分支不调用自身 3. 使用了全局变量或者使用了一个或多个参数, O- l+ f3 i8 v* a$ m, S0 d, B, , * L3、以下函数的结果？2 * s; z/ O$ a$ z R+ int cal(int x) 1 r9 P4 L& ?3 k( M8 P+ f$ q if(x=0) . s$ z0 I P! T1 O W! return 0;* z: T8 7 d+ R9 pelsereturn x+cal(x-1);8 G H( $ I( a: R- d3 ; # W4、 以下程序的结果？ void foo(int*a, int* b) ( 4 . o# p, o7 c2 y9 M6 c0 S *a = *a+*b; *b = *a-*b; *a = *a-*b;3 s/ J: i9 L0 Y: y 6 6 d/ # D3 f g2 v8 c) vvoid main() & t& * & i1 a! a5 Kint a=1, b=2, c=3;7 o- U- h1 o5 i, Efoo(&a,&b); foo(&b,&c); foo(&c,&a);printf(%d, %d, %d, a,b,c);5、下面哪项不是链表优于数组的特点？ 1. 方便删除 2. 方便插入 3. 长度可变 4. 存储空间小6、T(n) = 25T(n/5)+n2的时间复杂度？7、n个顶点，m条边的全连通图，至少去掉几条边才能构成一棵树？ 8、正则表达式(01|10|1001|0110)*与下列哪个表达式一样？4 V3 A3 w6 |- H. q; G% q3 E a5 D, j 5 D/ K9、如何减少换页错误？3 C- I: g/ r6 1. 进程倾向于占用CPU 2. 访问局部性（locality of reference）满足进程要求 )3. 进程倾向于占用I/O 4.使用基于最短剩余时间（shortest remaining time）的调度机制 5. 减少页大小! B$ a5 ! 9 V. C9 y10、实现两个N*N矩阵的乘法，矩阵由一维数组表示8 7 M$ + v/ a3 6 # Y7 q/ D, $ I C1 z11、找到单向链表中间那个元素，如果有两个则取前面一个2 t1 v4 U, h0 b3 D. d12、长度为n的整数数组，找出其中任意(n-1)个乘积最大的那一组，只能用乘法，不可以用除法。要求对算法的时间复杂度和空间复杂度作出分析，不要求写程序。 google浙大招聘笔试题（转）一、单选1、80x86中，十进制数-3用16位二进制数表示为？ 2、假定符号-、*、$分别代表减法、乘法和指数运算，且 ( 2 1)三个运算符优先级顺序是：-最高，*其次，$最低；& 7 Y5 l- J5 e8 S1 : c# K4 S2)运算符运算时为左结合。请计算3-2*4$1*2$3的值：(A)4096，(B)-61，(C)64，(D)-80，(E)5123、下列伪代码中，参数是引用传递，结果是？) C, u+ p6 |4 ocalc(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);8 r7 / B1 i4 L/ 4 ) J(A)1.5 (B)2.5 (C)10.5 (D)8 (E)6.5 4、求输出结果：int foo(int x, int y) I2 - l l! j( B5 i1 R7 aif(x =0 | y = 1且k = n）：/ d1 L; d0 k n# ?- F( t如果k = n - k，从链表开始往前进k-1个元素。否则，从终点出发，往回走n - k个元素。这个算法的时间代价是？6 f, ) U q+ D* 2 y T(A)(nlogn) (B)(maxk, n - k) (C)(k + (n - k) (D)(maxk, k - n) (E)(mink, n - k)4 v+ 3 L% p$ p0 z& t Q% v0 T4 |4 X. 2 r# z2 V/ j0 b7、有一个由10个顶点组成的图，每个顶点有6个度，那么这个图有几条边？ Z3 2 f& K0 1 i8 m(A)60 (B)30 (C)20 (D)80 (E)90( O p& L. D: _2 O8、正则表达式L = x*(x|yx+)。下列哪个字符串不符号L3 Z3 ?1 k7 y N$ a N8 F7 P( O(A)x (B)xyxyx (C)xyx (D)yxx (E)yx8 u, p; W, a U9 f- 9、为读取一块数据而准备磁盘驱动器的总时间包括% y( x+ p0 8 s& N. g& e(A)等待时间 (B)寻道时间 (C)传输时间 (D)等待时间加寻道时间 (E)等待时间加寻道时间加传输时间2 n, 8 S! l: t0 i4 m二、算法 ?; O* U6 B9 P1、打印出一个二叉树的内容。2、在一个字符串中找到第一个只出现一次的字符。如abaccdeff，输出b。2 y X- y8 d9 P: v8 7 x/ 3、给定一个长度为N的整数数组（元素有正有负），求所有元素之和最大的一个子数组。分析算法时空复杂度。不必写代码。 附上算法题第3题的动态规划做法的参考答案:最大子序列问题：给定一整数序列A1， A2，. An （可能有负数），求A1An的一个子序列AiAj，使得Ai到Aj的和最大例如： 整数序列-2, 11, -4, 13, -5, 2, -5, -3, 12, -9的最大子序列的和为20。 对于这个问题，最简单也是最容易想到的那就是穷举所有子序列的方法。利用三重循环，依次求出所有子序列的和然后取最大的那个。当然算法复杂度会达到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;jmax)max=v; return max;那怎样才能达到线性复杂度呢？这里运用动态规划的思想。先看一下源代码实现：int max_sub2(int a, int size)int i,max=0,temp_sum=0;for(i=0;imax)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。这样一趟扫描结果也就出来了。 google面试试题汇总（转）笔试题目：9道单选+3道问答 W, B2 ? n2 A8 m2 P+ T) t时间：100分钟/ A) Z; e4 ?* l( d9 Y, v K我做的是B卷。3 N1 B; C6 j& T# L/ N) r单选题：1，求两个二进制数的异或值，基本上学过一点计算机的东西的人都能对的题目。2，不记得了。也是不需要思考的题目。3，大概是如下的函数：& ; n7 E7 B2 A n- N7 h) Yint someFunc(int x)* 7 D# _; F# m. b if (x = 0) return 0;( h5 5 A& v: x else l8 _% U) R4 L* l return x + someFunc(x - 1);6 H- K c5 W9 W) J6 Y8 ?问这个计算的是什么。% U! m: L/ n, s6 z8 s$ B$ S8 N4，不记得了。不需要思考吧。5，不记得了。不需要思考吧。6，参见2，4，5。- a1 d! b; 4 w% 2 Y9 7，似乎需要思考一下。 u5 F c; W, l0 S8，问链表结构和数组相比的优势不包括哪项，包括：1 S8 . C Z# C G c插入的时间/ q: x. R2 f6 w |: x2 H9 j8 D4 y$ R删除的时间1 S/ S2 b- T% U! I+ J7 I存储空间2 V8 L& ; s8 y6 O% T2 y剩下两个不记得了。9，如下函数：1 z8 T3 U# I- C( v. R$ x# N+ u% sT(x) = 1 (x ABprint “2A-aprint “3 X/ h O y3 p3 k. h J cB-bCprint “4+ t6 ( e j2 X7 Y; q6 y! WB-dBprint “5C-cprint “66. 有关哈希表正确的说法（不定项）3 L7 j N. b9 f. z9 Aa.哈希表的效率和哈希函数。相关3 h* O& P9 j- Z Nb.哈希表的解决冲突方法慢，回影响哈希表效率 r2 r( ) y0 * r7 U c.使用链表哈希可使内存紧凑9 X, g0 $ V8 z6 m. Z: H7. 一种无饥饿调度方法是：a. 轮叫调度b.c. 最短使用时间d. 最新队列. A; e- m9 U5 n9 t( Z9 S9 k8. 下列排序方法最差情况时间复杂度为O(n2)的是：a. 插入# R9 V* x7 2 ib. 归并c. 冒泡d. 快速3 E: C& v j8 C! _; P c8 |+ N) q: . E: s编程题：1 - k* U1 L. , G9 K9 X N# w% b* w; m, K j: n8 n1. 求一个二叉树的高度，如果只有root结点，高度为01 o- h2 |+ |) v/ k9 X: x2. 将稀疏疏组中的非零元素提取出来，用链表表示3. 两个n维数组，已排序，为升序。设计算法求2n的数中第n大的数。要求分析时间和空间复杂度。不用给出代码 = google招聘面试题回馈zz这是部分google面试题目,希望后来者好运. 1.求直方图的最大内接矩形,假设每个细条的宽度为1.这个题很hot,两个人来问.我没想出什么好的算法. # u) t) w4 V8 Z7 F; _. 2.NxN行列有序的矩阵查找一个数.以前有人遇到过.O(N)的时间复杂度 E3 e4 m w2 C4 J4 )