2009百度实习笔试题

aftyingjiesheng

2009百度实习笔试题


; g. J  r& y6 }

/ w' k2 J7 R$ \一、编程题（30分）
% d( @/ d3 H/ A输入：N（整数）
0 k5 _0 \! ]$ |. M# `- C- P输入：数据文件A.txt，不超过6条记录，字符串长度不超过15个字节
文件格式如下：
字符串\t数字\n

说明：
每行为1条记录；字符串中不含有\t。
数字描述的是该字符串的出现概率，小于等于100的整数。
多条记录的出现概率之和为100，如果A.txt不满足该条件，程序则退出；
  C% D- T. m2 {+ s6 l+ y' u如果文件格式错误，程序也退出。

/ R- I9 b# G, g. y# Q3 ^要求：
编写一个程序，输入为N（正整数），读入文件A.txt，按照字符串出现概率随机

地输出字符串，输出N条记录

" |" U# @2 S+ z# ?0 ^2 V6 k8 U1 z例如：
输入文件A.txt
abc\t20
a\t30
, I- X- t" S/ P. z+ m. u- V# x) {de\t50
输入为：10
- U6 r4 V6 n+ `0 v$ q
$ U) v: B6 u$ |4 r$ O& C+ ]! S即 abc有20%的概率输出，a有30%的概率输出，de有50%的概率输出，输出10条记
) p& g1 W# s: G
# D2 W% w. D/ \& R; \. y录
以下为一次输出的结果,多次输出的结果可能不相同。
% Y* ^- ]9 v2 M( A0 I6 G. Cabc
+ n! L- q8 e$ k  h0 u4 ?2 Ua
de
de
abc
9 i0 M$ X: Y. m0 J, B4 pde
a
de
) c; e3 I, N( q2 |3 Z6 V" p6 I+ F) \a
) `, O# T1 p% e6 S0 [: [de

4 F: ~) w: k; a二、算法题（35分）
题目描述：
0 I% [- J3 {# l- i# J设有n个正整数，将它们联接成一排，组成一个最小的多位整数。
0 b, |" |- u, p; y& X9 M+ C
程序输入：n个数
* `0 M  z( U; ]% C: M6 t6 W! t程序输出：联接成的多位数
! A$ e4 n5 K+ T# v; @
, s! {8 J( `! H. F9 c) j5 J$ ~例如：
9 X' T; ~. h- z6 g. Sn=2时，2个整数32，321连接成的最小整数为：32132，
n=4时，4个整数55，31，312, 33 联接成的最小整数为：312313355
  Y0 T2 o/ W; l/ ^+ z. f4 u( p. j
  p" x9 G* E$ h4 u5 i! {3 m( J[题目要求]
1. 给出伪代码即可，请给出对应的文字说明，并使用上面给出的例子试验你的算

& h" T& Q$ E( Q9 I+ H1 r法。
2. 给出算法的时间空间复杂度。
7 Z2 \+ z7 |' K/ s" x3. 证明你的算法。（非常重要）

, t# _8 b) i7 J5 A$ a' ^, _三、系统设计题（35分）
在一个有1000万用户的系统中，设计一个推送(feed)系统。以下是一些预定义概

念
1、用户：在这个系统中，每个用户用一个递增的unsigned int来表示user id(简
; h( y7 Y$ v+ P! Y
写为uid)；则uid的范围是从1到1000万的正整数。
2、好友：用户之间可以形成好友关系，好友是双向的；比如说uid为3和uid为4的
( c, T) \+ b4 X* |1 ], }4 N! ?
两个用户可以互为好友。每个用户好友的上限是500个；用户之间的好友关系可以
; }! q9 m) H0 {* o. I' J
; [/ F1 g: u: E8 J" V% ?被解除
! E4 k. {, @0 _/ Y3、活动：每个用户只能发文章；文章可以被作者删除，其他人不能删除非自己发

0 y6 ]; ?0 ^7 J表的文章；每篇文章通过一个blogid表示。
4 s: `; F4 h* y  g, C% S8 \! B# Z4、feed：我们希望，每个用户可以看到他所有好友的活动列表，在这个简化的系

统中就是所有好友的文章更新列表。
5、访问量要求：所有feed访问量每天在1亿量级；所有的blogid增加量每天在百
( x4 D4 X% W$ _' @" c
万量级。

8 e& P4 F$ i4 W% |9 V0 B: y& Y) v( Z1 N% a题目：请在以上限制条件下，设计一个高效的feed访问系统。

要求：
* A$ Q& |4 k) m$ J& T1 ?1、能够尽快的返回每个用户的好友feed列表，每个用户可以最多保留1000条feed
" K8 f) V3 E: P0 K
；feed的展现按照时间倒排序，最新的在最前面
2、用户删除某篇文章后，被推出去的feed需要及时消失。即每个用户看到的好友

5 s$ N8 o5 M+ {. @0 v" \5 Efeed都是未被删除的
: e( E+ H' }4 I3、尽可能高效。

( Z; |; A& u$ j/ c百度历年校园招聘笔试题：http://bbs.aftjob.com/thread-417000-1-1.html
2 D' N; w4 o" h3 M, W) M& b百度历年实习生招聘真题：http://bbs.aftjob.com/thread-606504-1-1.html
; X2 [' D4 {; }: d3 d) p1 F3 f7 X百度2010实习生笔试2套：http://bbs.aftjob.com/thread-610484-1-1.html
  k; r8 h7 u( U, @  U% C2 v0 C: i百度求职俱乐部：http://bbs.aftjob.com/group-4-1.html