2010.9.27--Google笔试归来

jayjiazhigang

昨天刚参加Google宣讲和笔试，考得很基础，共享一下笔试题目，奇文共赏之。顺便攒RP，哈哈10道选择题，3道大题。10道选择对六道才看你答题，否则直接被BS。
1.考的是正则表达式，什么字符串匹配，没看过，:87)~~。
2.在Intel 8086中，加减乘除那个整数运算最耗时。很基础哇~~
3.看程序，写算法，考察的是unsigned short类型的范围。程序有点长，变量名还相似，想不起来了，
4.19本书，编号从1-19。从中抽五本，任意相邻两本不是相邻编号的情况有多少种。这个题谁会啊，大家发帖探讨一下。
5.N为满二叉树的叶子节点数，求总结点数。确实很基础~~
6.排序算法：在最坏情况下时间复杂度为O（nlogn）的是归并，快速，冒泡，插入中的哪个。
7.房价200万，每年以10%的速度递增，工程师为40万年薪，问什么时候买得起房。
8.有两个有序数组长度为M和N，将两个数组合并，最好情况下比较几次。M次，N次，Min(M,N),Max(M,N)
9_TLB和Cache的区别，这个题不会，没听说过TLB。上网查了查，TLB：Translation lookaside buffer,即旁路转换缓冲，或称为页表缓冲；里面存放的是一些页表文件（虚拟地址到物理地址的转换表）。大家还是自己上网了解吧。
10.数据库的试题，偶记不清了，不过不难。

一 写函数double value(double x,double A[],double N) double A[N]存储多项式f(x)=a0+a1x+a2x^2+……的系数。N为已知。

二 有2^K队伍比赛，按照order给出一个比赛顺序的排列，order表示编号为i的队的位置，呀呀，记不太清了，有winner[j]表示i,j两队比赛结果，只有胜负没有平局，winner[j]=winner[j]求result[]里面存放各队比赛排名。貌似用递归，只是小弟拙见，哈哈，

三 KOF里连招，简化为ABCD……Z求最长连招……记不清了，见谅，XDJM补充。有答案飘过来啊