2009百度实习笔试题

aftyingjiesheng

2009百度实习笔试题
: p4 k" `3 L9 D! }
0 l: ^, ]( S. v0 _8 k! `7 q' [

  C* x, U3 }1 j/ U$ Q6 _+ Z4 r
8 P2 L- d* f% c# r$ ]5 [/ |一、编程题（30分）
( `0 F6 ~' [* D9 E+ n输入：N（整数）
输入：数据文件A.txt，不超过6条记录，字符串长度不超过15个字节
文件格式如下：
字符串\t数字\n

说明：
' W7 G% E" v3 M" P1 O4 P9 R每行为1条记录；字符串中不含有\t。
8 U' p! [7 n4 ]0 U$ N数字描述的是该字符串的出现概率，小于等于100的整数。
; h" q/ j, u$ _多条记录的出现概率之和为100，如果A.txt不满足该条件，程序则退出；
如果文件格式错误，程序也退出。

要求：
编写一个程序，输入为N（正整数），读入文件A.txt，按照字符串出现概率随机
# T7 G$ O# k' b6 @' E
& n  k! [6 t8 H) z地输出字符串，输出N条记录

例如：
2 x# u. T: J- F5 {- Y- Z8 e" l输入文件A.txt
abc\t20
a\t30
de\t50
3 ^# ~/ H2 \; }7 z输入为：10
2 v* T' V# H5 O" p2 N- p
3 \* T  C6 j4 U1 B- j- m: b" W, d$ I即 abc有20%的概率输出，a有30%的概率输出，de有50%的概率输出，输出10条记

录
以下为一次输出的结果,多次输出的结果可能不相同。
* q6 W9 A! @, I* S2 nabc
/ w2 @2 x; e/ {- `+ ta
de
de
% B6 T5 e) B. y/ O4 O9 \$ q  O- ^/ Rabc
de
a
de
3 H! m* G% l8 `/ Ua
de

二、算法题（35分）
题目描述：
. U7 H& {3 _9 a( a# q7 B设有n个正整数，将它们联接成一排，组成一个最小的多位整数。
/ l1 K3 d! F, ]% K" c6 l
程序输入：n个数
! K3 E$ n5 T+ C- l4 N程序输出：联接成的多位数

例如：
n=2时，2个整数32，321连接成的最小整数为：32132，
n=4时，4个整数55，31，312, 33 联接成的最小整数为：312313355

[题目要求]
1. 给出伪代码即可，请给出对应的文字说明，并使用上面给出的例子试验你的算
+ {- i5 D1 N* q! X- {2 {
法。
2. 给出算法的时间空间复杂度。
3. 证明你的算法。（非常重要）

. [. x* f. H  A: Y! M! O三、系统设计题（35分）
在一个有1000万用户的系统中，设计一个推送(feed)系统。以下是一些预定义概

. C- R7 n+ X* ~  g! i0 B$ G念
1、用户：在这个系统中，每个用户用一个递增的unsigned int来表示user id(简
" Y# O: G& t( C' R, N- s
5 s2 Y' _/ S2 T6 y& w3 r1 A写为uid)；则uid的范围是从1到1000万的正整数。
; k" z! ?3 Y! H: H9 j2、好友：用户之间可以形成好友关系，好友是双向的；比如说uid为3和uid为4的

两个用户可以互为好友。每个用户好友的上限是500个；用户之间的好友关系可以
9 _7 v, j9 v' N. V3 ]
被解除
2 r. n3 X1 S3 M1 O. O3、活动：每个用户只能发文章；文章可以被作者删除，其他人不能删除非自己发
6 V9 C6 F3 `7 r. B
表的文章；每篇文章通过一个blogid表示。
4、feed：我们希望，每个用户可以看到他所有好友的活动列表，在这个简化的系

% ~, M' d! K/ S统中就是所有好友的文章更新列表。
5、访问量要求：所有feed访问量每天在1亿量级；所有的blogid增加量每天在百

9 g/ V+ P" t1 y5 P/ K. m) ?万量级。

4 S$ h: n* g+ ^2 _1 w& G题目：请在以上限制条件下，设计一个高效的feed访问系统。
, u. y& B) O. b% N' x  h  f
要求：
1、能够尽快的返回每个用户的好友feed列表，每个用户可以最多保留1000条feed
4 ~. F5 d  h# ~, Y
9 P4 V8 }2 V+ ?' j. p& _  n. b；feed的展现按照时间倒排序，最新的在最前面
8 u: b9 {9 M* d& Y2、用户删除某篇文章后，被推出去的feed需要及时消失。即每个用户看到的好友
" x9 `2 V. T) S3 f8 F
% h5 Y* O7 _; V8 s7 r; ^feed都是未被删除的
3、尽可能高效。

百度历年校园招聘笔试题：http://bbs.aftjob.com/thread-417000-1-1.html
% f; F9 j0 `, W9 z百度历年实习生招聘真题：http://bbs.aftjob.com/thread-606504-1-1.html
百度2010实习生笔试2套：http://bbs.aftjob.com/thread-610484-1-1.html
百度求职俱乐部：http://bbs.aftjob.com/group-4-1.html