选择题三道算法题r
r
选择题没什么难的最后一道考的数据库使用什么存储结构不会做。。r
r
算法题r
第一题没什么好说r
第二题可破坏一个数组A0N1的条件下使用最少的内存判断是否存在相同的元素r
我的做法是堆排序时间ONlogN空间O1复杂度上来看应该最优了r
第三题已知每个点的父节点，求这棵树的最大独立集r
用递归求解类似动态规划但是不存在重叠子状态经典算法问题了r
预处理每个节点的子节点存在一张表里r
时间ON）空间ON）r
r
大家做的结果是这样吗？r
r
发信站饮水思源2006年10月11日030604星期三站内信件r
r
开章明义，我是个废人，上来积攒rp了。r
在宣讲会的时候，听旁边的师姐说上海只招两个职位每个职位只招一个人。r
现在后悔只选了北京和上海的SWE了。r
不过反正……也不指望了。。。r
r
r
笔试题目：9道单选3道问答r
时间：100分钟r
我做的是B卷。r
r
单选题：r
1，求两个二进制数的异或值，基本上学过一点计算机的东西的人都能对的题目。。r
r
2，不记得了。。也是不需要思考的题目。。r
r
3，大概是如下的函数：r
i
tsomeFu
ci
txr
ifx0r
retur
0r
elser
retur
xsomeFu
cx1r
r
问这个计算的是什么。。。r
r
4，不记得了。。不需要思考吧。。r
r
5，不记得了。。不需要思考吧。。r
r
6，参见2，4，5。。r
r
7，似乎需要思考一下。。r
r
8，问链表结构和数组相比的优势不包括哪项，r
包括：r
插入的时间r
删除的时间r
存储空间r
剩下两个不记得了。。r
r
9，如下函数：r
Tx1x1r
T
25T
5
2r
问T
随
的增长。r
选项大概是这样的：r
O
2，O
2log
等等的。。r
r
问答：r
1，写两个NN的矩阵的乘法，给出了C的格式，你可以选择你喜欢的语言去写。。r
i
tmultii
ta1i
ta2i
tNr
r
r
2，寻找一个单向链表的中项，如果存在两个则返回前一个。给出了C的格式，同样你可r
以选择。。。。r
structr
Node
extr
i
tvaluer
Noder
NodesomeFu
cNodeheadr
r
r
3，给一个长度为
的整数数组，只允许用乘法不允许用除法，计算任意
1个数的组合r
乘积中最大的一组。。。写出算法的时空复杂度。r
ps：怀疑这道题目出错啦。。虽然我也做错了。。。。。。r
r
一些补充：r
1，问答的第一题是google上学期i
ter
的大题原题；r
2，google很喜欢考链表，无论i
ter
的面试以及两次的笔试都有这样的题目；r
3，google一般大题第三道都是写算法的时空复杂度；r
4，选择题基本上偏简单，但是要做得准确率高似乎并不那么容易；r
5，根据传言，小道消息，人云亦云以及以讹传讹，google的高速审卷政策来r