Google笔试题整理(超全!)附部分答案.doc

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、 两个二进制数的异或结果% L. P2 C5 _ 2、 递归函数最终会结束，那么这个函数一定（不定项选择）：7 R8 c7 y( Q+ g/ a O1. 使用了局部变量; s2 S8 9 M; w& . 3 d2. 有一个分支不调用自身 & J2 D7 Z+ $ a4 R A4 c3. 使用了全局变量或者使用了一个或多个参数, O- l+ f3 i8 v* a$ m, S0 d, B, , * L3、以下函数的结果？2 * s; z/ O$ a$ z R+ 8 w4 F( A* h+ a& e ! ) M7 s& int cal(int x) 1 r9 P4 L& ?3 k( M8 P+ f$ q & y1 n m9 R4 _5 g, vif(x=0) . s$ z0 I P! T1 O W! return 0;* z: T8 7 d+ R9 pelse; |1 P; : y* o6 c( I1 Yreturn x+cal(x-1); L6 k- X, g4 h+ K- ? _/ N9 m+ p7 C/ M9 ?, j) M8 G H( $ I( a: R- d3 ; # W4、 以下程序的结果？ 8 f7 N$ z/ g& c+ - V2 X* 8 evoid foo(int*a, int* b) ( 4 . o# p, o7 c2 y9 M6 c0 S + ( t4 e5 W. Q+ 2 *a = *a+*b; & g4 _, o0 W; . h% p m3 f*b = *a-*b; $ _8 D b. e# M) m& R d G*a = *a-*b;3 s/ J: i9 L0 Y: y 6 6 d/ # D3 f g2 v8 c) v L4 L: ; ) _# wvoid main()( Y: * + d( D0 U9 R# & t& * & i1 a! a5 Kint a=1, b=2, c=3;7 o- U- h1 o5 i, Efoo(&a,&b); * : r8 I2 - f 0 D, A0 ofoo(&b,&c); 0 k4 I& l1 h5 wfoo(&c,&a);( k# s7 X- | e) i6 P* b O# printf(%d, %d, %d, a,b,c);9 0 f9 5 w, j M9 N Y. 8 g; n* w; u2 p o5、下面哪项不是链表优于数组的特点？ % S1 U) _1 g5 T, d$ R# W- K7 L/ p1. 方便删除 2. 方便插入 3. 长度可变 4. 存储空间小4 K$ J$ l+ r# a2 W+ F8 ) Q6、T(n) = 25T(n/5)+n2的时间复杂度？9 y r& x: h8 d$ A, ?8 I4 M7、n个顶点，m条边的全连通图，至少去掉几条边才能构成一棵树？ . q( |7 g/ i* G# 4 K- o8、正则表达式(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 4 M ?0 z9 X$ Y0 x0 m3. 进程倾向于占用I/O 4.使用基于最短剩余时间（shortest remaining time）的调度机制 E- a! F. C& i5. 减少页大小, Q- V7 V9 2 C8 s: s6 T2 / J! 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. d% u# c! M8 p: A12、长度为n的整数数组，找出其中任意(n-1)个乘积最大的那一组，只能用乘法，不可以用除法。要求对算法的时间复杂度和空间复杂度作出分析，不要求写程序。 google浙大招聘笔试题（转）一、单选0 g. i6 _, L: L% 8 1、80x86中，十进制数-3用16位二进制数表示为？0 d- Y. h L4 R* j; k0 2、假定符号-、*、$分别代表减法、乘法和指数运算，且 ( 2 1)三个运算符优先级顺序是：-最高，*其次，$最低；& 7 Y5 l- J5 e8 S1 : c# K4 S2)运算符运算时为左结合。请计算3-2*4$1*2$3的值：/ G$ B* I) G7 (A)4096，(B)-61，(C)64，(D)-80，(E)512 O* x6 + l8 ?; a6 N* w) L5 g/ U7 L) o* H3、下列伪代码中，参数是引用传递，结果是？) C, u+ p6 |4 ocalc(double p, double q, double r): N- X2 c) I L3 _+ Yq=q-1.0;r=r+p d/ J, h0 , u$ l V N6 nmain(): ) Q2 T$ K$ l- p4 Vdouble a = 2.5, b = 9.0;8 ) 2 - o h, j$ # Vcalc(b-a, a, a);/ print(a);+ A% G; Y% h2 x1 8 r7 / B1 i4 L/ 4 ) J(A)1.5 (B)2.5 (C)10.5 (D)8 (E)6.56 f, e! t# 6 P, i$ 4、求输出结果：( b m2 H2 C$ u E5 Hint 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个元素。1 H k$ c& C* b- ; I9 i9 否则，从终点出发，往回走n - k个元素。+ H1 j. # M1 E8 r U3 i这个算法的时间代价是？6 f, ) U q+ D* 2 y T(A)(nlogn) (B)(maxk, n - k) (C)(k + (n - k) + o+ v+ Z3 t) z(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)905 o/ Z4 O3 f& y( 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- , J; f$ h9 1 5 d/ f M- C6 9、为读取一块数据而准备磁盘驱动器的总时间包括% y( x+ p0 8 s& N. g& e(A)等待时间 (B)寻道时间 (C)传输时间 (D)等待时间加寻道时间 : s9 K4 H0 o, w* M(E)等待时间加寻道时间加传输时间1 J0 E9 , f0 C5 4 s2 n, 8 S! l: t0 i4 m二、算法 ?; O* U6 B9 P1、打印出一个二叉树的内容。7 k0 z2 ( k5 f! : A! h0 2、在一个字符串中找到第一个只出现一次的字符。如abaccdeff，输出b。2 y X- y8 d9 P: v8 7 x/ 3、给定一个长度为N的整数数组（元素有正有负），求所有元素之和 f% L/ G, m# s最大的一个子数组。分析算法时空复杂度。不必写代码。 附上算法题第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单选题：& : g i/ T g n2 p3 1，求两个二进制数的异或值，基本上学过一点计算机的东西的人都能对的题目。! ?; v6 f/ Y 9 P2，不记得了。也是不需要思考的题目。2 # P Z p! u: N3，大概是如下的函数：& ; n7 E7 B2 A n- N7 h) Yint someFunc(int x)* 7 D# _; F# m. b if (x = 0)8 S5 , T9 4 8 L2 Q2 G3 c! I return 0;( h5 5 A& v: x else l8 _% U) R4 L* l return x + someFunc(x - 1);2 t1 k- d# D / k7 Q1 E( M3 6 H- K c5 W9 W) J6 Y8 ?问这个计算的是什么。% U! m: L/ n, s6 z8 s$ B$ S8 N4，不记得了。不需要思考吧。 o7 3 q, e y+ k2 C. B# N5，不记得了。不需要思考吧。+ i# F8 y T# T+ R& x; L6，参见2，4，5。- a1 d! b; 4 w% 2 Y9 7，似乎需要思考一下。 u5 F c; W, l0 S8，问链表结构和数组相比的优势不包括哪项，$ Q2 U7 C/ v5 - z. i/ l包括：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剩下两个不记得了。 - , P4 q! 6 2 k9，如下函数：1 z8 T3 U# I- C( v. R$ x# N+ u% sT(x) = 1 (x ABprint “29 & c2 p. D* D+ lA-aprint “3 X/ h O y3 p3 k. h J cB-bCprint “4+ t6 ( e j2 X7 Y; q6 y! WB-dBprint “5 v# E6 R6 S1 _! hC-cprint “63 D& N2 c2 k9 k0 C# x6 # 0 m X% w8 |- P6. 有关哈希表正确的说法（不定项）3 L7 j N. b9 f. z9 Aa.哈希表的效率和哈希函数。相关3 h* O& P9 j- Z Nb.哈希表的解决冲突方法慢，回影响哈希表效率 r2 r( ) y0 * r7 U c.使用链表哈希可使内存紧凑2 h- Y7 l6 i) l% G$ s, m. f$ ?9 X, g0 $ V8 z6 m. Z: H7. 一种无饥饿调度方法是：9 L+ j8 O! V) ) x; Wa. 轮叫调度( 9 ! M& R6 1 c0 Yb.! s2 , x K: X/ : pc. 最短使用时间/ m! F: * 1 H4 X% td. 最新队列. A; e- m9 U5 n9 t( Z9 S9 k& e, Q # e! u1 n: C8. 下列排序方法最差情况时间复杂度为O(n2)的是：& z5 u) x/ z, Q0 5 O; ma. 插入# R9 V* x7 2 ib. 归并2 a Z! x8 o$ . c. 冒泡! Y* I. Q6 z f% S! D6 t( xd. 快速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结点，高度为0! j* L& L* W# ) I& g) / _7 E I1 o- h2 |+ |) v/ k9 X: x2. 将稀疏疏组中的非零元素提取出来，用链表表示- Z c3 & l4 s. I5 u k2 W# 3. 两个n维数组，已排序，为升序。设计算法求2n的数中. j u5 v& t- |4 D, e8 S, * k- g# h第n大的数。要求分析时间和空间复杂度。不用给出代码 = 这是部分google面试题目,希望后来者好运. 1 O2 H- S 4 D/ ( k+ a2 d1.求直方图的最大内接矩形,假设每个细条的宽度为1.这个题很hot,两个人来问.我没想出什么好的算法. # u) t) w4 V8 Z7 F; _. $ ) h _1