2009百度实习笔试题

aftyingjiesheng

2009百度实习笔试题
1 g) E9 {4 D% N: `2 B; Y
2 q+ x! ]; v9 O
0 ]% j; A; D/ g
: f# R! ~# G8 }2 e  a9 P* Z0 M/ p
一、编程题（30分）
& ]/ L, n0 {$ R* [- E1 ]  i5 y- l输入：N（整数）
输入：数据文件A.txt，不超过6条记录，字符串长度不超过15个字节
文件格式如下：
字符串\t数字\n

说明：
每行为1条记录；字符串中不含有\t。
3 O! z, `% o) L, j/ G1 s* o: l数字描述的是该字符串的出现概率，小于等于100的整数。
多条记录的出现概率之和为100，如果A.txt不满足该条件，程序则退出；
9 f! @* U& V- X如果文件格式错误，程序也退出。
7 A  r* n- j8 Y3 R: s* T
+ N0 s+ s5 P- d0 ^5 |! C要求：
编写一个程序，输入为N（正整数），读入文件A.txt，按照字符串出现概率随机

0 o) m3 n% N2 ]* K地输出字符串，输出N条记录

  `8 z# u' X9 o( m  J7 {例如：
输入文件A.txt
abc\t20
$ L  E6 Z- T5 S. xa\t30
de\t50
输入为：10
5 R3 p" z- S5 z
4 O; m; E& `! x& k6 P* p9 k- R) r即 abc有20%的概率输出，a有30%的概率输出，de有50%的概率输出，输出10条记
. g9 X0 F2 R3 M1 x
: B! w: m: u$ g6 o" r) Z录
* W$ i4 ^" @- R8 x2 b以下为一次输出的结果,多次输出的结果可能不相同。
abc
a
de
7 R5 }5 h+ f" l$ S/ Xde
abc
% ~6 J( n! U2 V" a* E! h1 y* K3 `( B5 Zde
a
de
! T5 _- z0 z2 l( C5 Z' r) pa
de
5 j  A2 r" T8 t* b1 |6 e! H
- L0 g- f0 l; ^5 p二、算法题（35分）
题目描述：
设有n个正整数，将它们联接成一排，组成一个最小的多位整数。
  t) k  k+ D/ |% G4 d% k9 P/ z
- w  }  t1 G) k! `1 L程序输入：n个数
; z3 f# [; p: p( j; K5 T0 |程序输出：联接成的多位数
: k# C! D3 v$ C$ N- T% V5 ^' T
例如：
- H( }5 @  N' f) D7 kn=2时，2个整数32，321连接成的最小整数为：32132，
n=4时，4个整数55，31，312, 33 联接成的最小整数为：312313355

[题目要求]
" o$ Y! x: q, I1 @( n) d' w. X1. 给出伪代码即可，请给出对应的文字说明，并使用上面给出的例子试验你的算

法。
2. 给出算法的时间空间复杂度。
6 D: c* L. }+ N; O: J3. 证明你的算法。（非常重要）

: K1 r/ Z+ {2 l, F& Q1 C. Y三、系统设计题（35分）
! a, F1 T6 E7 n$ L6 g; Y7 x! T在一个有1000万用户的系统中，设计一个推送(feed)系统。以下是一些预定义概

念
1、用户：在这个系统中，每个用户用一个递增的unsigned int来表示user id(简
, r6 t9 G: P' w% X4 c0 [5 i# O3 V
写为uid)；则uid的范围是从1到1000万的正整数。
: I  G7 o" |' g, q1 ]- I7 i& u: T; c2、好友：用户之间可以形成好友关系，好友是双向的；比如说uid为3和uid为4的
4 f4 ~; _8 S: o& ~+ X
两个用户可以互为好友。每个用户好友的上限是500个；用户之间的好友关系可以

被解除
3、活动：每个用户只能发文章；文章可以被作者删除，其他人不能删除非自己发

表的文章；每篇文章通过一个blogid表示。
4、feed：我们希望，每个用户可以看到他所有好友的活动列表，在这个简化的系
' D5 `' S$ i* B2 a, l
统中就是所有好友的文章更新列表。
5、访问量要求：所有feed访问量每天在1亿量级；所有的blogid增加量每天在百

万量级。

题目：请在以上限制条件下，设计一个高效的feed访问系统。

要求：
" g1 Z. p% Z( R6 g% @/ i( q0 J; d1、能够尽快的返回每个用户的好友feed列表，每个用户可以最多保留1000条feed
0 U  `1 D) h$ j7 G' z
! l! N8 t# n- O  D1 {9 b；feed的展现按照时间倒排序，最新的在最前面
+ c, u+ F1 V% d) d2 J2、用户删除某篇文章后，被推出去的feed需要及时消失。即每个用户看到的好友
+ C9 t$ X. r4 X; u$ r0 {
! p5 A# X/ _0 f/ [0 j# w& Xfeed都是未被删除的
9 i4 K9 K  K! J8 g: Y) A3、尽可能高效。
# Y" h) I. Z. T: Q6 p" p2 c
* [0 l6 O9 d  `  I- l: f, G百度历年校园招聘笔试题：http://bbs.aftjob.com/thread-417000-1-1.html
6 }/ O8 L6 p$ T; q  P4 A; Q百度历年实习生招聘真题：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