2011年Google招聘笔试题完整版

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 。 题目要求给出算法思想并结合一定的伪码，不需要实现。