百度2013校园招聘笔试题(自动化平台、测试开发)

鉴于最近在百度文库看到侵权性质的转载并索要积分的情况,以及百度对投诉的消极回应
(如 ID 为 594325551 的 http://wenku.baidu.com/view/5aa818dda58da0116c17498b.html ),
对这家公司的态度表示极度失望。在此郑重重申:
除特别说明外,本站所有文章和作品采用 BY-NC-SA 3.0 Unported License 进行许可。
在该协议下,仅允许非商业性质的转载和演绎,且必须注明来源和作者。

 

百度的笔试应该上个月20号的事情了,一个月后才发是因为今年百度校招现在已经结束,不会对其他人造成麻烦(好吧其实就是我前一阵忙论文去了)。申的职位是自动化平台研发工程师,考题跟开发测试工程师仅一两道题的区别,所以也附了一道测试工程师的题目。考试时间两小时。

以下插播广告一则,框内皆为无意义文字:

招聘小年,度娘力挽狂澜号称全国招聘1500人,吸引苦逼应届生无数。全国各地,火热程度跟混乱程度同步上升,于是该签的签了,不该签的也签了,轮到最后一站魔都,度娘惊讶的发现名额没了。可是发出去的Offer还是那么多,收到的人第二天满怀欣喜和诚意的踏上地铁穿越半个魔都去签约,直到路上接到度娘一通电话说我们不要你了……当然毁Offer顺便还能毁心情,接下来其他的面试也多半受影响,回去之后每家每户幸灾乐祸的跑来慰问,最后上网看帖子发现报该职位的魔都学子居然全军覆没……看见这一套狗血剧情度娘应该也觉得挺好玩的。不过呢,人在做,天在看,企业的声誉都是一点一滴做出来的,恭喜这个世界上又多了好几个百度黑。


– – – –

一、简答题

1. 写出几种常见的哈希算法。简述哈希算法有什么作用。

2. 写出OSI七层网络模型。并指出HTTP,UDP,ARP通信分别位于哪一层。

3. 说明C代码在怎样的情况下可以正常运行,并说明运行原理。

 

二、算法与程序设计题

1. 现要将一车苹果装袋,装3个一袋余2个,装5个一袋余3个,装7个一袋余2个。写一个程序或伪代码,求N个满足条件的苹果数。

2. 写一个递归程序,求字符串中最长的重复字母数量。比如abbbccd返回3,abbc返回2。

3. 现需要开发一种社交关系网络,对一个用户A来说,可能会有如下关系:
A的父子关系:B
A的母子关系:C
A的朋友:C、D、E…
A的同事:F、G、H…

这些关系都是相互的,即C是A的朋友,那A也会出现在C的朋友关系中。

1) 设计数据库和数据表,可包含以下数据表:用户表、关系标签表、关系列表等,表的数量不限;

2) 设计伪代码实现输出A的所有关系表,需要有SQL实现代码,函数原型是
function getRelation(char* personName)

3) 基于1)设计伪代码实现添加一个人到A的关系中,需要有SQL实现代码,函数原型是
function addRelation(int personId, char* relationName, int typeId)
其中personId是A的身份号,relationName是新关系的人名,typeId是关系标签身份号

4) 以上的设计都是基于人名两两不相同而实现的,如果存在相同人名,则需要怎样修改来实现2)和3)的功能?函数原型在必要时可以修改。

 

三、系统设计题

(自动化平台研发工程师)

现需要维护一个100亿个以上元素的大数组,数据已经从小到大排序好。现在对这个大数组进行分段,每段长度不定,但最多不超过20个元素,对每段内的数据进行随机打乱。请设计一种方法重新对该数组进行排序,并分析其复杂度。

(测试开发工程师)

现有1000万个url,其中大约有10万个apk链接。现在百度需要做一个apk搜索引擎,请列出其中所有的有效apk链接,并且避免重复的链接。并且提出一种机制,过滤其中的恶意和虚假apk链接。

 

– – – –

以下是个人的一些解题思路,可能不甚正确,望大家指正和补足:

一、
1. 关于哈希算法:http://baike.baidu.com/view/273836.htm
2. 关于OSI七层网络模型:http://baike.baidu.com/view/547338.htm
3. 这个题很水了。简单的说分三步:编译、链接、执行;细分一点的话,编译包括预处理、编译、优化和汇编;链接分静态和动态。具体可以见这篇文章:http://lavasoft.blog.51cto.com/62575/187229

二、
1. 因为装3个和装7个都余2个,所以等价于装21个余2个,可以考虑以21n+2这样向上检查。

cnt = 0; i = 2;
while (cnt < N) {
	i += 21;
	if (i % 5 == 3) result[cnt++] = i;
}

