2009百度实习笔试题

aftyingjiesheng

2009百度实习笔试题
8 F. i3 T7 s. |* N: Z) d5 r



一、编程题（30分）
/ E" U5 `, l9 J$ Y$ h0 x输入：N（整数）
2 B7 P$ ]. W9 Z4 k1 Y+ f4 d输入：数据文件A.txt，不超过6条记录，字符串长度不超过15个字节
文件格式如下：
0 J3 [8 E6 ]# [% y) H字符串\t数字\n
) @( {: J- z0 `- P7 Q1 B! @
说明：
每行为1条记录；字符串中不含有\t。
数字描述的是该字符串的出现概率，小于等于100的整数。
多条记录的出现概率之和为100，如果A.txt不满足该条件，程序则退出；
如果文件格式错误，程序也退出。
' O+ g, b# i  |  |: [2 F+ J
要求：
编写一个程序，输入为N（正整数），读入文件A.txt，按照字符串出现概率随机
7 ~( Y( ?$ S8 x7 y- v) I
地输出字符串，输出N条记录
1 g1 A5 \  t3 `3 Y1 D
例如：
8 C0 q4 o- D1 n输入文件A.txt
; C: u9 [. }: D; G+ S2 uabc\t20
a\t30
- `' d; ^1 _9 o/ F2 [. N! s: \de\t50
7 Z& S' }* G$ y) D5 P输入为：10

; O' ]1 ^0 l% a8 u9 P即 abc有20%的概率输出，a有30%的概率输出，de有50%的概率输出，输出10条记
0 [. }% I3 T) ^# C# b& n  ]
, Z+ _, `. }" l- U8 {. Q录
! p7 v! X! R# P* f4 F以下为一次输出的结果,多次输出的结果可能不相同。
# j9 U* P$ o+ _: k" Q, ^abc
2 v* j0 b" w$ N! `0 [1 {: d  Aa
de
5 r3 J/ a  p4 G* I* ^de
abc
de
a
" @/ ?' U; X" X) D0 ?8 _7 Fde
. T1 V, L1 E$ d- A: va
de
) B. J* I9 r) S. t# ~% M2 Y
二、算法题（35分）
& Y" ]1 X4 g, c2 s2 ^( O题目描述：
设有n个正整数，将它们联接成一排，组成一个最小的多位整数。
. j5 h# \9 p1 \7 i1 a9 z
程序输入：n个数
9 {% c9 \% H7 |5 ^! {程序输出：联接成的多位数
  s4 A" {7 ^" Y; `
5 r$ D$ Z- ]& F2 o9 R& u2 f/ a例如：
n=2时，2个整数32，321连接成的最小整数为：32132，
n=4时，4个整数55，31，312, 33 联接成的最小整数为：312313355
: G5 G+ B% k0 D. q  ]# ~/ N
5 Z0 p1 n3 f  ]/ q, v/ \' ?5 R[题目要求]
- Y$ \2 A1 b& h4 t! W! D; T# i1. 给出伪代码即可，请给出对应的文字说明，并使用上面给出的例子试验你的算

7 P+ ~/ s0 ^& U+ @  |- w# T法。
  E$ [% E( ]( ]+ W( |2. 给出算法的时间空间复杂度。
3. 证明你的算法。（非常重要）
) ^) i1 ]( F+ e: `
三、系统设计题（35分）
在一个有1000万用户的系统中，设计一个推送(feed)系统。以下是一些预定义概
3 D& L9 `- w; C9 H* i& X
念
1、用户：在这个系统中，每个用户用一个递增的unsigned int来表示user id(简
- e! A7 g& c) g
写为uid)；则uid的范围是从1到1000万的正整数。
6 e! ~, G7 j9 A" t2、好友：用户之间可以形成好友关系，好友是双向的；比如说uid为3和uid为4的
# {. r0 J' r0 f5 O. {
7 m7 L7 p9 H) [+ E+ G! j- s  s+ r两个用户可以互为好友。每个用户好友的上限是500个；用户之间的好友关系可以
# H+ ?* U  g/ b. u$ U6 n
被解除
: Y: h' E9 [- l( {3、活动：每个用户只能发文章；文章可以被作者删除，其他人不能删除非自己发

表的文章；每篇文章通过一个blogid表示。
) n7 s  l3 x/ j' R7 x4、feed：我们希望，每个用户可以看到他所有好友的活动列表，在这个简化的系

统中就是所有好友的文章更新列表。
5、访问量要求：所有feed访问量每天在1亿量级；所有的blogid增加量每天在百
4 ^) w7 ]& B& c/ R6 Z
$ W# M7 O9 e) m3 C; T$ M! T万量级。

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

, i% p+ v+ y4 u& R要求：
1、能够尽快的返回每个用户的好友feed列表，每个用户可以最多保留1000条feed

9 k( }! C' h" Z；feed的展现按照时间倒排序，最新的在最前面
2、用户删除某篇文章后，被推出去的feed需要及时消失。即每个用户看到的好友
) v6 E7 ]4 U0 w% R
feed都是未被删除的
! l- ?# U; ~# i' g; c3、尽可能高效。
. o% m; d) `7 z$ S& Z- t# N
) r  J5 s8 M$ c百度历年校园招聘笔试题：http://bbs.aftjob.com/thread-417000-1-1.html
  K' Q  P4 B( N/ T1 x9 j+ I% t百度历年实习生招聘真题：http://bbs.aftjob.com/thread-606504-1-1.html
4 o3 f9 d9 w& j0 F/ G: Y百度2010实习生笔试2套：http://bbs.aftjob.com/thread-610484-1-1.html
. C* E/ s/ ~* q' n% P: I  w百度求职俱乐部：http://bbs.aftjob.com/group-4-1.html