2009百度实习笔试题

aftyingjiesheng

2009百度实习笔试题




0 o' Y5 d+ I, D6 [* A% ]一、编程题（30分）
; \) E  @" u5 d+ |2 |+ l: ~' Z( }输入：N（整数）
* t. G0 N* a- {1 M6 Z输入：数据文件A.txt，不超过6条记录，字符串长度不超过15个字节
文件格式如下：
2 [# h1 |# u- z0 u0 z% _字符串\t数字\n

/ p1 t! b. N+ v1 \1 b说明：
每行为1条记录；字符串中不含有\t。
数字描述的是该字符串的出现概率，小于等于100的整数。
( R3 e' y1 ^- ^% V' X  A& A多条记录的出现概率之和为100，如果A.txt不满足该条件，程序则退出；
如果文件格式错误，程序也退出。

! _# `5 l8 J9 U: _) d! q& [要求：
编写一个程序，输入为N（正整数），读入文件A.txt，按照字符串出现概率随机
1 `  y3 }* t' o9 h. v# B
地输出字符串，输出N条记录
4 R3 K( a/ c6 K
例如：
4 A/ R1 _; B0 O: P6 p输入文件A.txt
3 o2 H+ w. n0 L. K' g! Mabc\t20
a\t30
de\t50
9 Y- w& @# y( I* l( ^3 n9 N  f输入为：10
1 i$ w; V/ g2 I* ~4 ]! @$ }
* k7 r: L: \! a0 E3 f% y$ E即 abc有20%的概率输出，a有30%的概率输出，de有50%的概率输出，输出10条记
9 T& t4 I- Z. c7 [" n
录
) X6 m  ]# r. [: V以下为一次输出的结果,多次输出的结果可能不相同。
abc
( V( }9 C. l2 `4 ?# \: Ja
de
de
0 u# [) C9 Y/ |abc
de
( s0 F$ M, @6 A) x! Z4 F8 }: [0 Ia
de
& b8 F; Z1 y, e1 ]5 I7 w4 wa
de
; t0 w  x7 d4 `7 D. O
二、算法题（35分）
- @7 Q2 O- s% f. ]题目描述：
设有n个正整数，将它们联接成一排，组成一个最小的多位整数。
1 [$ o; {  E. W4 r
程序输入：n个数
程序输出：联接成的多位数

, Q8 [" T7 l0 b6 Y例如：
& {8 E1 K8 S9 X# g" a# w/ En=2时，2个整数32，321连接成的最小整数为：32132，
% A2 G/ B0 n3 j# x- `! [n=4时，4个整数55，31，312, 33 联接成的最小整数为：312313355
' Z: c$ C. i  t+ B+ P/ O
[题目要求]
- i2 s2 t, W  `) ^  F6 s0 Z0 W) o1. 给出伪代码即可，请给出对应的文字说明，并使用上面给出的例子试验你的算

9 S) }# w% X# `' a- n( t9 I法。
2. 给出算法的时间空间复杂度。
$ M7 N, E( L; L4 ^: W9 r8 ?3. 证明你的算法。（非常重要）
& T+ [8 c! H% o; D0 I7 c( W
三、系统设计题（35分）
- J( c0 _8 a+ o' C' v9 `- [在一个有1000万用户的系统中，设计一个推送(feed)系统。以下是一些预定义概

念
1、用户：在这个系统中，每个用户用一个递增的unsigned int来表示user id(简

8 G7 ?. W2 U( [1 @& _; ]写为uid)；则uid的范围是从1到1000万的正整数。
+ g4 {4 G+ M3 n8 B3 G* M2、好友：用户之间可以形成好友关系，好友是双向的；比如说uid为3和uid为4的

8 W2 ~$ H2 p. J! t4 e两个用户可以互为好友。每个用户好友的上限是500个；用户之间的好友关系可以

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

/ ^5 i' E: q6 E6 o表的文章；每篇文章通过一个blogid表示。
4、feed：我们希望，每个用户可以看到他所有好友的活动列表，在这个简化的系
' w6 P4 o# a# ]+ S3 \' m
统中就是所有好友的文章更新列表。
5、访问量要求：所有feed访问量每天在1亿量级；所有的blogid增加量每天在百
, C" P6 z: W  b# u
万量级。

  u$ o" U- {9 u& w8 b+ ]7 v题目：请在以上限制条件下，设计一个高效的feed访问系统。

3 V+ m' b& R* ?$ j& K要求：
1、能够尽快的返回每个用户的好友feed列表，每个用户可以最多保留1000条feed
4 ^9 T% H' y9 P$ ]0 U+ e. o8 r: o
；feed的展现按照时间倒排序，最新的在最前面
- r; m( z4 I5 r. j3 S2、用户删除某篇文章后，被推出去的feed需要及时消失。即每个用户看到的好友

feed都是未被删除的
3、尽可能高效。

8 W0 D6 u' }( K- d3 Q# Q( t百度历年校园招聘笔试题：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
$ x3 M# R- s; `" x! H/ ~9 }百度求职俱乐部：http://bbs.aftjob.com/group-4-1.html