百度2011实习生招聘笔试题

aftyingjiesheng

百度2011实习生招聘笔试题
$ y  L3 p6 k* d/ h! E  Y! H
笔试时间：5月7日


! M; n- K) D! o- ^2009百度实习笔试题Zz
8 [& m# A! C9 a, K  A
一、编程题（30分）
( h2 J; \5 u8 w0 I* Z, s) k8 j& g输入：N（整数）
输入：数据文件A.txt，不超过6条记录，字符串长度不超过15个字节
8 ~- O+ c+ o7 P& U文件格式如下：
# @( ~; ^. p+ R- a, s& f字符串\t数字\n
5 L5 k# b6 I* _+ N  A说明：
$ i1 o1 c# @9 `每行为1条记录；字符串中不含有\t。
数字描述的是该字符串的出现概率，小于等于100的整数。
多条记录的出现概率之和为100，如果A.txt不满足该条件，程序则退出；
0 e  A3 ]" z% e如果文件格式错误，程序也退出。
要求：
编写一个程序，输入为N（正整数），读入文件A.txt，按照字符串出现概率随机
$ C7 }5 C$ N4 u( ]地输出字符串，输出N条记录
例如：
输入文件A.txt
2 T2 p3 b7 n$ Q% H! j+ q4 T0 k, Yabc\t20
& S; B6 N8 W3 i- q) @2 q9 Y5 Ea\t30
de\t50
' A! ^% n$ ?$ t  }4 ^输入为：10
即 abc有20%的概率输出，a有30%的概率输出，de有50%的概率输出，输出10条记
3 ]$ ^6 \* I" N: Q录
以下为一次输出的结果,多次输出的结果可能不相同。
abc
a
- D' ]8 K/ R4 J1 c$ [( f0 Lde
de
5 |3 ?& H% \9 Y4 f/ xabc
, Y; Y" V, C6 x0 s- ~' o# T% E/ ede
a
de
. F6 ]; M, [4 S5 x5 A3 ya
de
& C% X# \* w/ ]  M二、算法题（35分）
题目描述：
设有n个正整数，将它们联接成一排，组成一个最小的多位整数。
程序输入：n个数
* q/ i: q7 P  j1 b+ r程序输出：联接成的多位数
例如：
+ C: j9 l' c$ N3 g% xn=2时，2个整数32，321连接成的最小整数为：32132，
n=4时，4个整数55，31，312, 33 联接成的最小整数为：312313355
[题目要求]
/ m( o" [/ `7 @6 R. ^/ H1. 给出伪代码即可，请给出对应的文字说明，并使用上面给出的例子试验你的算
法。
2. 给出算法的时间空间复杂度。
3. 证明你的算法。（非常重要）
三、系统设计题（35分）
! h8 R* E0 _6 C: \9 o. Y在一个有1000万用户的系统中，设计一个推送(feed)系统。以下是一些预定义概
念
3 z& _6 Y- f, M/ |( ~0 P1、用户：在这个系统中，每个用户用一个递增的unsigned int来表示user id(简
- P/ N7 n1 }4 `写为uid)；则uid的范围是从1到1000万的正整数。
2、好友：用户之间可以形成好友关系，好友是双向的；比如说uid为3和uid为4的
两个用户可以互为好友。每个用户好友的上限是500个；用户之间的好友关系可以
& [7 _) S, \0 S9 D8 B# F9 }* p9 V被解除
, N( k. C: L  [- @; `3、活动：每个用户只能发文章；文章可以被作者删除，其他人不能删除非自己发
) A; i  D# s  [1 J" s6 H3 \表的文章；每篇文章通过一个blogid表示。
4、feed：我们希望，每个用户可以看到他所有好友的活动列表，在这个简化的系
  ^+ M' L2 F- H" I4 [统中就是所有好友的文章更新列表。
5、访问量要求：所有feed访问量每天在1亿量级；所有的blogid增加量每天在百
" ?4 A6 x0 T8 E& C" e) O万量级。
! Q: c+ \  |; d5 Q2 v9 n: ?8 l题目：请在以上限制条件下，设计一个高效的feed访问系统。
+ R4 w5 C6 Y' @; K0 y  d要求：
1、能够尽快的返回每个用户的好友feed列表，每个用户可以最多保留1000条feed
. ?+ I, U6 j; t0 [5 Y；feed的展现按照时间倒排序，最新的在最前面
2、用户删除某篇文章后，被推出去的feed需要及时消失。即每个用户看到的好友
feed都是未被删除的
2 C* o3 a4 z9 \" B: }; _3、尽可能高效。
. f- R7 j( I, T; E( X
Zz
5 \) p# q; `" Z" t  k8 W信息来自:阿凡提求职社区
0 @% `! r0 d  \0 T- ^- k——
百度历年实习生招聘真题
9 [0 I( H" g) d) S! Khttp://bbs.aftjob.com/thread-606504-1-1.html
. N2 B! i" T' M$ h5 ]2010年百度实习笔试真题（全套，2010年5月）
http://bbs.aftjob.com/thread-606500-1-1.html
2009年百度实习笔试真题
# W" L" [* Q; |8 Jhttp://bbs.aftjob.com/thread-114579-1-1.html
百度这三年实习招聘必考的题目
' j$ c5 N8 _% Ohttp://bbs.aftjob.com/thread-606503-1-1.html
( T: q) x; ~$ Q2 t: |, q! i百度历年校园招聘笔试题
+ a+ F0 o" J: n3 Y7 Q- hhttp://bbs.aftjob.com/thread-417000-1-1.html
——
面试时间：5月8日开始
工作人员电话通知笔试通过的同学到指定地点进行现场面试。

黄俊晓

顶一下