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

aftyingjiesheng

百度（Baidu）校园招聘笔试题
9 N9 V  k& E" x5 ?; T

2009百度笔试题Zz
9 p/ f4 w2 ?& x. |" e$ R5 v
一、编程题（30分）
2 S; V: K7 R1 t& V& O输入：N（整数）
输入：数据文件A.txt，不超过6条记录，字符串长度不超过15个字节
文件格式如下：
4 A+ c/ u8 Y$ ]9 Q& i字符串\t数字\n

/ N2 H3 M$ _1 {说明：
5 R7 v: E4 V5 ^% A. i每行为1条记录；字符串中不含有\t。
* b1 L) F6 c" \0 A2 u数字描述的是该字符串的出现概率，小于等于100的整数。
! d$ [) N1 _6 J; k' D  S多条记录的出现概率之和为100，如果A.txt不满足该条件，程序则退出；
如果文件格式错误，程序也退出。
- Q) h. u3 h0 }
4 M( R& ]; |' |( j; O  e4 v要求：
7 Q0 c1 p* v4 L, t# \" _) B1 D编写一个程序，输入为N（正整数），读入文件A.txt，按照字符串出现概率随机
7 \( v, d! U7 n& ]6 ^0 n2 E7 A4 ]. `
$ u8 z) q3 Y: H- G地输出字符串，输出N条记录
- M" ~" }  X; P. P& z) i/ {
例如：
" ^/ V- R, B6 s输入文件A.txt
8 ]' l' M/ i' c5 G  I3 C" a2 aabc\t20
a\t30
de\t50
+ H9 |# b. c3 S输入为：10
, g# J3 c! T2 s3 _: k) L
) g. C. E* d1 Y即 abc有20%的概率输出，a有30%的概率输出，de有50%的概率输出，输出10条记

录
( @! k% b% R+ z& y以下为一次输出的结果,多次输出的结果可能不相同。
abc
a
de
% n, X; \$ s% A$ d& c% L' [) ]' yde
abc
; ~( G' Q% u# Sde
' F7 x* b- Z+ A: Qa
de
# Q- s0 E9 Q" Ca
* J, ?  `6 u% Z# vde
6 j$ C9 K+ S8 K% R5 k, y
二、算法题（35分）
题目描述：
设有n个正整数，将它们联接成一排，组成一个最小的多位整数。
) i! y4 S5 t, H6 ?
程序输入：n个数
程序输出：联接成的多位数
/ ?- e. R2 [+ o; d9 A
例如：
) v" Q: A7 j2 P( K" [- m; en=2时，2个整数32，321连接成的最小整数为：32132，
- F2 J7 q' |+ }( ^5 I8 Xn=4时，4个整数55，31，312, 33 联接成的最小整数为：312313355
4 Z8 _: u0 v2 l+ _/ I
# e8 i& N. V6 C, V[题目要求]
2 s) w" D) ]8 {. z4 c1. 给出伪代码即可，请给出对应的文字说明，并使用上面给出的例子试验你的算

- |% B, m& x1 T. Q/ V法。
5 \9 S+ d, b# W0 Z! u5 C' ~  @2. 给出算法的时间空间复杂度。
3. 证明你的算法。（非常重要）
! U) h6 N" j+ Q" J& q
$ U( b: |6 t" G! K( X# y三、系统设计题（35分）
在一个有1000万用户的系统中，设计一个推送(feed)系统。以下是一些预定义概

( t& r4 t+ A* L! N: J: f念
1、用户：在这个系统中，每个用户用一个递增的unsigned int来表示user id(简

写为uid)；则uid的范围是从1到1000万的正整数。
) n* b1 R$ o2 J+ @" G6 t/ ]' W2、好友：用户之间可以形成好友关系，好友是双向的；比如说uid为3和uid为4的
7 y7 h7 a5 K7 r* R" E
两个用户可以互为好友。每个用户好友的上限是500个；用户之间的好友关系可以

被解除
$ O- @2 ~& o* D* A0 O7 h* _9 u3、活动：每个用户只能发文章；文章可以被作者删除，其他人不能删除非自己发
  M6 ~- {5 F- ^. h4 I
表的文章；每篇文章通过一个blogid表示。
1 }6 E2 O! e0 D! c. |- D8 i4、feed：我们希望，每个用户可以看到他所有好友的活动列表，在这个简化的系

统中就是所有好友的文章更新列表。
$ q8 A3 h$ p- w' Y0 }* h& S5、访问量要求：所有feed访问量每天在1亿量级；所有的blogid增加量每天在百

万量级。
: h9 r0 P0 u' e  D; \2 |3 f
题目：请在以上限制条件下，设计一个高效的feed访问系统。

( J5 X! n! a1 A" H+ z要求：
1、能够尽快的返回每个用户的好友feed列表，每个用户可以最多保留1000条feed

；feed的展现按照时间倒排序，最新的在最前面
4 C1 W. `1 E# v2、用户删除某篇文章后，被推出去的feed需要及时消失。即每个用户看到的好友
: N8 `7 Y/ [8 S+ B- @- A
9 _0 D$ Y& f/ x% f5 c; Sfeed都是未被删除的
7 w4 ]$ A' [; Z, ^3、尽可能高效。


" W+ e, S: W; ^* KZz


# g3 Z! C( M$ q, C# h0 f1 U——
% f8 z- S+ M, o0 ~1 _1 i百度历年校园招聘笔试题（2005-2009年）
http://www.aftjob.com/bbs/thread-417000-1-1.html
. u8 e4 m; K) K; ]" `0 L
百度笔经大全
http://www.aftjob.com/bbs/thread-263898-1-1.html

) ?9 c1 U" ?% N' G+ z4 D4 Q( y2006百度在线笔试题及答案
http://www.aftjob.com/bbs/thread-263888-1-1.html

百度在线笔试分享
http://www.aftjob.com/bbs/thread-164108-1-1.html

- P* l  F% Y, L% ^; Obaidu笔试
http://www.aftjob.com/bbs/thread-31644-1-1.html

4 u4 {/ P' K8 O9 n百度笔试题ZZ
http://www.aftjob.com/bbs/thread-170475-1-1.html
( z( i1 K: n; y2 s8 }  ~, A4 p% f
zt 百度非技术笔试题
4 W1 f2 ]5 F$ {: s8 R, T' R9 _http://www.aftjob.com/bbs/thread-31656-1-1.html
: c( I2 z' P! N. r& P
: z  K$ y# _# F3 r百度川大站笔试题 Zz
9 D# S! u) P9 X' Phttp://www.aftjob.com/bbs/thread-109752-1-1.html
6 t# O# k5 ~7 {- _3 l
……
; }; s; ]+ t# y+ A# j& r% f3 q. l
查看名企2012校园招聘最新进度，请关注阿凡提求职公共日历：http://www.aftjob.com/home.php?mod=space&do=calendar
百度历年校园招聘笔试题：http://bbs.aftjob.com/thread-417000-1-1.html
: {4 b" T% s( B百度历年校园招聘笔试题：http://bbs.aftjob.com/thread-417000-1-1.html
  ^( F* ~6 h  q0 T; e( Q2 }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