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

aftyingjiesheng

百度（Baidu）校园招聘笔试题
* B2 z+ k0 `4 r! P0 v* ~2 w

2009百度笔试题Zz

3 i3 o3 [: I- k0 r  a一、编程题（30分）
6 p5 F$ x4 l% q+ T: t& M# t输入：N（整数）
( K" ]7 e; A3 T& X输入：数据文件A.txt，不超过6条记录，字符串长度不超过15个字节
* W8 m/ E( d/ T# u文件格式如下：
0 w" E1 b5 r/ D! j字符串\t数字\n

6 @" q$ Y, R" Q/ y2 l说明：
每行为1条记录；字符串中不含有\t。
数字描述的是该字符串的出现概率，小于等于100的整数。
' m/ m- e! h2 B, V2 H多条记录的出现概率之和为100，如果A.txt不满足该条件，程序则退出；
如果文件格式错误，程序也退出。

要求：
编写一个程序，输入为N（正整数），读入文件A.txt，按照字符串出现概率随机

地输出字符串，输出N条记录
! [# I! z. g: X& N% i8 w8 v
例如：
输入文件A.txt
( i7 V+ F7 R* Dabc\t20
a\t30
de\t50
+ g, I& `' ~  U  _! Q9 Q; ?  u9 R输入为：10
- s, p/ Q: ^2 n/ r0 _" J6 c3 q+ ^7 C
即 abc有20%的概率输出，a有30%的概率输出，de有50%的概率输出，输出10条记

) b* Y8 ?# t" V7 m录
' F# T3 K5 ?( {, w1 R7 H. l8 S9 F以下为一次输出的结果,多次输出的结果可能不相同。
' C! u6 N5 B3 l7 Oabc
a
de
de
+ C; k. C, I! m" w% eabc
de
a
6 A7 m9 ^# x  ]0 K8 o' ]. M. _de
a
de

二、算法题（35分）
! N- h6 R9 j1 o- ~题目描述：
设有n个正整数，将它们联接成一排，组成一个最小的多位整数。

0 J* u# u8 j# v4 h# S程序输入：n个数
5 O8 t2 r9 U) ^4 a: h; R程序输出：联接成的多位数

# X" D/ x" T! u3 ?  Y例如：
  j! }5 |, z6 R( p5 Pn=2时，2个整数32，321连接成的最小整数为：32132，
n=4时，4个整数55，31，312, 33 联接成的最小整数为：312313355

% v8 E9 B) \* X3 P% f! ][题目要求]
9 n( T; X4 F, n0 R$ ^* r3 s6 p1. 给出伪代码即可，请给出对应的文字说明，并使用上面给出的例子试验你的算
1 T* Q8 R0 H/ D$ {
法。
. I, \+ W* R. Z3 U# x$ ^! C2. 给出算法的时间空间复杂度。
3. 证明你的算法。（非常重要）
+ @  x8 P  o- k* A: j
三、系统设计题（35分）
在一个有1000万用户的系统中，设计一个推送(feed)系统。以下是一些预定义概

念
1、用户：在这个系统中，每个用户用一个递增的unsigned int来表示user id(简

写为uid)；则uid的范围是从1到1000万的正整数。
2、好友：用户之间可以形成好友关系，好友是双向的；比如说uid为3和uid为4的
% ?0 ]& }" d1 c
两个用户可以互为好友。每个用户好友的上限是500个；用户之间的好友关系可以
( \0 r9 A* n% U  B* p8 J
被解除
3、活动：每个用户只能发文章；文章可以被作者删除，其他人不能删除非自己发

- J) w) ?- E  N6 \& k表的文章；每篇文章通过一个blogid表示。
! l7 b5 I/ ]% I, J* J: U' g9 b4、feed：我们希望，每个用户可以看到他所有好友的活动列表，在这个简化的系
8 M# u- |$ r' y  ?1 z
统中就是所有好友的文章更新列表。
5、访问量要求：所有feed访问量每天在1亿量级；所有的blogid增加量每天在百
0 M* D, M2 Z& `) v5 {! e
万量级。
) g* `) U+ x6 C$ w. X3 }
题目：请在以上限制条件下，设计一个高效的feed访问系统。

要求：
1、能够尽快的返回每个用户的好友feed列表，每个用户可以最多保留1000条feed

. E) c$ C/ f- I7 i$ K8 r8 I! e；feed的展现按照时间倒排序，最新的在最前面
' C7 _; [6 q" O/ L& ~5 y2、用户删除某篇文章后，被推出去的feed需要及时消失。即每个用户看到的好友
0 o9 H2 {8 h8 ]8 M. \# U
6 {" B" ^' h3 h6 ]5 nfeed都是未被删除的
3、尽可能高效。


Zz
* R: w; I6 k5 y9 ]
! c, U/ V/ I2 R/ S2 m- y
7 L5 _4 Z# n7 c1 |$ X1 e. t2 V# ~! @——
" ^  L; G- r' R6 z百度历年校园招聘笔试题（2005-2009年）
: @8 A6 ~4 r& U$ s; u5 O6 G0 ?http://www.aftjob.com/bbs/thread-417000-1-1.html

百度笔经大全
http://www.aftjob.com/bbs/thread-263898-1-1.html
  m! v$ T5 q" B1 V. X! v
2006百度在线笔试题及答案
http://www.aftjob.com/bbs/thread-263888-1-1.html
% K5 F+ Q# n) c2 n) W  \& q
# J) n7 D! v, d$ `1 Q百度在线笔试分享
9 e4 ^* \5 P- T1 J$ e( O) g, b8 d2 {http://www.aftjob.com/bbs/thread-164108-1-1.html
5 l* `' Q3 m) W0 F: J) C, m
baidu笔试
http://www.aftjob.com/bbs/thread-31644-1-1.html

百度笔试题ZZ
http://www.aftjob.com/bbs/thread-170475-1-1.html

zt 百度非技术笔试题
http://www.aftjob.com/bbs/thread-31656-1-1.html
( B" L. C* i/ b; V
百度川大站笔试题 Zz
# D8 ]8 S7 D5 u/ }/ bhttp://www.aftjob.com/bbs/thread-109752-1-1.html
: q$ K* ^3 f* k# n: d" d
1 |' y9 s) J# u5 G; K……

查看名企2012校园招聘最新进度，请关注阿凡提求职公共日历：http://www.aftjob.com/home.php?mod=space&do=calendar
百度历年校园招聘笔试题：http://bbs.aftjob.com/thread-417000-1-1.html
7 e# H/ R: G' x" [. J百度历年校园招聘笔试题：http://bbs.aftjob.com/thread-417000-1-1.html
  k) n% Y& a; b5 l( w( q2012腾讯求职手册:http://bbs.aftjob.com/thread-608477-1-1.html
2012百度求职手册:http://bbs.aftjob.com/thread-608484-1-1.html
( G5 o2 y! `8 T1 }6 u, P2012阿凡提求职手册——IT行业篇 :http://bbs.aftjob.com/thread-607158-1-1.html