Google 面试题

1、 两个二进制数的异或结果
2、 递归函数最终会结束，那么这个函数一定（不定项选择）：
1.  使用了局部变量    2. 有一个分支不调用自身
3.  使用了全局变量或者使用了一个或多个参数
3、以下函数的结果？
int cal(int x)
{
if(x==0)
return 0;
else
return x+cal(x-1);
}
4、 以下程序的结果？
void foo(int*a, int* b)
{
*a = *a+*b;
*b = *a-*b;
*a = *a-*b;
}
void main()
{
int a=1, b=2, c=3;
foo(&a,&b);
foo(&b,&c);
foo(&c,&a);
printf("%d, %d, %d", a,b,c);
}
5、下面哪项不是链表优于数组的特点？
1. 方便删除 2. 方便插入 3. 长度可变 4. 存储空间小
6、T(n) = 25T(n/5)+n^2的时间复杂度？
7、n个顶点，m条边的全连通图，至少去掉几条边才能构成一棵树？
8、正则表达式(01|10|1001|0110)*与下列哪个表达式一样？
1.(0|1)*  2.(01|01)*   3.(01|10)*   4.(11|01)*   5.(01|1)*
9、如何减少换页错误？
1. 进程倾向于占用CPU   2. 访问局部性（locality of reference）满足进程要求
3. 进程倾向于占用I/O  4.使用基于最短剩余时间（shortest remaining time）的调度
机制  5. 减少页大小
10、实现两个N*N矩阵的乘法，矩阵由一维数组表示
11、找到单向链表中间那个元素，如果有两个则取前面一个
12、长度为n的整数数组，找出其中任意(n-1)个乘积最大的那一组，只能用乘法，不可
以用除法。要求对算法的时间复杂度和空间复杂度作出分析，不要求写程序。
1 0
2。2
3。(n+1)*n/2
4.1 3 2
5.4
6. O(n^2*lgn)
对于T(n) = a*T(n/b)+c*n^k;T(1) = c 这样的递归关系，有这样的结论：
if (a > b^k) T(n) = O(n^(logb(a)));
if (a = b^k) T(n) = O(n^k*logn);
if (a < b^k) T(n) = O(n^k);
T(n) = 25T(n/5)+n^2 = 25(25T(n/25)+n^2/25)+n^2
= 625T(n/25)+n^2+n^2 = 625T(n/25) + 2n^2
= 25^2 * T( n/ ( 5^2 ) ) + 2 * n*n
= 625(25T(n/125)+n^2/625) + 2n^2
= 625*25*T(n/125) + 3n^2
= 25^3 * T( n/ ( 5^3 ) ) + 3 * n*n
= ....
= 25 ^ x * T( n / 5^x ) + x * n^2
T(0) = 25T(0) + n^2 ==> T(0) = 0
T(1) = 25T(0)+n^2 ==> T(1) = 1
x = lg5 n
25 ^ x * T( n / 5^x ) + x * n^2
= n^2 * 1 + lg 5 n * n^2
= n^2*(lgn)
后面的几题在想，最后一题要不要考虑负数？
．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．
1、0
2、2，3（eg, if(n&2) return 1; else return a(n-1)+a(n-2)）
应该要使用参数满足某个条件然后退出。
3、x(x+1)/2
4、1，3，2
5、4
6、O(log5(n))
7、(n-1)(n-2)/2＝n(n-1)/2-(n-1)
8、3
9、2，4 ?
10、
void matrixmul(int a[N][N], int b[N][N], int result[N][N])
{
memset(result, 0, sizeof(int) * N * N);
for(int i = 0; i & N; i++)
{
for(int j = 0; j & N; j++)
{
for(int k = 0; k & N; k++)
{
result[i][j] += a[i][k] * b[k][j];
}
}
}
}
11、用两个指针，一个步长为1，一个步长为2，当步长2的那个指针走到头时，这个时候步
长为1的那个指针刚好指着中间的那个结点。
12、
思路：定义一临时量保存当前最小的数(min)，和一个保存总数的(sum)，开始比较（从第
2个开始）如果有比这大的，那么乘上，如果比这小，那么乘于min,把小数放到min中。
算法复杂度为O(n)
空间复杂度为O(2)
．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．
．
11
somestruct* FindMiddle(somestruct* pHead)
{
if (pHead == NULL || pHead->next == NULL)
return pHead;
somestruct* p1 = pHead, p2 = pHead->next;
while (p2 != NULL && p2->next != NULL)
{
//每次p1前进一位，p2前进2位
p1 = p1->next;
p2 = p2->next->next;
}
return p1;
}
1.写程序判断是否字符串A里每个字符在A中出现的次数都大于在字符串B中出现的次数。
注：此题我是对每个字符出现的次数分别统计，然后比较。重复的字符重复统计比较，所以效率很低。不知有什么好的改进方法？
2.对一个数组S，求其中满足要求的最大元素C。要求C满足等式C=A*B，其中A、B也是数组S中的元素。请用能想到的最优算法，分析时间和空间复杂度。（用语言描述算法，不用写程序）
注：这个题我当时做的方法在时间上要用o(n^3)，事后想出了个o(n^2 logn)的方法。不知有没有更好的方法。
1. typedef struct {
Node * node;
}Tree;
typedef struct {
Node * left;
Node * right;
}Node;
请写出深拷贝函数：Tree * deepCopy(Tree *tree);
2. 输入一个整型数组，对该数组进行随机排序，写出该函数
void randomShuffle(int *a, int len);
可以使用随机函数发生器
int random(int N); //假设是完全的随机函数，返回值是0 - N-1的整数
3. N个人排成一圈，指定第一个人，去除他，然后跳着一人去除第3人，以次类推，最后
的那一人获胜。给定这N个人和第一个人的位置，你该如何选取位置才会获胜。
让你写最优算法，并计算时间和空间复杂度。不要求写出代码，解释算法即可。
Joseph问题的数学方法
无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅
程序写起来比较烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上
千万)的时候，几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要
求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，
就要打破常规，实施一点数学策略。
为了讨论方便，先把问题稍微改变一下，并不影响原意：
问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继
续从0开始报数。求胜利者的编号。
我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的
约瑟夫环（以编号为k=m%n的人开始）:
k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2
并且从k开始报0。
现在我们把他们的编号做一下转换：
k --> 0
k+1 --> 1
k+2 --> 2
...
...
k-2 --> n-2
k-1 --> n-1
变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：
例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况
的解吗？！！变回去的公式很简单，相信大家都可以推出来：x‘=(x+k)%n
如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)
个人的解呢？当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题！好了，思
路出来了，下面写递推公式：
令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]
递推公式:
f[1]=0
f[i]=(f[i-1]+m)%i; (i>1)
有了这个公式，我们要做的就是从1-n顺序算出f[i]的数值，最后结果是f[n]。因
为实际生活中编号总是从1开始，我们输出f[n]+1,由于是逐级递推，不需要保存每
个f[i]，程序也是异常简单：
#include
int main()
{
int n, m, i, s=0;
printf ("N M = ");
scanf("%d%d", &n, &m);
for (i=2; i
int mod(int x,int n)
{ return (x%n+n)%n; }
int f(int n,int m,int t) {
if(n==2) return mod(t,n)==1?2:1;
else if(mod(t,n)!=mod(m,n))return mod(f(n-1,m,mod(t-m-1,n)+1)+m-1,n)+1;
else return mod(f(n-1,m,n-1)+m,n)+1;
}
int main(int arg, char* args[])
{
int k,n,m,t;
freopen(args[1], "r",stdin);
scanf("%d",&k);
while( k-- ) {
scanf("%d%d%d",&n,&m,&t);
printf("%d\n",f(n,m,t));
}
return 0;
}
一、 选择题：
1.
456×567＝150216
问这是在什么进制下？
A.9 B.10 C.12 D.18
2.
二叉树前序：ABCEDF，中序：CBADEF，请问后序？
3.
char s[][10]={"hello","google"};
char *p=s[0];
printf("%d",strlen(p+10));
结果为
A. 10 B.0 C.5 D.6
4
G: S->uvSvu|w，请问S
5
给出前序遍历和中续遍历 求后序遍历（题目似乎有错）
6
f(0)=1, f(n)=n*f(n-1)+1  求它的复杂度
7
等待 就绪 运行 挂起的 关系
8
有6个进程以及7个同类资源。每个进程每次申请一个资源，并且最多需要2个资源，问会不会死锁
9
一个自动机的文法题目
10
一个文件分成3份，并且每份有一个拷贝，每个拷贝出现错误的概率10％，问整个文件出错的概率
（3％）
二、 算法题：
1  一个图G，编写两点间是否存在路径的函数
2 有一棵树，每个节点与子节点间看成是有距离的，都给定一个整数。现在要延长某些边，使得根节点到所有叶节点的路径长度都相等。求这种情况下，所有路径长度最短是多少。
1、 一些奥运组委会每个月都有定期的会议，有一些委员同时在多个组委会中，假设这些组
委会是：C1={A,B,C} C2={D,E,F} C3={A,C,E} C4={B,D,F} C5={E,F} C6={B,F}。并且任何
一名委员在同一天只能参加一个会议，问每月至少有一个组委在开会的日子最少有几天？
A.  3
B.  4
C.  5
D.  6
2、 下面一段代码的输出是
void f(char *p) {
if (*p >= ‘A’ && *p <=’Z’)
*p = *p – ‘A’ + ‘a’;
if (*p >= ‘a’ && *p <= ‘z’)
*p = *p – ‘a’ + ‘A’;
}
int main() {
char s[] = “ABC+abc=defDEF”;
while (*p != ‘\0’) { f(p); p++; }
cout << s;
return 0;
}
A.  abc+ABC=DEFdef
B.  abc+abc=defdef
C.  ABC+ABC=DEFDEF
D.  abcABCDEFdef
3、 高度为H的堆的最小元素数目是多少？
A.  H^2
B.  H^2-H
C.  2^H-1
D.  2^(H-1)
E.  2^(H-1)+1
4、 下列排序算法中，当要排序的数列已经为有序时，耗费时间最多的是
A.  冒泡排序
B.  选择排序
C.  插入排序
D.  归并排序
5、 定义函数f如下：
int f(int n) {
if (n <= 10) return n+3;
return f(f(n – 7));
}
那么f(30)的输出结果是
A.  10
B.  11
C.  12
D.  13
6、 已经树T的结点集为{A, B, C, D, E, F, G, H, I, J}，边的集合为{, , ,F>, , , , , , }，可知树T至少有多少个叶节点？
A.  3
B.  4
C.  5
D.  6
7、 下面对进程的描述中错误的是
A.  进程是动态的概念
B.  进程需要处理机
C.  进程是有生命周期的
D.  进程是指令的集合
8、 产生死锁的原因不包括
A.  系统资源不足
B.  共享互斥资源
C.  进程的推进顺序不当
D.  并发执行的进程数太多
9、 某服务器要与大量客户端进行频繁的小数据量通信，为了达到更好的性能，应该采用下
面的哪种协议？
A.  TCP
B.  ICMP
C.  HTTP
D.  UDP
10、下面文法（或者用自动机表示）描述的语言是：S=aA|bB; A=aS|bC|e; B=bS|aC; C=bA|
aB;
A.  奇数个a和一些b
B.  偶数个a和一些b
C.  奇数个a和偶数个b
D.  偶数个a和奇数个b
程序设计与算法
1、 用单链表实现一个存储空间管理器，包括分配和释放空间。要求释放的时候合并相连空
闭地址。分配空间的策略可以自选，并说明所用的策略的优点和缺点。（下面的框架是C++
描述的，你可以用你熟悉的语言。）
void* xmalloc(unsigned int size)
void xfree(void* p)
2、 给定n个数，要从中选出m个数使其标准差最小。分析你的算法的时间复杂度，解释算法
即可，不必写代码。
3、 你编写过的最有创意的项目是什么？有人使用这个创意吗？