2010年9月27日晚在北京进行了2011年度招聘宣讲会，宣讲会结束后就开始现场笔试，第二天6点之前就可以得到面试资格的通知。据当时Hr所说，根据以往经验，其中800笔试者中会有40名入选面试。Google的效率和招人的精益程度可见一斑。

笔试一共有10个选择题和3个编程算法题，Google的要求是前面的选择题至少正确6个以上，判卷人才会看后面的三个算法题。下面是回忆版的笔试题，有的已经记不起来了，有可能回忆的不太准确。大家看看这些题，在找工作的时候有个参考，好运Ｅｖｅｒｙｏｎｅ～～～

一：选择

1）以下哪个字符串不能被正则表达式 a(bc?)d 匹配到？

A abcd B abd C abc D acd

2)在X86平台下，下面哪种运算速度最慢？

A 加 B 减 C 乘 D 除

3)下面程序输出的结果是什么？

A 65535，0 B 65536，65535

C 65536，1 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:2^n-1 D:2n+1

7)下列哪种排序方法在最坏情况下的时间复杂度是nlgn?

A:归并排序 B：快速排序 C：冒泡排序 D：插入排序

8）这个题我忘记了，囧

9）关于TLB和Cache的说法中，哪个是错的？

A 如果Cache发生错误，会引发TLB发生错误

B TLB发生错误后，要到Cache中读取数据

C 忘记了

D 如果TLB发生错误，会引发Cache错误

10）关于数据库的说法，哪个是错误的？

A 每个表都必须有主键

B 忘记了

C 不能同时对同一个表进行写操作

D 数据库中的**索引可以用DT树？实现

二、编程算法题。

1）编程实现多项式求值。f(n)=a0 + a1*x^1 + a2*x^2 +…+ an*x^n

函数声明如下：double foo(double* pArray, int len, double x)

2)这个题目有点长，记得不太清楚了。不过不难。

3)KOF游戏相关，玩过KOF（拳皇）的人都知道，玩的时候如果按照一定的按键次序就会连招，连招的威力很大。现在题目的意思是：每招用一个大写字母表示，如ABC…Z，现给定n个连招公式：S→T，其中S长度为m，T的长度为1。在前m招的时候可以随便连，但m+1招后就必须遵循连招公式。现在要写一个算法，计算最长连招的长度；如果可以无限连招，则返回def。1≤n,m≤100

这里有一个例子：n=4，m=3，连招公式为：ABC→C，ABC→D，CCA→A，BCC→A。连招公式的意思是：A、B、C可以连出C，也可连出D，C、C、A可以连出A，B、C、A、可以连出B。这时候可以得到最长连招公式：ABC→C→A→A，即最长连招公式长度为6。

题目要求给出算法思想并结合一定的伪码不需要实现。