百度2011实习生招聘笔试题

aftyingjiesheng

百度2011实习生招聘笔试题
7 m: W/ A8 Y! [+ }4 e
笔试时间：5月7日


9 E% J7 a+ p% e1 E+ l& a1 |2009百度实习笔试题Zz

一、编程题（30分）
) o/ _9 i* r' z# E4 W/ p5 l输入：N（整数）
7 W% Y* i/ a7 }% G. ]' P输入：数据文件A.txt，不超过6条记录，字符串长度不超过15个字节
2 Z7 \# ^* R" D! E- a  J文件格式如下：
' G; W5 |# I. t7 k# @字符串\t数字\n
- Z+ U7 w  I8 ^8 S+ u. L说明：
# z( {. L5 N7 X1 x' o+ R( |, [4 f6 s% _每行为1条记录；字符串中不含有\t。
+ ^! o" C# ~: n) c2 z. t- x数字描述的是该字符串的出现概率，小于等于100的整数。
多条记录的出现概率之和为100，如果A.txt不满足该条件，程序则退出；
- F$ w2 D3 U+ [2 ?8 l& l# q1 [如果文件格式错误，程序也退出。
5 e: w9 u9 m, z# ^9 }" N要求：
编写一个程序，输入为N（正整数），读入文件A.txt，按照字符串出现概率随机
地输出字符串，输出N条记录
) n$ l& ]0 o& O! M9 E3 t例如：
输入文件A.txt
abc\t20
a\t30
de\t50
, S, p2 _0 a! j3 T/ n- n输入为：10
即 abc有20%的概率输出，a有30%的概率输出，de有50%的概率输出，输出10条记
录
% N2 C* i+ z  l以下为一次输出的结果,多次输出的结果可能不相同。
abc
a
de
* G0 A$ N5 I1 d5 |de
5 l1 I* p  X  v" w5 U5 n! Kabc
de
a
de
6 x+ w% C- Y$ o* w7 M3 t; @a
; ]3 l1 u: g, D. M6 f! O( qde
二、算法题（35分）
题目描述：
设有n个正整数，将它们联接成一排，组成一个最小的多位整数。
程序输入：n个数
. U; w6 J9 S" V0 w, J+ i2 a& t程序输出：联接成的多位数
例如：
0 D" |0 L- S0 V. J% ~n=2时，2个整数32，321连接成的最小整数为：32132，
# y5 ]1 V6 ?& l( en=4时，4个整数55，31，312, 33 联接成的最小整数为：312313355
% @1 C1 h1 C) Y) s8 X1 ?! Z6 Y[题目要求]
% @  K) K7 @9 f! T' e* j+ [1. 给出伪代码即可，请给出对应的文字说明，并使用上面给出的例子试验你的算
/ N, ^7 h7 C9 J, Q8 ^& @法。
2. 给出算法的时间空间复杂度。
3. 证明你的算法。（非常重要）
三、系统设计题（35分）
, n7 r1 O: q- `0 K( B3 U7 n在一个有1000万用户的系统中，设计一个推送(feed)系统。以下是一些预定义概
7 z. ^3 t3 f$ A, J" s念
" T( s9 K# J+ T! H5 X1、用户：在这个系统中，每个用户用一个递增的unsigned int来表示user id(简
写为uid)；则uid的范围是从1到1000万的正整数。
2、好友：用户之间可以形成好友关系，好友是双向的；比如说uid为3和uid为4的
* H$ ~* |3 T, }9 U: d两个用户可以互为好友。每个用户好友的上限是500个；用户之间的好友关系可以
9 `/ j. t0 X! A6 p7 D- ^1 @被解除
. ~  g( E2 y' q. o# I$ ]3、活动：每个用户只能发文章；文章可以被作者删除，其他人不能删除非自己发
. |; e# L4 A7 f8 ^表的文章；每篇文章通过一个blogid表示。
, l/ j- \6 ]5 P& J. Q+ P4、feed：我们希望，每个用户可以看到他所有好友的活动列表，在这个简化的系
统中就是所有好友的文章更新列表。
5、访问量要求：所有feed访问量每天在1亿量级；所有的blogid增加量每天在百
9 N' `2 I1 X" _万量级。
题目：请在以上限制条件下，设计一个高效的feed访问系统。
# q& y6 Q7 V1 R* B( @要求：
1、能够尽快的返回每个用户的好友feed列表，每个用户可以最多保留1000条feed
；feed的展现按照时间倒排序，最新的在最前面
2、用户删除某篇文章后，被推出去的feed需要及时消失。即每个用户看到的好友
4 i: H" D+ l1 a  T! }feed都是未被删除的
3、尽可能高效。

$ t$ w  m( [& P- T* c1 jZz
9 Q0 a' t, Y$ h( q9 L信息来自:阿凡提求职社区
——
百度历年实习生招聘真题
) k2 W* o5 e" O# S) u2 Khttp://bbs.aftjob.com/thread-606504-1-1.html
& R( D% w4 `: T7 \: S( T2010年百度实习笔试真题（全套，2010年5月）
4 a7 S4 G3 j( O9 w. f8 L! x+ N0 H  ohttp://bbs.aftjob.com/thread-606500-1-1.html
  o7 w6 l7 Z/ }7 _. a2009年百度实习笔试真题
. V; {( |8 ^# W6 phttp://bbs.aftjob.com/thread-114579-1-1.html
百度这三年实习招聘必考的题目
: E$ J/ U! ~$ @' c# S2 f) X" Ihttp://bbs.aftjob.com/thread-606503-1-1.html
百度历年校园招聘笔试题
http://bbs.aftjob.com/thread-417000-1-1.html
——
面试时间：5月8日开始
工作人员电话通知笔试通过的同学到指定地点进行现场面试。

黄俊晓

顶一下