2009百度实习笔试题

aftyingjiesheng

2009百度实习笔试题



" K2 T' T6 ^4 j& x  I. {* |
" |3 J' r- u0 D! {一、编程题（30分）
) q, Y/ j- {1 G  p9 ~; y* ^输入：N（整数）
输入：数据文件A.txt，不超过6条记录，字符串长度不超过15个字节
- Q5 n; t$ u! ?& u文件格式如下：
字符串\t数字\n
7 k. h% @% c# `% _$ {& C" V
" b0 ?/ d; D- R# d说明：
4 k( y' {# R- i$ p. i每行为1条记录；字符串中不含有\t。
数字描述的是该字符串的出现概率，小于等于100的整数。
- F6 R: z0 Y9 `0 ~* P) z- t- a& x% }% ]多条记录的出现概率之和为100，如果A.txt不满足该条件，程序则退出；
如果文件格式错误，程序也退出。
# ]- I% M9 ]: F  W8 D! O
要求：
* T6 T% _9 M3 q编写一个程序，输入为N（正整数），读入文件A.txt，按照字符串出现概率随机

1 {& R$ M' U( u' r  u( ?地输出字符串，输出N条记录

例如：
6 V, u# }* ~0 Z5 V9 M8 x- x$ N9 }# R输入文件A.txt
abc\t20
a\t30
de\t50
' K" |+ d) F( m7 V2 n( C输入为：10
- \: \% w0 @! F. b2 b  h
即 abc有20%的概率输出，a有30%的概率输出，de有50%的概率输出，输出10条记
2 W( J( R' M1 |6 Y& G
录
, F! s. k  v+ K以下为一次输出的结果,多次输出的结果可能不相同。
2 U  N8 r4 b2 i2 J  \$ u* Tabc
a
de
de
( G4 m4 h5 q9 Q9 l% W0 W1 Habc
de
5 X1 l) W& U# F2 Fa
de
a
de
: u# ]0 L* d5 c' M$ `* v
5 L5 M$ v9 ^+ F, z, V二、算法题（35分）
题目描述：
9 j$ m1 }  U6 @  t4 Q+ C设有n个正整数，将它们联接成一排，组成一个最小的多位整数。
; d7 ]# @+ w- X" \! J* _
. r. J$ L! ^3 u* d0 o程序输入：n个数
; k. ^0 v; V6 E9 f程序输出：联接成的多位数

6 y) P% Y% |  A( b; `2 t! p7 \* q例如：
n=2时，2个整数32，321连接成的最小整数为：32132，
9 T) O9 N6 n6 en=4时，4个整数55，31，312, 33 联接成的最小整数为：312313355

; C+ X9 o* s/ b& b/ d6 k" o7 [[题目要求]
1. 给出伪代码即可，请给出对应的文字说明，并使用上面给出的例子试验你的算

法。
2. 给出算法的时间空间复杂度。
5 U+ V: I+ U, i1 }3. 证明你的算法。（非常重要）

三、系统设计题（35分）
* K. A9 h% v- d: W" A0 f在一个有1000万用户的系统中，设计一个推送(feed)系统。以下是一些预定义概
" `* Q. j* Z! I0 x
念
% f' i) @( s, r1、用户：在这个系统中，每个用户用一个递增的unsigned int来表示user id(简
, B% X" [# y' p, W1 p  Q6 J
写为uid)；则uid的范围是从1到1000万的正整数。
6 w8 p, J6 [8 `' j: f! D# R2、好友：用户之间可以形成好友关系，好友是双向的；比如说uid为3和uid为4的
* u. M, ], g& G- k5 X; M
/ T+ ^& p5 Q+ d6 D% m$ w1 C两个用户可以互为好友。每个用户好友的上限是500个；用户之间的好友关系可以

被解除
5 t; h0 Q7 R1 x1 D3、活动：每个用户只能发文章；文章可以被作者删除，其他人不能删除非自己发

表的文章；每篇文章通过一个blogid表示。
/ X. k9 Y7 x6 n- D' u/ h4、feed：我们希望，每个用户可以看到他所有好友的活动列表，在这个简化的系

统中就是所有好友的文章更新列表。
5、访问量要求：所有feed访问量每天在1亿量级；所有的blogid增加量每天在百
0 o( c) D$ H9 M5 R4 p( s9 ~# F3 p6 r
万量级。

题目：请在以上限制条件下，设计一个高效的feed访问系统。
" }; z. l2 U( Y* o' _! G2 }, q+ M
0 n; h# [5 g& k% Q& T要求：
1、能够尽快的返回每个用户的好友feed列表，每个用户可以最多保留1000条feed

；feed的展现按照时间倒排序，最新的在最前面
% `) o+ o) h3 V, F4 f2、用户删除某篇文章后，被推出去的feed需要及时消失。即每个用户看到的好友

$ @! x0 W( n$ C& H) Xfeed都是未被删除的
7 Q" S8 S% l- v( V3、尽可能高效。
5 S+ t3 @; X& @9 [& C
( R# D: e. n6 z: \百度历年校园招聘笔试题：http://bbs.aftjob.com/thread-417000-1-1.html
百度历年实习生招聘真题：http://bbs.aftjob.com/thread-606504-1-1.html
百度2010实习生笔试2套：http://bbs.aftjob.com/thread-610484-1-1.html
6 o( H2 K9 R* T" X3 x" l: W百度求职俱乐部：http://bbs.aftjob.com/group-4-1.html