谷歌笔试真题一：

选择题：

1.关于整数，下列说法正确的是：

A.忘了

B. 32位的机器上，8位加法比 32位加法更快

C.整数加法最好不要溢出，否则会浪费内存

D.一般来讲，整数除法比乘法更加费时间

2.在 OSI标准钟，下列协议哪个位于最底层：

A. HTTP

B. FTP

C. IP

D. TCP

3.给一段代码，问正确的是：

大概是两个函数，其中一个里面调用了 malloc但是没有释放，另一个申请了局部

数组 a[20M]

A.动态申请效率会比较高

B.声明局部数组的那个函数可能有内存泄露

C.声明局部数组的那个函数可能会导致运行时栈溢出

4. 28.5625的 4进制表示

A.121.XX

B.XXXX

C121.XX

D130.21

5.关于垃圾回收机制，下列说法错误的是

A.在这个机制下，程序员不必显式回收内存

B.现在的垃圾回收机制能够处理循环引用

C.垃圾回收机制能够让程序员更方便地写代码

D.有垃圾回收机制的语言肯定不会导致内存泄露

6.下列加密方法，哪个不能用于加密文本：

A. MD5

B. RSA

C. RC4

D. DES

7.有 3个 a，5个 b，2个 c，现在对他们做全排列，其中包含至少一个"abc"串的

排列数是多少?

A. 8!

B.好大一个数

C. 840

D. 780

E. 69

8.给定一个无向带权连通图，求最大生成树(权重和最大的生成树)邻接矩阵为{xxxxx}{xxxxx}{xxxxx}{xxxxx}{xxxxx}

A 11 b 12 C 13 D 14 E 15

9.一个节点数不小于 3的二叉树，至少删除几个点能够让它不连通?

A0 B1 C2 D3 E4

10.关于操作系统的说法，哪个是错误的?

A. XX(好像是微内核)和 XX(忘记是啥了)在现在仍然是比较新的概念

B.系统调用是用户态和内核态连接的接口

C.操作系统为用户程序提供运行平台

D.文件系统和 XX必须实现在内核态

参考答案：D C C D D A D D B D

三道大题：

1.一个环，N个点，任意相邻两点有一个距离。要求写一个算法，输入为点 i和点j，输出是他们之间的最短路径

2.一个字符串，去除重复的空格，并且把子段 reverse

3. X<10^6，如何用任意的 100、50、20、10、5、2、1来加出 X，求所有方法

谷歌笔试真题二：

以下是2011年google中国笔试题，共有10道选择题，3道大题。大家也来练一练，看看自己能做对多少题。

选择题

1、考的是正则表达式，什么字符串匹配，没看过。2、在 Intel 8086中，加减乘除那个

2、整数运算最耗时。

3、看程序，写算法，考察的是 unsigned short类型的范围。

4、19本书，编号从 1-19。从中抽五本，任意相邻两本不是相邻编号的情况有多少种。

5、N为满二叉树的叶子节点数，求总结点数。

6、排序算法：在最坏情况下时间复杂度为 O(nlogn)的是归并，快速，冒泡，插入中的哪个。

7、房价 200万，每年以 10%的速度递增，工程师为 40万年薪，问什么时候买得起房。

8、有两个有序数组长度为 M和 N，将两个数组合并，最好情况下比较几次。M次，N次，Min(M,N),Max(M,N)。

9、TLB和 Cache的区别，这个题不会，没听说过 TLB。

10、数据库的试题。

编程题

1、写函数 double value(double x,double A[],double N) double A[N]存储多项式f(x)=a0+a1x+a2x^2+……的系数。N为已知。

2、有 2^K队伍比赛，按照 order给出一个比赛顺序的排列，order表示编号为 i的

队的位臵，记不太清了，有 winner[j]表示 i,j两队比赛结果，只有胜负没有平局，winner[j]=winner[j]求 result[]里面存放各队比赛排名。

3、给一些字母连接规则比如 ABC->D表示前面是 ABC后面可以接 D，求是否可以无限接下去，或者求最大长度。

谷歌笔试真题三：

1、Solve this cryptic equation, realizing of course that values for M and E could

be,interchanged No leading zeros are allowed.6 WWWDOT - GOOGLE = DOTCOM.

2、Write a haiku describing possible methods' for predicting search traffic seasonality.

3、

1

11

21

1211

111221

What is the next line?

4、You are in a maze of twisty little passages, all alike. There is a dusty laptop here witha'weak wireless connection. There are dull, lifeless gnomes strolling about. What dost thoudo?

