笔试题目:9道单选+3道问答
时间:100分钟
单选题:
1,求两个二进制数的异或值,基本上学过一点计算机的东西的人都能对的题目。。
2,递归函数最终会结束,那么这个函数一定(不定项选择):
a. 使用了局部变量
b. 有一个分支不调用自身
c. 使用了全局变量或者使用了一个或多个参数
3,大概是如下的函数:
int someFunc(int x){
if (x == 0)
return 0;
else
return x + someFunc(x - 1);
}
问这个计算的是什么。。。
4,void foo(int *a, int*b)
{
*a=*a+*b;
*a=*a-*b;
*a=*a-*b;
}
int a=1;b=2;c=3;
foo(&a,&b);
foo(&b,&c);
foo(&c,&a);
printf("%d,%d,%d\n",a,b,c);结果
5,n个顶点和m个边连通图中至少去掉多少条边才可生成一颗生成树
6、如何减少换页错误?
a. 进程倾向于占用CPU
b. 访问局部性(locality of reference)满足进程要求
c. 进程倾向于占用I/O
d. 使用基于最短剩余时间(shortest remaining time)的调度机制
e. 减少页大小
7,给出正则表达式,选和它属于同一语言的选项
8,下面哪项不是链表优于数组的特点?
a. 方便删除
b. 方便插入
c. 长度可变
d. 存储空间小
9,如下函数:
T(x) = 1 (x <= 1)
T(n) = 25 T(n/5) + n^2
问T(n)随n的增长。
选项大概是这样的:
O(n^2),O(n^2logn)等等的。。
问答:
1,写两个N*N的矩阵的乘法,给出了C的格式,你可以选择你喜欢的语言去写。。
int* multi(int* a1, int* a2, int N){
}
2,寻找一个单向链表的中项,如果存在两个则返回前一个。给出了C的格式,同样你可
以选择。。。。
struct {
Node* next;
int value;
} Node;
Node* someFunc(Node* head){
}
3,给一个长度为n的整数数组,只允许用乘法不允许用除法,计算任意(n-1)个数的组合
乘积中最大的一组。。。写出算法的时空复杂度。
ps:怀疑这道题目出错啦。。虽然我也做错了。。。。。。
一些补充:
1,问答的第一题是google上学期 intern的大题原题;
2,google很喜欢考链表,无论intern的面试以及两次的笔试都有这样的题目;
3,google一般大题第三道都是写算法的时空复杂度;
4,选择题基本上偏简单,但是要做得准确率高似乎并不那么容易;
5,根据传言,小道消息,人云亦云以及以讹传讹,google的高速审卷政策来源于审卷时
以选择题为主,如果你全对啦,那么恭喜你pass啦;如果你错了好几道,那么下次努力
吧,如果还有下次。。。大题基本是做参考的。。。
6,选择题很多记不清了,因为一遍做下来的,回去随便扫了两眼。。。加上过了这几个
小时,记不得了。希望大家补充修正以及修改。。。
7,google会在11号开始3天内发面试通知,据小道消息等等,有四轮面试。bless大家~~
阅读(990) | 评论(0) | 转发(0) |