Google 历年笔试面试汇总第1-30题


题目整理人:Alina,点评人:cpcs、July。欢迎大家随时在本帖下讨论各题的答案。

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. 设计测试数据来验证函数程序在各种输入下的正确性。
点评by曹博:跟丑数差不多
vector<int> C;
int x = a;
int y = b;
while (C.size() < N) {
    if (x < y) {
        C.push_back(x);
        x += a;
    }
    else if (y < x) {
        C.push_back(y);
        y += b;
    }
    else {
        C.push_back(x);
        x += a;
        y += b;
    }
}
return C;

2、有一个由大小写组成的字符串,现在需要对他进行修改,将其中的所有小写字母排在大写字母的前面(大写或小写字母之间不要求保持原来次序),如有可能尽量选择时间和空间效率高的算法。
c语言函数原型void proc(char *str)
当然,也可以采用你自己熟悉的语言。
点评:奇偶排序问题:https://github.com/julycoding/ ... 06.md

3、如何随机选取1000个关键字?
给定一个数据流,其中包含无穷尽的搜索关键字(比如,人们在谷歌搜索时不断输入的关键字)。如何才能从这个无穷尽的流中随机的选取1000个关键字?
点评:水库采样 见此概率短视频的例5:http://www.julyedu.com/video/play/id/35

4、判断一个自然数是否是某个数的平方?
说明:当然不能使用开方运算。
点评:分解质因数 看指数的次数是否全是偶数 或者 二分求平方根, 或者牛顿迭代求平方根。

5、给定能随机生成整数1到5的函数,写出能随机生成整数1到7的函数。
点评:参考此概率短视频 http://www.julyedu.com/video/play/id/35

6、1024! 末尾有多少个0?
点评:[1024 / 5] + [1024 / 25] + [1024 / 125] + [1024 / 625] = 204 + 40 + 8 + 1 = 253

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

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,
且不需要移动,通过交换完成,只需一个交换空间。
点评:完美洗牌问题:https://github.com/julycoding/ ... 09.md

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。
点评by曹博:http://www.51nod.com/onlineJud ... D1099

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

define N 25

double D[N] 
....
void Preprocess()
{
     //Write your code1;
}
double Distance(int i, int j)
{
      //Write your code2;
}

点评:前缀和相减 估计要折腾一下,O(n)空间。

12、一个字符串,压缩其中的连续空格为1个后,对其中的每个字串逆序打印出来。比如"abc   efg  hij"打印为"cba gfe jih"。
点评:找空格 直接翻。

13、将一个较大的钱,不超过1000000(10^6)的人民币,兑换成数量不限的100、50、10、5、2、1的组合,请问共有多少种组合呢?
(其它选择题考的是有关:操作系统、树、概率题、最大生成树有关的题)
点评:naive dp

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

15、谷歌面试题:输入是两个整数数组,他们任意两个数的和又可以组成一个数组,求这个和中前k个数怎么做?
点评:超级复杂论文O(n)可以搞 只会用堆乱搞。

16、待更新。

17、待更新。

18、待更新。

19、给定三个整数a,b,c,实现函数int median(int a, int b, int c),返回三个数的中位数。不可以使用sort,要求整数操作(比较,位运行,加减乘除等)。次数尽量少,并分析说明程序最坏和平均情况下使用的操作次数。
点评:减法判断符号。

20、给定一个key(只含有ASCII编码的小写英文字母),例如kof,然后对input的string(只含有ASCII编码的小写英文字母),利用这个key排序,顺序是:先按照key中的字符顺序,然后对key中不包含的字符,按a-z顺序。
点评:自己写排序cmp函数。

21、一个平行于坐标轴的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的时间复杂度尽可能低,在这个前提下,预处理的时间复杂度尽可能低。
点评:离散化 + 2维线段树。

22、写一个函数,输出前N个素数,函数原型:void print_prime(int N); 不需要考虑整数的溢出问题,也不需要使用大数处理算法。

23、长度为N的数组乱序存放着0带N-1.现在只能进行0与其他数的swap操作,请设计并实现排序,必须通过交换实现排序。
点评by曹博:做过 http://www.patest.cn/contests/pat-a-practise/1067

24、给定一个源串和目标串,能够对源串进行如下操作:
   1.在给定位置上插入一个字符
   2.替换任意字符
   3.删除任意字符
写一个程序,返回最小操作数,使得对源串进行这些操作后等于目标串,源串和目标串的长度都小于2000。
点评:字符串编辑距离问题:https://github.com/julycoding/ ... 02.md

25、灯泡状态
You have a system with N light bulbs indexed from 0 to N1. The light bulbs are all in an OFF state. The system allows you to perform two operations: * boolean isOn(int index) return true if light bulb at given index is ON, false otherwise.
* void toggle(int start, int end) toggle all the light bulbs in the range [start, end] (inclusive). So if the light was ON in that range, flip it to OFF, and if it was OFF > to ON. 
Implement the class that allows me to efficiently use the two given methods
点评:线段树 或者 按2^k分段存 或者根号n大法存……

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

更多Google笔试面试题待更新。
已邀请:

cpcs - 诚实努力

赞同来自: Alina


1 跟丑数差不多
vector<int> C;
int x = a;
int y = b;
while (C.size() < N) {
    if (x < y) {
        C.push_back(x);
        x += a;
    }
    else if (y < x) {
        C.push_back(y);
        y += b;
    }
    else {
        C.push_back(x);
        x += a;
        y += b;
    }
}
return C;

2 荷兰国旗
3 水库采样 见概率短视频
4 分解质因数 看指数的次数是否全是偶数 或者 二分求平方根, 或者牛顿迭代求平方根
5 见概率 短视频
6 [1024 / 5] + [1024 / 25] + [1024 / 125] + [1024 / 625] = 204 + 40 + 8 + 1 = 253
7 98 0 1 0 1?
8 按前缀匹配搜索就好了。
9 完美洗牌 瞎折腾
10 是这个题么? http://www.51nod.com/onlineJud ... D1099
11 前缀和相减 估计要折腾一下。。。O(n)空间
12 找空格 直接翻
13 naive dp
14 看不懂
15 超级复杂论文O(n)可以搞 只会用堆乱搞的
16 和12的区别在哪。
17 和14的区别在哪
18 乱搞题 多机中位数。
19 太geek…… 减法判断符号。
20 自己写排序cmp函数
21 离散化 + 2维线段树
22 难点在哪? 自己筛
23 做过 http://www.patest.cn/contests/pat-a-practise/1067
24 如果用现有的答案 建议改描述 啥叫在指定位置添加。
25 线段树 或者 按2^k分段存 或者根号n大法存……
26 同18 一起搞 没有标准答案

要回复问题请先登录注册