A) Wander aimlessly, bumping into obstacles until you are eaten by a grue.

B) Use the laptop as a digging device to tunnel to the next level.

C) Play MPoRPG until the battery dies along with your hopes.

D) Use the computer to map the nodes of the maze and discover an exit path.

E) Email your resume to Google, tell the lead gnome you quit and find yourself in whole different world.

5、What’s broken with Unix? How would you fix it?

6、On your first day at Google, you discover that your cubicle mate wrote the textbook.You used as a primary resource in your first year of graduate school. Do you:

A) Fawn obsequiously and ask if you can have an autograph.

B) Sit perfectly still and use only soft keystrokes to avoid disturbing her concentration.

C) Leave her daily offerings of granola and English toffee from the food bins.

D) Quote your favorite formula from the textbook and explain how it’s now your mantra.

E) Show her how example 17b could have been solved with 34 fewer lines of code.

7、Which of the following expresses Google over-arching philosophy?.

A) "I’m feeling lucky",

B) "Don’t be evi”

C) "Oh, I already fixed that"

D) "You should never be more than 50 feet from food"

E) All of the above

8、How many different ways can you color an icosahedron with one of three colors on each face? What colors would you choose?

9、This space left intentionally blank. Please fill it with something that improves uponemptiness.

10、On an infinite, two-dimensional, rectangular lattice of 1-ohm resistors, what is the resistance between two nodes that are a knight’s move away?

11、It’s 2 PM on a sunny Sunday afternoon in the Bay Area. You’re minutes from the Pacific Ocean, redwood forest hiking trails and world class cultural attractions. What do you do?

12、In your opinion, what is the most beautiful math equation ever derived?

13、 Which of the following is NOT an actual interest group formed by Google employees?

A)Women’s basketball

B)Buffy fans

C)Cricketeers

D)Nobel winners

E)Wine club

14、What will be the next great improvement in search technology?

15、What is the optimal size of a project team, above which additional members do not contribute productivity equivalent to the percentage increase in the staff size?

A) 1

B) 3

C) 5

D) 11

E) 24

16、Given a ABC, how would you use only a compass and straight edge to find a point such that s ABP, ACP and BCP have equal perimeters? (Assume that ABC is constructed so that a solution does exist.)

17、Consider a function which, for a given whole number n, returns the number of ones

required when writing out all numbers between 0 and n. For example, f(13)=6. Notice that

f(1)=1.What is the next largest n such that f(n)=n?!

18、What’s the coolest hack you’ve ever written?

19、It is known in refined company, that choosing K things out of N can be done in ways as many as choosing N minus K from N: I pick K, you the remaining. Find though a cooler bijection,where you show a knack uncanny, of your choices contain all K of mine. Oh, for pedantry: let K be no more than half N.

20、What number comes next in the sequence:10, 9, 60, 90, 70, 66,?

A)96

B)10000000000000000000000000000000000000000000000000000000000000000000

000000000000000000000000000000000

C)Either of the above

D)None of the above

21、In 29 words or fewer, describe what you would strive to accomplish if you worked at Google Labs.

谷歌笔试真题四：

1.1关于 IP协议哪个正确?

A、IP是 TCP上层协议

B、IP协议是应用层协议

C、由于两个属于同一层协议，他们之间可以直接通信

D、IP协议不提供可靠的通信

1.2关于内存正确的是()。

A、内存的存取速度不能低于 cpu速度，否则会造成数据丢失。

B、程序只有在数据和代码等被调入内存后才能运行。

C、采用虚拟内存技术后程序可以在硬盘上直接运行。

D、某计算机的内存容量为 16MB，那么他的地址总线为 24位。

1.3单链表中结点的结构为(data，link)，若想删除结点 p(不是头节点或者尾结点)的直接后继，则应执行下列哪个操作?()

A、p=p->link; p->link=p->link->link;

B、p->link->link=p->link;

C、p=p->link->link;

D、p->link=p->link->link;

1.4已知 x>=y and y>=z为真，那么 x>z or y=z值为()。

A、真

B、假

C、无法确定

D、x y z同为正数时为真

1.5某请求被随即分配到四台机器进行处理，分配到每台机器的概率 A15%，B20%，C30%，D35%,处理请求的失败概率分别为 5%，4%，3%，2%，现在请求失败，问由 C造成的概率最接近()

A、26%

B、28%

C、30%

D、32%

1.6假设我们用 d=(a1,a2,….a5)表示无向无环图 G的 5个顶点的度数，下面给出的哪组值是可能的?()

A、{3,4,4,3,1}

