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

aftyingjiesheng

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


- O# N1 R( E4 D) D2009百度笔试题Zz

! ^% j# \  _9 u0 `一、编程题（30分）
1 |2 o8 W% t! m! m输入：N（整数）
输入：数据文件A.txt，不超过6条记录，字符串长度不超过15个字节
) W5 J) }9 s$ N5 J8 \  w文件格式如下：
字符串\t数字\n
7 P7 x# h5 b. E  K
& e0 B( s' k6 Z5 I* N. S说明：
) D3 l- k# P' e( F每行为1条记录；字符串中不含有\t。
数字描述的是该字符串的出现概率，小于等于100的整数。
多条记录的出现概率之和为100，如果A.txt不满足该条件，程序则退出；
如果文件格式错误，程序也退出。
0 w6 e' H) V/ X) P/ B; Y
要求：
1 [5 r! S. O- _! r/ K* Z编写一个程序，输入为N（正整数），读入文件A.txt，按照字符串出现概率随机

地输出字符串，输出N条记录

5 q6 H. Y, E9 K* b例如：
输入文件A.txt
abc\t20
; B! t4 M+ E2 t" t  \a\t30
de\t50
输入为：10

即 abc有20%的概率输出，a有30%的概率输出，de有50%的概率输出，输出10条记

2 M% X7 ?8 i" ?3 v' e7 r( Q录
% T4 L4 n0 B: [: K5 ^以下为一次输出的结果,多次输出的结果可能不相同。
abc
3 Y5 d/ G# J, O; d+ G5 a" P( ta
de
de
abc
de
a
de
) I/ G, e  C; Q# m# W; Ba
de

二、算法题（35分）
- [8 o2 [$ C( P; d( z题目描述：
* Z( S3 }6 l: M4 I2 R- d9 N( L0 K设有n个正整数，将它们联接成一排，组成一个最小的多位整数。

程序输入：n个数
. i4 B) V* `# @程序输出：联接成的多位数

例如：
n=2时，2个整数32，321连接成的最小整数为：32132，
n=4时，4个整数55，31，312, 33 联接成的最小整数为：312313355
' q- Z7 Z5 T$ `- d, e/ [
[题目要求]
$ f: v* F6 c2 D& h8 a/ e+ W/ `9 Q1. 给出伪代码即可，请给出对应的文字说明，并使用上面给出的例子试验你的算
! C, W0 ]0 _# G$ z  ^" M
法。
; M. N; u4 g( c" G5 E+ f- p8 T2. 给出算法的时间空间复杂度。
7 S4 m" w6 M; j- O" `: d6 ]3. 证明你的算法。（非常重要）
) u, Q: y+ h+ l8 f
6 C* L' \# n7 t' z7 s三、系统设计题（35分）
3 n. [4 f2 T5 C; t7 ]  I在一个有1000万用户的系统中，设计一个推送(feed)系统。以下是一些预定义概
+ d$ h$ ~/ x% t" n
念
1、用户：在这个系统中，每个用户用一个递增的unsigned int来表示user id(简
% t# X, V* C* G7 P; {+ A/ w. ^
写为uid)；则uid的范围是从1到1000万的正整数。
2 u  a$ s2 U  S! f2、好友：用户之间可以形成好友关系，好友是双向的；比如说uid为3和uid为4的

* M0 ^+ j4 }* _. O* J% s' a两个用户可以互为好友。每个用户好友的上限是500个；用户之间的好友关系可以

( t0 v# _# J; C5 S1 m$ l/ I被解除
4 s( ]' Z8 E4 Y$ n3、活动：每个用户只能发文章；文章可以被作者删除，其他人不能删除非自己发
4 S* {* D& m  Y5 W7 n
. J& ~1 N3 y# {4 L4 }" l. n表的文章；每篇文章通过一个blogid表示。
& J* i5 o! Z1 L4、feed：我们希望，每个用户可以看到他所有好友的活动列表，在这个简化的系
1 [7 m+ g3 F' i
统中就是所有好友的文章更新列表。
. k( a+ p& @8 k! f8 o4 T6 o/ z5、访问量要求：所有feed访问量每天在1亿量级；所有的blogid增加量每天在百

万量级。

% i8 W- i  r1 F  @5 \题目：请在以上限制条件下，设计一个高效的feed访问系统。
4 d0 J/ d1 J% b# Z3 a7 h' t1 B
要求：
1、能够尽快的返回每个用户的好友feed列表，每个用户可以最多保留1000条feed

；feed的展现按照时间倒排序，最新的在最前面
2 T/ {* a: o4 Z: A  X' `4 e9 p2、用户删除某篇文章后，被推出去的feed需要及时消失。即每个用户看到的好友
" J& S8 O9 n. R7 u
: `9 g& t9 ]( A% B/ T3 f$ A  \feed都是未被删除的
: T: _' ~3 n! v* `' d3、尽可能高效。
/ j* X6 A# ^8 K. N9 W( W( [+ i

7 ~; e7 ]% s0 ]7 ^/ R1 BZz

: g% W6 F6 ^3 N; r8 O! M2 x& p
2 f% o7 [  b( Q! O——
百度历年校园招聘笔试题（2005-2009年）
8 ^9 K/ C( m1 i9 dhttp://www.aftjob.com/bbs/thread-417000-1-1.html

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

4 A" ?0 Q2 p- d7 Z' E; M2006百度在线笔试题及答案
! J/ e! }6 h) |" {2 k9 Y+ u; M/ Zhttp://www.aftjob.com/bbs/thread-263888-1-1.html

- L6 w) r( g/ ~/ s百度在线笔试分享
9 }3 h5 t1 A! d  s6 E) Ehttp://www.aftjob.com/bbs/thread-164108-1-1.html

$ j3 _, S6 }8 f+ |- Ubaidu笔试
' \2 b# T' n3 r7 @3 yhttp://www.aftjob.com/bbs/thread-31644-1-1.html

百度笔试题ZZ
  [" h+ d( ~4 ~. M& Zhttp://www.aftjob.com/bbs/thread-170475-1-1.html
( G/ l% |  |$ X0 j; t& Q# b( S
6 Y, x- W' T( L& D& \* v! C& a3 j) ~zt 百度非技术笔试题
http://www.aftjob.com/bbs/thread-31656-1-1.html
0 o& M* {  v1 X1 Y5 ^
百度川大站笔试题 Zz
http://www.aftjob.com/bbs/thread-109752-1-1.html
: a/ E0 v0 N$ H& |: e+ x
! [! d" ~6 H& u# |……

查看名企2012校园招聘最新进度，请关注阿凡提求职公共日历：http://www.aftjob.com/home.php?mod=space&do=calendar
2 q$ B3 E3 f2 P8 l2 v百度历年校园招聘笔试题：http://bbs.aftjob.com/thread-417000-1-1.html
4 v* G7 o0 K! j0 n. ]3 M* |3 H百度历年校园招聘笔试题：http://bbs.aftjob.com/thread-417000-1-1.html
2012腾讯求职手册:http://bbs.aftjob.com/thread-608477-1-1.html
2012百度求职手册:http://bbs.aftjob.com/thread-608484-1-1.html
3 f- d8 @; [! u/ o* {8 k2012阿凡提求职手册——IT行业篇 :http://bbs.aftjob.com/thread-607158-1-1.html