Google历年笔试题和面试题题目列表

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

(1)、设计一个函数voidgenerate（inta,intb,intN,int*Q）计算Q的前几项。
(2)、设计测试数据来验证函数程序在各种输入下的正确性。

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

3、如何随机选取1000个关键字？
    给定一个数据流，其中包含无穷尽的搜索关键字（比如，人们在谷歌搜索时不断输入的关键字）。如何才能从这个无穷尽的流中随机的选取1000个关键字？

4、判断一个自然数是否是某个数的平方？
    说明：当然不能使用开方运算。

5、给定能随机生成整数1到5的函数，写出能随机生成整数1到7的函数。

6、1024!末尾有多少个0？

7、有5个海盗，按照等级从5到1排列，最大的海盗有权提议他们如何分享100枚金币。但其他人要对此表决，如果多数反对，那他就会被杀死。他应该提出怎样的方案，既让自己拿到尽可能多的金币又不会被杀死？
（提示：有一个海盗能拿到98%的金币）

8、给定一个集合A=[0,1,3,8](该集合中的元素都是在0，9之间的数字，但未必全部包含)，指定任意一个正整数K，请用A中的元素组成一个大于K的最小正整数。比如，A=[1,0]K=21那么输出结构应该为100。

9、输入a1,a2,...,an,b1,b2,...,bn,在O(n)的时间,O(1)的空间将这个序列顺序改为a1,b1,a2,b2,a3,b3,...,an,bn，且不需要移动，通过交换完成，只需一个交换空间。

10、 有一台机器，上面有m个储存空间。然后有n个请求，第i个请求计算时需要占R[i]个空间，储存计算结果则需要占据O[i]个空间（据O[i]个空间（其 中O[i]<R[i]）。问怎么安排这n个请求的顺序，使得所有请求都能完成。你的算法也应该能够判断出无论如何都不能处理完的情况。比方 说，m=14，n=2，R[1]=10，O[1]=5，R[2]=8，O[2]=6。在这个例子中，我们可以先运行第一个任务，剩余9个单位的空间足够执 行第二个任务；但如果先走第二个任务，第一个任务执行时空间就不够了，因为10>14-6。

11、一个环形公路，上面有Ｎ个站点，A1,...,AN，其中Ai和Ai+1之间的距离为Di,AN和A1之间的距离为D0。高效的求第i和第j个站点之间的距离，空间复杂度不超过O(N)。它给出了部分代码如下：

defineN25doubleD[N]
....
voidPreprocess()
{
    //Writeyourcode1;
}
doubleDistance(inti,intj)
{
    //Writeyourcode2;
}

12、一个字符串，压缩其中的连续空格为1个后，对其中的每个字串逆序打印出来。比如"abcefghij"打印为"cbagfejih"。

13、将一个较大的钱，不超过1000000(10^6)的人民币，兑换成数量不限的100、50、10、5、2、1的组合，请问共有多少种组合呢？（其它选择题考的是有关：操作系统、树、概率题、最大生成树有关的题，另外听老梦说，谷歌不给人霸笔的机会。）。

14、谷歌在线笔试题：
输入两个整数A和B，输出所有A和B之间满足指定条件的数的个数。指定条件：假设C=8675在A跟B之间，若（8+6+7+5）/4>7，则计一个，否则不计。要求时间复杂度：log(A)+log(B)。

15、谷歌面试题：输入是两个整数数组，他们任意两个数的和又可以组成一个数组，求这个和中前k个数怎么做？

16、一个字符串，压缩其中的连续空格为1个后，对其中的每个字串逆序打印出来。比如"abcefghij"打印为"cbagfejih"。

17、将一个较大的钱，不超过1000000(10^6)的人民币，兑换成数量不限的100、50、10、5、2、1的组合，请问共有多少种组合呢？（其它选择题考的是有关：操作系统、树、概率题、最大生成树有关的题，另外听老梦说，谷歌不给人霸笔的机会。）。

18、输入两个整数A和B，输出所有A和B之间满足指定条件的数的个数。指定条件：假设C=8675在A跟B之间，若（8+6+7+5）/4>7，则计一个，否则不计。要求时间复杂度：log(A)+log(B)。

19、有几百亿的整数，分布的存储到几百台通过网络连接的计算机上，你能否开发出一个算法和系统，找出这几百亿数据的中值？就是在一组排序好的数据中居于中间的数。显然，一台机器是装不下所有的数据。也尽量少用网络带宽。

20、给定三个整数a,b,c,实现函数intmedian(inta,intb,intc),返回三个数的中位数。不可以使用sort，要求整数操作（比较，位运行，加减乘除等）。次数尽量少，并分析说明程序最坏和平均情况下使用的操作次数。

21、给定一个key（只含有ASCII编码的小写英文字母），例如kof，然后对input的string（只含有ASCII编码的小写英文字母），利用这个key排序，顺序是：先按照key中的字符顺序，然后对key中不包含的字符，按a-z顺序。

22、 一个平行于坐标轴的n*n的网络，左下角（0,0）右上角（n,n），n为非负整数，有n个平行于坐标轴的矩形，每个矩形用左下角（X1，Y1）右上角 （X2，Y2）来表示，X1，Y1，X2，Y2都是非负整数，现在有非常多个query,每个query会询问一个网格（X,Y）（X+1，Y+1）一共 被几个矩形覆盖。现在要求设计一个算法，使得处理每个query的时间复杂度尽可能低，在这个前提下，预处理的时间复杂度尽可能低。

23、写一个函数，输出前N个素数，函数原型：voidprint_prime(intN);不需要考虑整数的溢出问题，也不需要使用大数处理算法。

24、长度为N的数组乱序存放着0带N-1.现在只能进行0与其他数的swap操作，请设计并实现排序，必须通过交换实现排序。

25、给定一个源串和目标串，能够对源串进行如下操作：
1.在给定位置上插入一个字符
2.替换任意字符
3.删除任意字符
写一个程序，返回最小操作数，使得对源串进行这些操作后等于目标串，源串和目标串的长度都小于2000。

26、找几百亿数据中值
有几百亿的整数，分布的存储到几百台通过网络连接的计算机上，你能否开发出一个算法和系统，找出这几百亿数据的中值？就是在一组排序好的数据中居于中间的数。显然，一台机器是装不下所有的数据，也尽量少用网络带宽。

PS：本文会不定期更新，更新更多题，欢迎大家随时在下面讨论以上各题的答案。