B、{4,2,2,1,1}

C、{3,3,3,2,2}

D、{3,4,3,2,1}

1.7设栈 S和队列 Q的初始状态为空，元素 e1，e2，e3，e4，e5，e6一次压入栈 S,一个元素出栈后即进入队列 Q，若出队列的顺序为 e2,e4,e3,e6,e5,e1则栈 S的容量要求最小值为?()

A、2

B、3

C、4

D、5

1.8在堆排序算法中我们用一个数组 A来模拟二叉树 T，如果该 A[0]存放的是 T的根节点，那么 A[K](K>0)的父亲节点是?()

A、(K-1)/2

B、K/2

C、(K+1)/2

D、都不对

1.9现有如下任务需要安排在若干机器上并行完成，每个任务都有开始时间和结束时间(开始和结束时间都包括在任务执行时间内)的要求。

则最少需要使用的机器数目为?()

A、1

B、2

C、3

D、4

1.10在设计一个操作系统时，哪项不是必须考虑的?()

A、设备管理模块

B、文件系统模块

C、用户管理模块

D、进程管理模块

2.1正整数序列 Q中的每个元素都至少能被正整数 a和 b中的一个整除，现给定a和 b，需要计算出 Q中的前几项，例如，当 a=3，b=5，N=6时，序列为 3，5，6，9，10，12。

(1)设计一个函数 void generate(int a,int b,int N ,int * Q)计算 Q的前几项。

(2)设计测试数据来验证函数程序在各种输入下的正确性。

2.2有一个由大小写组成的字符串，现在需要对他进行修改，将其中的所有小写字母排在答谢字母的前面(大写或小写字母之间不要求保持原来次序)，如有可能尽量选择时间和空间效率高的算法 c语言函数原型 void proc(char *str)也可以采用你自己熟悉的语言。

2.3已知一颗无向无环连通图 T的所有顶点和边的信息，现需要将其转换为一棵树，要求树的深度最小，请设计一个算法找到所有满足要求的树的根结点，并分析时空复杂度(描述算法即可，无需代码)。

谷歌笔试经验一：

昨天刚参加 Google 宣讲和笔试，考得很基础，共享一下笔试题目，奇文共赏之。共有10道选择题，3 道大题。

1.考的是正则表达式，什么字符串匹配，没看过。

2.在 Intel 8086 中，加减乘除那个整数运算最耗时。很基础哇。

3.看程序，写算法，考察的是 unsigned short 类型的范围。程序有点长，变量名还相似，想不起来了，

4.19 本书，编号从 1-19。从中抽五本，任意相邻两本不是相邻编号的情况有多少种。这个题谁会啊，大家发帖探讨一下。

5.N 为满二叉树的叶子节点数，求总结点数。确实很基础。

6.排序算法：在最坏情况下时间复杂度为 O(nlogn)的是归并，快速，冒泡，插入中的哪个。

7.房价 200 万，每年以 10%的速度递增，工程师为 40 万年薪，问什么时候买得起房。

8.有两个有序数组长度为 M 和 N，将两个数组合并，最好情况下比较几次。M 次，N 次，Min(M,N),Max(M,N)

9.TLB 和 Cache 的区别，这个题不会，没听说过 TLB。上网查了查，TLB：Translation lookaside buffer,即旁路转换缓冲，或称为页表缓冲;里面存放的是一些页表文件(虚拟地址到物理地址的转换表)。大家还是自己上网了解吧。

10.数据库的试题，偶记不清了，不过不难。

大题

一、写函数 double value(double x,double A[],double N) double A[N]存储多项式 f(x)=a0+a1x+a2x^2+……的系数。N为已知。

二、有 2^K 队伍比赛，按照 order 给出一个比赛顺序的排列，order 表示编号为 i 的队的位置，呀呀，记不太清了，有 winner[j]表示 i,j 两队比赛结果，只有胜负没有平局，winner[j]=winner[j]求 result[]里面存放各队比赛排名。貌似用递归，只是小弟拙见。

三、KOF 里连招，简化为 ABCD……Z 求最长连招……记不清了，见谅，XDJM补充。

谷歌笔试经验二：

昨天晚上去蹭了一下Google的招聘笔试。其实是去打酱油的，主要是为了感受一下Google的出题风格和考试氛围，可以对将来找工作提供些参考。

回来之后本来想回忆一下题目的，结果发现braveheart89大大已经贴出了所有的题而且连选项都一字不差，记忆力真心佩服……以下就根据他写的题目稍微修正一下[1]，然后随便说说好了。(说的也不一定对，欢迎更正。)

