百度（Baidu）校园招聘笔试题

aftyingjiesheng

百度（Baidu）校园招聘笔试题


+ _& k3 q( N3 N6 C- M  [2009百度笔试题Zz

一、编程题（30分）
0 i9 W" N% i, b2 Y, Y1 \输入：N（整数）
输入：数据文件A.txt，不超过6条记录，字符串长度不超过15个字节
5 t, G, }! c8 h- D6 \文件格式如下：
字符串\t数字\n

0 Z8 V! w: h/ Z! ^说明：
每行为1条记录；字符串中不含有\t。
1 s( E, C  q2 ?& u* F7 y数字描述的是该字符串的出现概率，小于等于100的整数。
4 T# i+ d  g5 X6 p0 z4 e5 m4 }多条记录的出现概率之和为100，如果A.txt不满足该条件，程序则退出；
2 B, A& ]4 p% K2 l1 }) ?% a! c7 J' y如果文件格式错误，程序也退出。

/ T6 L! j2 X* n9 C1 o9 R$ v要求：
编写一个程序，输入为N（正整数），读入文件A.txt，按照字符串出现概率随机
3 t/ \% i* ?$ F5 k* k- {
4 w2 u6 K- `* n) a) K4 e地输出字符串，输出N条记录
! S$ F1 x) g4 s7 x" S% K8 L/ l% i
  [1 W, f2 s, ~- D例如：
输入文件A.txt
# F$ P, ~( F; x6 Iabc\t20
a\t30
de\t50
输入为：10

& J% W! w  g* i& p* a) m即 abc有20%的概率输出，a有30%的概率输出，de有50%的概率输出，输出10条记
7 q9 ~0 ^# W! k. b
$ m( [3 `! R$ Z+ F8 c/ g& D6 v录
以下为一次输出的结果,多次输出的结果可能不相同。
+ s" v8 d9 H8 C/ x9 m. J9 F8 oabc
a
6 t$ N! n4 D6 u8 n1 S4 Zde
8 I3 A- o1 E9 G. o; j. t$ q* z+ Cde
0 R. S* D7 d2 l& r/ \+ babc
$ H' [. H4 J. n# e7 S2 y$ Y6 \de
, h7 e. L* ]+ ua
de
a
' {; J8 ?! _. N' a7 I, {3 q& Qde
2 X7 w$ h6 D3 O9 j
二、算法题（35分）
题目描述：
' n2 ~% W. u6 A& f设有n个正整数，将它们联接成一排，组成一个最小的多位整数。

程序输入：n个数
程序输出：联接成的多位数

% ?. P: x2 r- Z/ r+ r4 n3 v( l例如：
6 ~( B% s+ i1 L2 h9 l! mn=2时，2个整数32，321连接成的最小整数为：32132，
# U; l; \  ]% S3 ^- S, S& `n=4时，4个整数55，31，312, 33 联接成的最小整数为：312313355
5 o/ _$ F9 h, s3 [- L8 F- U
2 r- W9 h; i8 Z6 ^[题目要求]
/ r! V* }9 R( t) {  c' T8 p1. 给出伪代码即可，请给出对应的文字说明，并使用上面给出的例子试验你的算
) M: L, d0 a/ o3 _2 X; p: r1 [
法。
2. 给出算法的时间空间复杂度。
( [8 w( c2 w( H  Y  ~' Z! x  ^; K3. 证明你的算法。（非常重要）
9 L% L: T. [* n
) Y7 p* Y1 `, K4 ~( A1 `三、系统设计题（35分）
在一个有1000万用户的系统中，设计一个推送(feed)系统。以下是一些预定义概
; v5 @2 Q2 B* E( h- K+ y
$ X! o* d8 l8 I+ V& a! y/ {$ D念
1、用户：在这个系统中，每个用户用一个递增的unsigned int来表示user id(简
9 p+ B% ?2 y0 z* F
9 q: t# a, a) R写为uid)；则uid的范围是从1到1000万的正整数。
8 X6 `8 c: v' u" C2、好友：用户之间可以形成好友关系，好友是双向的；比如说uid为3和uid为4的

- F5 S" a# {1 P4 H两个用户可以互为好友。每个用户好友的上限是500个；用户之间的好友关系可以

被解除
+ V5 u, C9 X) t$ x' P3、活动：每个用户只能发文章；文章可以被作者删除，其他人不能删除非自己发
0 v. h" d& t0 y' S2 J
表的文章；每篇文章通过一个blogid表示。
4、feed：我们希望，每个用户可以看到他所有好友的活动列表，在这个简化的系

统中就是所有好友的文章更新列表。
4 a# Z' a9 z) Z0 K0 |( X2 b1 d5、访问量要求：所有feed访问量每天在1亿量级；所有的blogid增加量每天在百

+ s- C5 F0 W, z  q  r万量级。
" _7 C, Q9 ]6 {; Z) [% V% T$ G
题目：请在以上限制条件下，设计一个高效的feed访问系统。

要求：
1、能够尽快的返回每个用户的好友feed列表，每个用户可以最多保留1000条feed
" e! m: b* K' X. u0 k
& G9 P! z+ K3 W- F$ ^; Q；feed的展现按照时间倒排序，最新的在最前面
" M8 Z1 w" @9 [9 o1 x; [- \  [2、用户删除某篇文章后，被推出去的feed需要及时消失。即每个用户看到的好友
, C  h' u" \3 f/ c2 S. U
feed都是未被删除的
3、尽可能高效。
. X+ s7 c0 i. E: z0 E

Zz

' V+ ?7 n8 K' k& y
——
' U) H3 o8 [9 b4 s3 {, F+ T百度历年校园招聘笔试题（2005-2009年）
* W4 g" U: g# q' Y# I" nhttp://www.aftjob.com/bbs/thread-417000-1-1.html

百度笔经大全
http://www.aftjob.com/bbs/thread-263898-1-1.html

2006百度在线笔试题及答案
# i5 G/ P1 G) y2 ]4 Z' Lhttp://www.aftjob.com/bbs/thread-263888-1-1.html

( t1 i, K7 u; Q& b百度在线笔试分享
http://www.aftjob.com/bbs/thread-164108-1-1.html

0 r' ~8 C! X; e5 q: `/ u0 Zbaidu笔试
% |9 d& w. {$ ?3 h5 khttp://www.aftjob.com/bbs/thread-31644-1-1.html

# t% Z; P* b$ u百度笔试题ZZ
6 X$ l8 V1 r+ y1 Lhttp://www.aftjob.com/bbs/thread-170475-1-1.html
% f- ?$ T' S( M- s( Q2 v
zt 百度非技术笔试题
http://www.aftjob.com/bbs/thread-31656-1-1.html
% g1 S& I9 Q0 L* G
! J" k1 q' r  f百度川大站笔试题 Zz
& r/ g. g; u+ X7 \: ^+ \http://www.aftjob.com/bbs/thread-109752-1-1.html

……
( I, }0 N6 R7 r# I5 k% o. ^8 c
9 j" }9 p, J) a: W( Q' q查看名企2012校园招聘最新进度，请关注阿凡提求职公共日历：http://www.aftjob.com/home.php?mod=space&do=calendar
百度历年校园招聘笔试题：http://bbs.aftjob.com/thread-417000-1-1.html
1 j, G7 }7 M% u( c; w百度历年校园招聘笔试题：http://bbs.aftjob.com/thread-417000-1-1.html
2012腾讯求职手册:http://bbs.aftjob.com/thread-608477-1-1.html
4 {. }  R2 ?: t0 G2012百度求职手册:http://bbs.aftjob.com/thread-608484-1-1.html
" H* H9 }3 z/ i8 `, `2012阿凡提求职手册——IT行业篇 :http://bbs.aftjob.com/thread-607158-1-1.html