谷歌笔试题函数

谷歌笔试题（函数）

单选题：
1，求两个二进制数的异或值，基本上学过一点计算机的东西的人都能对的题目。。
2，不记得了。。也是不需要思考的题目。。
3，大概是如下的函数：
int someFunc(int x){
if (x == 0)
return 0;
else
return x + someFunc(x - 1);
}
问这个计算的是什么。。。
4，不记得了。。不需要思考吧。。
5，不记得了。。不需要思考吧。。
6，参见2，4，5。。
7，似乎需要思考一下。。
8，问链表结构和数组相比的优势不包括哪项，
包括：
插入的时间
删除的时间
存储空间
剩下两个不记得了。。
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啦；如果你错了好几道，那么下次努力吧，如果还有下次。。。大题基本是做参考的。。。