考试是第一页需要填写个人信息，包括实习经历、获奖情况、工作地点意向(国内、国外还是两者皆可之类，反正对我无用啦-.-)然后就是一个半小时的答题，全部手写。

1、单项选择题

1.1 如果把传输速率定义为单位时间内传送的信息量(以字节计算)多少。关于一下几种典型的数据传输速率：

1.使用USB2.0闪存盘，往USB闪存盘上拷贝文件的数据传输速率

2.使用100M以太网，在局域网内拷贝大文件时网络上的数据传输速率

3.使用一辆卡车拉1000块单块1TB装满数据的硬盘，以100km/h的速度从上海到天津(100km)一趟所等价的数据传输带宽

4.使用电脑播放MP3，电脑的PCI总线到声卡的数据传输速率

在通常情况下，关于这几个传输速率的排序正确的是：

A.4<1<2<3 B.1<4<2<3 C.4<1<3<2 D.1<4<3<2

1.2 对以下程序，正确的输出结果是

#define SUB(x,y) x-y

#define ACCESS_BEFORE(element,offset,value) *SUB(&element, offset) =value

int main()

{

int array[10]= {1,2,3,4,5,6,7,8,9,10};

int i;

ACCESS_BEFORE(array[5], 4, 6);

printf("array: ");

for (i=0; i<10; ++i){

printf("%d", array[i]);

}

printf("\n");

return (0);

}A.array: 1 6 3 4 5 6 7 8 9 10

B.array: 6 2 3 4 5 6 7 8 9 10

C.程序可以正确编译连接，但是运行时会崩溃

D.程序语法错误，编译不成功

1.3 在区间[-2, 2]里任取两个实数，它们的和>1的概率是：

A.3/8 B.3/16 C.9/32 D.9/64

1.4 小组赛，每个小组有5支队伍，互相之间打单循环赛，胜一场3分，平一场1分，输一场不得分，小组前三名出线。平分抽签。问一个队最少拿几分就有理论上的出线希望：

A.1 B.2 C.3 D.4

1.5 用二进制来编码字符串“abcdabaa”，需要能够根据编码，解码回原来的字符串，最少需要多长的二进制字符串?

A.12 B.14 C.18 D.24

1.6 10个相同的糖果，分给三个人，每个人至少要得一个。有多少种不同分法

A.33 B.34 C.35 D.36

1.7 下列程序段，循环体执行次数是：

y=2

while(y<=8)

y=y+y;

A.2 B.16 C.4 D.3

1.8 下面哪种机制可以用来进行进程间通信?

A.Socket B.PIPE C.SHARED MEMORY D.以上皆可

1.9 下列关于编程优化的说法正确的是：

A.使用编译器的优化选项(如-O3)后程序性能一定会获得提高

B.循环展开得越多越彻底，程序的性能越好

C.寄存器分配能够解决程序中的数据依赖问题

D.现代主流C/C++编译器可以对简单的小函数进行自动Iinline

1.10 一下程序是用来计算两个非负数之间的最大公约数：

long long gcd(long long x, long long y) {

if( y==0) return 0;

else return gcd (y, x%y);

}我们假设x,y中最大的那个数的长度为n，基本运算时间复杂度为O(1)，那么该程序的时间复杂度为：

A.O(1) B.O(logn) C.O(n) D.O(n^2)

2、程序设计与算法(2.1,2.2为编程题，2.3为算法设计题，只需设计思路和关键步骤伪代码)

2.1 写函数，输出前N个素数。不需要考虑整数溢出问题，也不需要使用大数处理算法。

2.2 长度为n的数组乱序存放着0至n-1. 现在只能进行0与其他数的swap，请设计并实现排序。

2.3 给定一个原串和目标串，能对源串进行如下操作：

1.在给定位置插入一个字符

2.替换任意字符

3.删除任意字符

要求写一个程序，返回最少的操作数，使得源串进行这些操作后等于目标串。源串和目标串长度都小于2000。

——

以下是我根据各种来源总结的参考答案：

1.1 A

USB 2.0的理论传输极限是480Mbps[2]，但是按照这个速率就没有选项可选了-.-，所以猜测应该认为是普通U盘写数据的6MB/s，即48Mbps;

100M以太网的速率就是100Mbps;

卡车拉硬盘，1000x1000x8/3600=2222Mbps，这个应该是最快的;

MP3在256kbps码率下也平均只有1分钟2MB，所以不会超过0.3Mbps，所以一定是最慢的。

1.2 D

这道题大家走出考场后争议非常大。