2011 年 Google 招聘笔试题完整版
一、选择题
(1) 以下哪个字符串不能被正则表达式 a(bc)*d* 匹配到?
A.
ad
B.
abcd
C. abc
D.
abccd
(2) 在 x86 cpu 中,下面哪种运算速度最慢?
A. 加
B. 减
C. 乘
D. 除
(3) 下面程序输出的结果是什么?
void main()
{
bool first=true;
int sum =0;
int current_value;
for(unsigned short i=65535;i>=0;--i )
{
if(first)
{
}
current_value=65535;
sum+=current_value%3;
first=false;
else
{
sum+=-current_value%3;
if(current_value<=0)
printf("%d,%d",sum,i);
break;
{
}
}
}
}
A.
65535, 0
B.
65536, 1
C.
65536, 65535
D.
65536, 0
(4) 书架上有编号为 1-19 的 19 本书,从中拿 5 本,问 5 本编号都不相邻的拿法有多
少种?
了。
A.
2002
B.
3003
C.
11628
D. 比 C 大的一个数,具体多少我忘记
(5) 现在有一套房子,价格 200 万,假设房价每年上涨 10%,一个软件工程师每年固定
能赚 40 万。如果他想买这套房子,不贷款,不涨工资,没有其他收入,那么他需要几年才
能攒够钱买这套房子?
A.
5 年
B.
7 年
C.
8 年
D.
9 年
E. 永远买不起
(6) 一棵满二叉树,一共有 n 个叶子节点,请问该二叉树一共有多少个节点?
A.
2n-1
B.
2n
C.
n-1
D.
n
(7) 下列哪种排序方法在最坏情况下的时间复杂度是 nlgn?
A. 归并排序
B. 快速排序
C. 冒泡排序
D. 插入排序
(8) 有两个从小到大排好序的数组,长度分别是 N 和 M,将这两个数组合并成一个有序
数组的最小比较次数是:?
A min(N,M)
B M+N-1
C N+M
D max(M,N)
(9) 关于 TLB 和 Cache 的说法中,哪个是错的?
A. TLB 与 Cache 中保存的数据是不同的
B. TLB miss 后,有可能直接在 Cache 中找到页表内容
C. TLB miss 后会导致程序出错,但是 Cache miss 不会
D TLB 和 Cache 的命中率都与程序的访存模式有关
(10) 关于数据库的说法,哪个是错误的?
A. 每个表都必须有主键
B. 跨表查询可能非常慢
C. 数据库不支持多个用户对同一个表进行写操作
D. 多维索引可以用 KD 树实现
二、编程算法题
(1) 编程实现多项式求值:
f(n)=a0+ a1*x^1 + a2*x^2 +…+ an*x^n,
函数声明如下:double foo(double x, double *A, int N)。
(2) 现在有 n=2^k 支足球队,编号为 0,1,…,n-1,给出 2 维数组
winner[][],winner[i][j]表示当编号 i 和 j 的会胜出的队伍的编号,并且没有平局,输入
保证 winner[i][j]==winner[j][i],现在给出一个单败淘汰赛的签位一维数组
order[],order[i]表示第 i 个签位上的队伍的编号,order 保证是 0 到 n-1 的一个排列。返
回比赛最后的排名顺序,同一轮被淘汰的队伍名词并列,并列的队伍之间的顺序任意,要求
时间和空间复杂度尽量的低,将结果写到一维数组 result[]里面即可。
接口定义:
c++:
void calculate_result(int n,vector> winner,vector
order,vector result);
例子:
N=4,winner={{0,1,2,3},{1,1,2,1},{2,2,2,3},{3,1,3,3}},order={0,1,2,3}
…
(3) KOF 游戏相关,玩过 KOF(拳皇)的人都知道,玩的时候如果按照一定的按键次
序就会连招,连招的威力很大。现在题目的意思是:每招用一个大写字母表示,如 ABC … Z ,
现给定 n 个连招公式:S→T,每个公式的 S 长度都相同,都为 m ,T 的长度为 1 。
每个公式都代表一个连招规则,表示如果之前的 m 招为 S,那么可以在后面连出一招 T, 在
前 m 招的时候可以随便连,但 m+1 招后就必须遵循连招公式。现在要写一个算法,计
算最长连招的长度;如果可以无限连招,则返回 def 。(1≤n, m≤100)
这里有一个例子:n=4, m=3,连招公式为:ABC→D,ABC→C,CCA→A,BCC→A。连招
公式的意思是:A、B、C 可以连出 C,也可连出 D,C、C、A 可以连出 A,B、C、A、可以连
出 B。这时候可以得到最长连招公式:ABC→C→A→A,即最长连招公式长度为 6 。
题目要求给出算法思想并结合一定的伪码,不需要实现。