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

aftyingjiesheng

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

/ W+ W9 ~$ h( U/ q# A5 a! M- f7 z
2009百度笔试题Zz

一、编程题（30分）
! a+ c5 @$ k  K1 f( _输入：N（整数）
" r# X. T- v% D+ j4 a! P( b. q4 |输入：数据文件A.txt，不超过6条记录，字符串长度不超过15个字节
" }( o+ ^% Y5 N4 P$ n5 S' O% D, j文件格式如下：
字符串\t数字\n
8 Q; K6 ]& V& m- t7 Y7 X! s
% ^8 T* P* x; [- K: b2 t说明：
+ D$ O, R9 n! e+ ]& v4 Q' w每行为1条记录；字符串中不含有\t。
; v" r% M+ L9 F数字描述的是该字符串的出现概率，小于等于100的整数。
多条记录的出现概率之和为100，如果A.txt不满足该条件，程序则退出；
- F. M; h( Z. M4 W4 s9 T* ~如果文件格式错误，程序也退出。

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

3 k5 \( W. b, ^4 q地输出字符串，输出N条记录

例如：
输入文件A.txt
abc\t20
/ k- z$ k" t( h6 Ja\t30
de\t50
输入为：10

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

9 P6 Y0 J  p$ C( s0 O8 {录
; P, z$ q( _* z4 u( f% h( V& `以下为一次输出的结果,多次输出的结果可能不相同。
- \2 X3 w% J  ?, ?6 }! Qabc
a
5 e( ]& }+ H' K; P; ^& g8 ~' |de
de
5 o8 ]! z( y0 X& nabc
, |: H7 X+ ^, N5 Y5 ]( a# f/ _5 w3 ade
a
6 u/ s5 P/ O$ z8 |- Dde
/ s7 o/ p4 l8 ja
de

二、算法题（35分）
8 ^: M( N9 m  I; X9 {+ p题目描述：
& p6 n, U, l. j# B# |设有n个正整数，将它们联接成一排，组成一个最小的多位整数。

程序输入：n个数
# }! J+ r/ k, N( e: C程序输出：联接成的多位数

2 L+ E7 ?5 z5 s  I* h1 W5 g例如：
& Z9 C' L4 [+ N4 v4 Ln=2时，2个整数32，321连接成的最小整数为：32132，
+ ?9 K' ]* ~8 bn=4时，4个整数55，31，312, 33 联接成的最小整数为：312313355
4 X) @& J' K0 y* \
[题目要求]
1. 给出伪代码即可，请给出对应的文字说明，并使用上面给出的例子试验你的算

+ }+ Z- J7 R) B: I' O法。
2. 给出算法的时间空间复杂度。
3. 证明你的算法。（非常重要）
+ k7 Q$ E4 X' R. W9 t/ S
2 c3 o! T: T7 f+ v7 k三、系统设计题（35分）
! U3 s" W2 K% C在一个有1000万用户的系统中，设计一个推送(feed)系统。以下是一些预定义概

% _$ b3 }/ e0 l. V' Q) X& d念
4 _( O. J' \9 O# e: y! k. m1、用户：在这个系统中，每个用户用一个递增的unsigned int来表示user id(简

写为uid)；则uid的范围是从1到1000万的正整数。
2、好友：用户之间可以形成好友关系，好友是双向的；比如说uid为3和uid为4的

1 x3 ?, z' |* b5 Y2 N两个用户可以互为好友。每个用户好友的上限是500个；用户之间的好友关系可以
8 |8 s9 |# j) ?! i8 \
) M- T8 V" h5 `* L" r! Z5 Q被解除
# ]9 c8 l+ g) E! E3、活动：每个用户只能发文章；文章可以被作者删除，其他人不能删除非自己发
  T, F* p5 y  n% P9 k# |
2 B) O1 ?9 y4 B. U! R8 t表的文章；每篇文章通过一个blogid表示。
$ j$ O3 R% H" K2 S4、feed：我们希望，每个用户可以看到他所有好友的活动列表，在这个简化的系
! b. j$ P2 P8 T% C, ~' N/ h! X
+ b  e! b4 {4 p, Q统中就是所有好友的文章更新列表。
5、访问量要求：所有feed访问量每天在1亿量级；所有的blogid增加量每天在百

0 w- n5 E# \9 s; D8 o$ |% k+ t万量级。

0 e& i* ^. D/ Q/ E' g% ^题目：请在以上限制条件下，设计一个高效的feed访问系统。

要求：
1、能够尽快的返回每个用户的好友feed列表，每个用户可以最多保留1000条feed
" q' l4 {( F& Y9 J0 f- V
5 s" c* B# w1 F. m) x；feed的展现按照时间倒排序，最新的在最前面
7 U" }( A$ v5 ^! m6 }2、用户删除某篇文章后，被推出去的feed需要及时消失。即每个用户看到的好友

feed都是未被删除的
7 B- ]7 r3 G7 x+ ]3、尽可能高效。
% t% f& \. C! @7 F& N/ p
- u; B" Z( E0 l/ q
Zz

7 }9 w- d; X( C+ M& q! |1 w
——
; j; j5 k! O% L8 V5 ^7 h百度历年校园招聘笔试题（2005-2009年）
6 a2 b( }; |, T7 \9 Nhttp://www.aftjob.com/bbs/thread-417000-1-1.html
( L  \8 O7 S$ }, m  c" p# {& U: ?
7 h6 J/ ?3 M! z& Q百度笔经大全
9 a& a8 _, S; P, ?; {) h) g2 @& u  Bhttp://www.aftjob.com/bbs/thread-263898-1-1.html
; Q: p5 v8 t% U$ L
' E$ ~. \% b3 Y" q2006百度在线笔试题及答案
! ^+ Q7 N, m/ q+ Ghttp://www.aftjob.com/bbs/thread-263888-1-1.html

百度在线笔试分享
1 i( x' a5 T1 Z0 G7 G% f) xhttp://www.aftjob.com/bbs/thread-164108-1-1.html

baidu笔试
8 O$ A4 G- B/ \  {$ W' [+ r( ~0 L' Bhttp://www.aftjob.com/bbs/thread-31644-1-1.html
" B, \! l7 |: a. T+ m1 M7 L1 s
; l. P( F! K: Q- k9 @2 r$ F百度笔试题ZZ
. R4 n  D1 a& P/ B( @http://www.aftjob.com/bbs/thread-170475-1-1.html

. U" G; g! x4 \7 ]" }2 [; u4 Q8 Hzt 百度非技术笔试题
6 l) k1 s  ]2 b- f) `$ l, }9 Yhttp://www.aftjob.com/bbs/thread-31656-1-1.html
" x: c, O  Q! g0 t1 x+ O' O! _) |
百度川大站笔试题 Zz
8 b6 D! W* Y1 I  X1 x" W+ qhttp://www.aftjob.com/bbs/thread-109752-1-1.html
: }9 t8 @! l0 w. M/ @
% @. J* G" c& C1 p* x……
% I4 I+ d! n2 U2 L
查看名企2012校园招聘最新进度，请关注阿凡提求职公共日历：http://www.aftjob.com/home.php?mod=space&do=calendar
, Q, A6 l4 o2 n( d1 e$ z百度历年校园招聘笔试题：http://bbs.aftjob.com/thread-417000-1-1.html
百度历年校园招聘笔试题：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
2012阿凡提求职手册——IT行业篇 :http://bbs.aftjob.com/thread-607158-1-1.html