百度2011实习生招聘笔试题

aftyingjiesheng

百度2011实习生招聘笔试题
: }3 h3 J( C8 f
笔试时间：5月7日
) f( F" l! X& [" ~& _

3 m7 z. v: j+ L3 j4 N, L) Q2009百度实习笔试题Zz

一、编程题（30分）
0 G4 [- h' l5 W. e% H输入：N（整数）
输入：数据文件A.txt，不超过6条记录，字符串长度不超过15个字节
, U: j0 g6 }# b% ?( a0 U文件格式如下：
: h# X" l+ |" e: _5 q字符串\t数字\n
4 q! D+ m/ _6 |4 w' _9 r' ~说明：
9 r! N3 `, z8 F每行为1条记录；字符串中不含有\t。
数字描述的是该字符串的出现概率，小于等于100的整数。
多条记录的出现概率之和为100，如果A.txt不满足该条件，程序则退出；
0 v) @7 ~; v$ m" {& w9 d如果文件格式错误，程序也退出。
* q! R/ u. p% B8 [& n+ s0 q, h要求：
6 U# D) d. E6 Q: F编写一个程序，输入为N（正整数），读入文件A.txt，按照字符串出现概率随机
; c/ }: g" C1 d$ ^地输出字符串，输出N条记录
例如：
( M1 I8 S, T7 M: c, v$ @; `输入文件A.txt
abc\t20
a\t30
de\t50
" E# ?* j, B- Q/ W9 G0 [- @% ^输入为：10
即 abc有20%的概率输出，a有30%的概率输出，de有50%的概率输出，输出10条记
录
0 o. m5 w* @$ a3 R* t5 V以下为一次输出的结果,多次输出的结果可能不相同。
- j7 e4 m) f' }1 G& Q  O/ babc
a
de
. G( H: s6 I" l) r* F( e" ede
abc
0 t- g* n8 P1 n: {" Lde
5 N; x: h7 K5 Oa
; c' X4 D! M; Y) mde
a
7 r1 g& r3 O+ h. K  Ade
6 V2 V$ ]' A$ W  G' {3 F: ?二、算法题（35分）
题目描述：
设有n个正整数，将它们联接成一排，组成一个最小的多位整数。
, u" p/ ?  _/ K+ o: l/ `程序输入：n个数
* W! h  l2 f& T& J程序输出：联接成的多位数
例如：
n=2时，2个整数32，321连接成的最小整数为：32132，
9 _6 y! v% A0 [1 R5 f2 fn=4时，4个整数55，31，312, 33 联接成的最小整数为：312313355
% I- v/ ^3 J) k8 g' B9 {! I$ s[题目要求]
1. 给出伪代码即可，请给出对应的文字说明，并使用上面给出的例子试验你的算
2 ^& z  q, q7 ~4 O法。
2. 给出算法的时间空间复杂度。
" s" d" s  B( e1 I9 W/ W3. 证明你的算法。（非常重要）
三、系统设计题（35分）
, x2 |/ b* F" y, t+ ~# H$ g: E4 K& l在一个有1000万用户的系统中，设计一个推送(feed)系统。以下是一些预定义概
8 E. w# _5 t' p2 e! [念
1、用户：在这个系统中，每个用户用一个递增的unsigned int来表示user id(简
( {' E' L- y; g5 _; E写为uid)；则uid的范围是从1到1000万的正整数。
2、好友：用户之间可以形成好友关系，好友是双向的；比如说uid为3和uid为4的
两个用户可以互为好友。每个用户好友的上限是500个；用户之间的好友关系可以
被解除
3 [; i2 y7 }7 ~$ `0 G* K2 g3、活动：每个用户只能发文章；文章可以被作者删除，其他人不能删除非自己发
表的文章；每篇文章通过一个blogid表示。
4、feed：我们希望，每个用户可以看到他所有好友的活动列表，在这个简化的系
统中就是所有好友的文章更新列表。
5、访问量要求：所有feed访问量每天在1亿量级；所有的blogid增加量每天在百
万量级。
题目：请在以上限制条件下，设计一个高效的feed访问系统。
) `0 F, m. O7 u2 D* W要求：
1、能够尽快的返回每个用户的好友feed列表，每个用户可以最多保留1000条feed
+ n' \: }+ f. f8 ]$ T. Z* s. G；feed的展现按照时间倒排序，最新的在最前面
4 Q! ?2 n) K4 v4 C( S* {2、用户删除某篇文章后，被推出去的feed需要及时消失。即每个用户看到的好友
feed都是未被删除的
3、尽可能高效。
: D& g7 E; n) D2 {7 P
* v% R% I/ c' t: ?4 YZz
信息来自:阿凡提求职社区
——
百度历年实习生招聘真题
http://bbs.aftjob.com/thread-606504-1-1.html
2010年百度实习笔试真题（全套，2010年5月）
2 G. B. l7 `6 ~+ W' ohttp://bbs.aftjob.com/thread-606500-1-1.html
2009年百度实习笔试真题
http://bbs.aftjob.com/thread-114579-1-1.html
百度这三年实习招聘必考的题目
http://bbs.aftjob.com/thread-606503-1-1.html
百度历年校园招聘笔试题
http://bbs.aftjob.com/thread-417000-1-1.html
- Y( q2 e% o7 t% U7 m( b——
面试时间：5月8日开始
工作人员电话通知笔试通过的同学到指定地点进行现场面试。

黄俊晓

顶一下