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

aftyingjiesheng

百度（Baidu）校园招聘笔试题
8 w2 z2 Z* t4 b0 ~7 P3 N
' Q4 A! P2 Q3 C
2009百度笔试题Zz
! G- Z+ e! j& q0 W, @; S
一、编程题（30分）
. ~3 \# W$ u6 Z& k- B5 X输入：N（整数）
输入：数据文件A.txt，不超过6条记录，字符串长度不超过15个字节
3 C. R7 Z4 J* u- G2 U( F文件格式如下：
字符串\t数字\n
8 ?7 t; t0 o7 f, Q+ X9 U! l
说明：
' ]+ r1 d9 y8 M每行为1条记录；字符串中不含有\t。
数字描述的是该字符串的出现概率，小于等于100的整数。
+ K+ ?& H$ B# j, q多条记录的出现概率之和为100，如果A.txt不满足该条件，程序则退出；
" ?8 u4 }+ i$ h1 R+ j如果文件格式错误，程序也退出。

要求：
2 t# X2 F! r1 {" {编写一个程序，输入为N（正整数），读入文件A.txt，按照字符串出现概率随机
! c# R! Q2 j& I! N! Y2 [- @6 f
  }1 j1 Z4 p  W" R地输出字符串，输出N条记录
; Q0 J, F* W6 a& M! b, ~7 f( c$ p
/ }6 J' M* Q* W3 ?% c) Q例如：
输入文件A.txt
  m- {9 p* n/ y# c: Zabc\t20
a\t30
. R. x0 {$ U  ?( Mde\t50
输入为：10
# g7 W0 e3 X" {
4 C/ n* Q4 \8 S, v2 f即 abc有20%的概率输出，a有30%的概率输出，de有50%的概率输出，输出10条记
9 m0 R. Z0 v  g0 k0 E' M
录
& ^. d/ q7 Y* G/ x+ c  _3 `! Y, j4 c以下为一次输出的结果,多次输出的结果可能不相同。
abc
a
de
de
+ D% U8 |/ S8 k( g- ]2 W6 Gabc
de
a
de
* K5 a3 Z4 ?2 V5 v3 Ka
de

2 K- d6 W/ ]( f5 W二、算法题（35分）
题目描述：
$ s6 y* P3 D7 Q. G. D1 ^( n( b2 i设有n个正整数，将它们联接成一排，组成一个最小的多位整数。
. s% {$ m+ T& ~. T) l
- k) w) t7 `% g/ Z- ^& D程序输入：n个数
+ K" L# ^* d) t, n9 h程序输出：联接成的多位数

! C: \' L( U2 J; b0 J2 J例如：
n=2时，2个整数32，321连接成的最小整数为：32132，
" {$ _4 i: ^# t: e) on=4时，4个整数55，31，312, 33 联接成的最小整数为：312313355

[题目要求]
: ]  k* T! Z" K- Y! ^) A4 _3 l7 a1. 给出伪代码即可，请给出对应的文字说明，并使用上面给出的例子试验你的算

$ Z& v& k* D  b/ H: Y( b6 g3 d法。
/ Y8 X, M) O+ K6 Y* M2. 给出算法的时间空间复杂度。
2 G7 }" Q' d7 G; e- J1 y, b3. 证明你的算法。（非常重要）

; {' w2 _! b4 @. l三、系统设计题（35分）
) X- a  O' \: u2 S在一个有1000万用户的系统中，设计一个推送(feed)系统。以下是一些预定义概
; J7 P  r6 r7 b$ a
念
' ^2 X5 y5 T& j1、用户：在这个系统中，每个用户用一个递增的unsigned int来表示user id(简

写为uid)；则uid的范围是从1到1000万的正整数。
7 O/ @$ s, ]; ?0 ?& Q- Z6 m- }2、好友：用户之间可以形成好友关系，好友是双向的；比如说uid为3和uid为4的
- u4 P0 B3 l, p( G  @7 w
两个用户可以互为好友。每个用户好友的上限是500个；用户之间的好友关系可以
" |: b1 X9 q( q0 u+ f
被解除
3、活动：每个用户只能发文章；文章可以被作者删除，其他人不能删除非自己发

表的文章；每篇文章通过一个blogid表示。
4、feed：我们希望，每个用户可以看到他所有好友的活动列表，在这个简化的系

0 N- O& t& x9 i& G$ v统中就是所有好友的文章更新列表。
! u( _  `! l+ S% X5、访问量要求：所有feed访问量每天在1亿量级；所有的blogid增加量每天在百

万量级。

题目：请在以上限制条件下，设计一个高效的feed访问系统。
" B3 u& C3 f: v! L. V
3 I( g% H  O+ O6 ^0 v要求：
1、能够尽快的返回每个用户的好友feed列表，每个用户可以最多保留1000条feed
, O- T: E2 q; i0 J, P
；feed的展现按照时间倒排序，最新的在最前面
$ \% ?3 t" ~( o0 A- c' O5 n! Z' X2、用户删除某篇文章后，被推出去的feed需要及时消失。即每个用户看到的好友

feed都是未被删除的
6 y$ d$ z" ^5 s% D% s7 H8 ?3、尽可能高效。
) c, P: K3 ]5 X) U/ p$ A( o
0 a: F/ I- D/ }# D" }3 v; a% g* U
Zz
) A' D6 \, i3 n! M/ U

——
  z1 @' e1 z* V  V5 @* R. ]$ \3 u百度历年校园招聘笔试题（2005-2009年）
http://www.aftjob.com/bbs/thread-417000-1-1.html
( n* A7 O. L' q2 R
百度笔经大全
1 B: U0 i' k  U8 g! e# Vhttp://www.aftjob.com/bbs/thread-263898-1-1.html
' f3 v8 B8 S7 v/ A1 o
9 y9 E; D* H  _8 S- g: Y- u2006百度在线笔试题及答案
4 N7 R) W/ z: H9 j. a4 ^  c6 Ghttp://www.aftjob.com/bbs/thread-263888-1-1.html

百度在线笔试分享
http://www.aftjob.com/bbs/thread-164108-1-1.html
. q  Z3 a' ~- \2 D
7 O, z0 m% X; ^. v+ ?: _5 }1 V' Abaidu笔试
& i+ M  K! t0 H4 R* S/ B' H6 Mhttp://www.aftjob.com/bbs/thread-31644-1-1.html
% E& h+ `6 b$ R# Y; e
百度笔试题ZZ
http://www.aftjob.com/bbs/thread-170475-1-1.html
/ Z" U6 q9 C2 q3 U
zt 百度非技术笔试题
" h1 _' l1 i: Jhttp://www.aftjob.com/bbs/thread-31656-1-1.html
* k7 o3 T- ]6 r( y# ?; U
" |/ z8 \8 f1 N+ @) {5 W; K# M百度川大站笔试题 Zz
http://www.aftjob.com/bbs/thread-109752-1-1.html
% }* {* w3 [- M' c* E9 S( k
0 X5 [( _( V2 i6 X……

查看名企2012校园招聘最新进度，请关注阿凡提求职公共日历：http://www.aftjob.com/home.php?mod=space&do=calendar
7 D2 r) ^2 y9 f2 l, }* `百度历年校园招聘笔试题：http://bbs.aftjob.com/thread-417000-1-1.html
# i" `1 ]% t& g% J$ Q# o百度历年校园招聘笔试题：http://bbs.aftjob.com/thread-417000-1-1.html
2012腾讯求职手册:http://bbs.aftjob.com/thread-608477-1-1.html
$ C" V' Q" {& y* U3 X3 U, T1 s8 N- t; k2012百度求职手册:http://bbs.aftjob.com/thread-608484-1-1.html
0 C6 g  i; F: Q0 Y( }4 `! e2012阿凡提求职手册——IT行业篇 :http://bbs.aftjob.com/thread-607158-1-1.html