2. 这道题个人觉得其实非递归算法更容易想到。递归算法可以这样思考:设m和n分别表示字符串S[m..n]的起始和结束下标,k表示S从m开始第一个与m不同的字符的下标,maxRepeated(S[m..n])表示S最长的重复字母数量,则当m=n时,maxRepeated(S[m..n]) = 1;否则maxRepeated(S[m..n]) = max{ k-m, maxRepeated(S[k..n]) }。

unsigned int maxRepeated(char* S)
{
	unsigned int k, max;
	if (*S == '\0') return 0;
	for (k = 1; S[k] != '\0' && S[k] == *S; k++);
	max = maxRepeated(&S[k]);
	max = k > max ? k : max;
	return max;
}

3. SQL不是我的专长所以不贴具体算法了。当时胡乱写了点,用户表拿id作key,含name项;关系标签表给各种关系以relationNameId为key编号;关系列表relationId作为key,含relationName,user1,user2,每一个关系存一项。

三、
(自动化平台研发题)
大数组由于已经排好序,所以分段打乱后总体还是递增的。看题意应该是用归并排序的思路。关键是分段方法,因为每段数据不超过20个,不妨就以20个一组进行强行分段。对排好序的分段S[20k..20k+19], k=0,1,2,…,只要20k不恰好是实际分段的开头,则一定能找到一个p[k]使得S[20k..p[k]]属于上一个分段的一部分,其中20k <= p[k] <= 20k+19。 我们从S[20k..20k+19]的左侧开始扫描,根据S[p[k]+1] > S[20k-1]找到p[k]。由于每段个数不超过20个,则可以对S[p[k]-19..20k-1]和S[20k..p[k]]进行归并,而事实上由于上一个分段的起始不会在p[k-1]的左侧,因此事实上可以对S[max{p[k-1]+1,p[k]-19}..20k-1]和S[20k..p[k]]进行归并。

对S[20k..20k+19]进行归并排序的时间复杂度是O(20log20),扫描得到p[k]的时间复杂度是O(20),对S[max{p[k-1]+1,p[k]-19}..20k-1]和S[20k,p[k]]进行归并的时间复杂度是O(20),因此整体的时间复杂度是O((n/20)*(20log20+20+20))=O(n)。

unsigned int processGroup(int* S, unsigned int k, unsigned int last_p)
{
	unsigned int p;
	mergeSort(S, k*20, k*20+19);
	if (k == 0) return 0;
	for (p = 0; S[p] <= S[k*20-1]; p++);    // find p[k]+1
	if (p == 0) return 0;           // for sector head, do nothing
	p--;                                    // p[k]
	last_p = last_p+1 > p-19 ? last_p+1 : p-19;
	merge(S, last_p, k*20-1, k*20, p);
	return p;
}

(2012-11-20 更新)这道题也可以采用1楼QJ的思路,算法更方便(感谢提供算法)。由于每个分段不会超过20个元素,故对每一个k>19,元素S[k]一定大于S[k-19]前的任意一个元素,故可以直接在S[k-19..k]中做插入。一次插入的时间复杂度为O(20),整体的时间复杂度为O(20n)=O(n)。

 

(测试开发题)
为解决重复url问题,需要建立类似哈希表的结构。考虑到10万量级空间占用较大,想到直接使用外存来做,按照url的路径建立目录结构即可。例如http://domain/dir1/dir2/name.apk可置于$ROOT/domain/dir1/dir2下,可下载下来(易于检查恶意和虚假链接),也可不下载只生成一个占位文件(此时可以根据apk的大小等属性来判断是否为恶意和虚假链接)。

以上的叙述,尤其是第三大题只是我的个人思路,如大家有什么更好的思路欢迎讨论指正。

鱼尾Swing

国内某理工学校电子类专业85后。热爱PS,热爱WEB,对各种技术都好奇。平时看看动画,听听音乐,做爱做的事。作为工坊的工头,负责工坊的维护,操劳各种苦力工作。

More Posts - Website

Follow Me:
Twitter

6 Responses

  • 第三大题第一题应该是O(n)的。
    我没有很理解你这里用归并的目的,毕竟这里归并的话会有很多冗余的比较,因为s[i]与s[i+20..n]是没有必要比较的。
    其实O(n)的算法很简单,简单的插入排序就好了。每次插入的时候只需要考虑最后20个元素,之前的已经固定了,因为s[i]在排完序后的数组的里的位置肯定大于i-20。

    • 我原来的复杂度可能算错了,应该也是O(n)。我的算法是每20个强行分段用归并排序,段首处劈开的两小段由于都是排好序的,可以直接用归并算法,这样每段20个实际只需要排一次并一次。用插入排序的话,每个元素都要对前20个元素进行插入,复杂度应该是一样的。

  • 还有百度不是一共就研发、测试、数据挖掘三种职位的嘛

    • 我这边是测试类的题目,每个小职位会有一到两道大题不一样。数据挖掘似乎简答题也是和测试一样的。
      另外你的另一个问题我不想惹麻烦,先删掉了,私下联系吧。

Leave a Reply