百度2011实习生招聘笔试题

aftyingjiesheng

百度2011实习生招聘笔试题
# I8 L2 H2 t' `; g3 h) T
) f3 }. H% O$ F5 |笔试时间：5月7日
3 X" [9 T' ?! x# w7 _& D

6 F1 p1 P' _5 h8 C9 ^: y2009百度实习笔试题Zz

5 @" j2 F; d3 s一、编程题（30分）
输入：N（整数）
输入：数据文件A.txt，不超过6条记录，字符串长度不超过15个字节
文件格式如下：
字符串\t数字\n
说明：
每行为1条记录；字符串中不含有\t。
/ e5 n9 A* G7 A5 S$ M( n3 X6 ~数字描述的是该字符串的出现概率，小于等于100的整数。
多条记录的出现概率之和为100，如果A.txt不满足该条件，程序则退出；
如果文件格式错误，程序也退出。
5 B  t$ Q( Q& y/ |' O6 M要求：
编写一个程序，输入为N（正整数），读入文件A.txt，按照字符串出现概率随机
" S0 J$ z! d( A, J; d3 k( m* |地输出字符串，输出N条记录
- p8 _$ p. A& a$ _例如：
输入文件A.txt
abc\t20
a\t30
de\t50
输入为：10
即 abc有20%的概率输出，a有30%的概率输出，de有50%的概率输出，输出10条记
6 [, y& W3 I3 q录
以下为一次输出的结果,多次输出的结果可能不相同。
abc
4 d8 b$ r- e9 A6 Ja
de
: z) y# G, O" i/ ^0 T8 Ade
9 M# h7 q5 m, b. h3 Babc
5 L* O) V: Y- u( X7 x$ Yde
; b, F4 H0 h) d  w& qa
de
a
de
二、算法题（35分）
$ O4 Z, v5 k3 R% s9 }: r: u4 b题目描述：
设有n个正整数，将它们联接成一排，组成一个最小的多位整数。
; R3 i, `( r! j程序输入：n个数
3 ^/ @% v, W- v/ q程序输出：联接成的多位数
9 k. E3 _' y* B* ]9 @1 C- H2 Q7 v4 D例如：
n=2时，2个整数32，321连接成的最小整数为：32132，
n=4时，4个整数55，31，312, 33 联接成的最小整数为：312313355
' [1 N5 S5 }% r# D  z[题目要求]
1. 给出伪代码即可，请给出对应的文字说明，并使用上面给出的例子试验你的算
. @, U, w) ~+ g) E法。
- V& ?2 e* d0 _2 E5 r) D2. 给出算法的时间空间复杂度。
) X: J6 T' n2 ]3. 证明你的算法。（非常重要）
三、系统设计题（35分）
1 Z6 w) ]4 W: i; H/ Y8 q6 i1 [$ d在一个有1000万用户的系统中，设计一个推送(feed)系统。以下是一些预定义概
念
- }! D0 A/ K  n, T7 y) S7 R1、用户：在这个系统中，每个用户用一个递增的unsigned int来表示user id(简
写为uid)；则uid的范围是从1到1000万的正整数。
8 U3 n% }8 v) y3 \  r9 A2 g2、好友：用户之间可以形成好友关系，好友是双向的；比如说uid为3和uid为4的
两个用户可以互为好友。每个用户好友的上限是500个；用户之间的好友关系可以
' B: x( a$ g5 y9 q2 {% G+ H被解除
3、活动：每个用户只能发文章；文章可以被作者删除，其他人不能删除非自己发
表的文章；每篇文章通过一个blogid表示。
4、feed：我们希望，每个用户可以看到他所有好友的活动列表，在这个简化的系
% z/ y3 I6 Y. s" f- j3 \0 V统中就是所有好友的文章更新列表。
5、访问量要求：所有feed访问量每天在1亿量级；所有的blogid增加量每天在百
万量级。
6 ~- u0 m  L: n! C* C题目：请在以上限制条件下，设计一个高效的feed访问系统。
: f$ F0 N% F0 f" C* \6 T: C要求：
+ @' j8 t0 o: N7 N$ F$ b' p( s1、能够尽快的返回每个用户的好友feed列表，每个用户可以最多保留1000条feed
4 p- k4 z8 L. p% f* r% G+ Z: h7 h$ H；feed的展现按照时间倒排序，最新的在最前面
9 i6 d* J! y& T& D2、用户删除某篇文章后，被推出去的feed需要及时消失。即每个用户看到的好友
feed都是未被删除的
3、尽可能高效。
  z. _$ u. v/ P2 b, W( B
Zz
- k" a/ g2 F* ]信息来自:阿凡提求职社区
——
百度历年实习生招聘真题
http://bbs.aftjob.com/thread-606504-1-1.html
2010年百度实习笔试真题（全套，2010年5月）
3 b) O/ X# X% _http://bbs.aftjob.com/thread-606500-1-1.html
2009年百度实习笔试真题
http://bbs.aftjob.com/thread-114579-1-1.html
1 @; q. l; u% \6 O* |7 |百度这三年实习招聘必考的题目
http://bbs.aftjob.com/thread-606503-1-1.html
百度历年校园招聘笔试题
* B0 r- ?% _. Q0 C. Bhttp://bbs.aftjob.com/thread-417000-1-1.html
" k+ g( j& M: l7 e& K9 X——
面试时间：5月8日开始
( S  U: H2 g# i/ b% {, y3 e工作人员电话通知笔试通过的同学到指定地点进行现场面试。

黄俊晓

顶一下