百度（Baidu）校园招聘笔试题

aftyingjiesheng

百度（Baidu）校园招聘笔试题


2009百度笔试题Zz

一、编程题（30分）
9 U" J( ]# M4 B" K* W输入：N（整数）
& z% h' {8 V, Y, g+ ~输入：数据文件A.txt，不超过6条记录，字符串长度不超过15个字节
文件格式如下：
+ n9 \7 \7 c  H: N! q字符串\t数字\n
) N2 Y; k5 ?) u* Y
6 a' N* I& P& I- m说明：
% B. q7 ^6 p: b5 d2 I每行为1条记录；字符串中不含有\t。
' z' j% K. r* T' X( U7 Q数字描述的是该字符串的出现概率，小于等于100的整数。
* ]3 P* [8 L: c8 e多条记录的出现概率之和为100，如果A.txt不满足该条件，程序则退出；
如果文件格式错误，程序也退出。
" M; s: K2 _. _( z4 N) X, g
要求：
, j$ }" R, T7 f3 i5 z编写一个程序，输入为N（正整数），读入文件A.txt，按照字符串出现概率随机
6 ~! O: {7 F" i0 i
地输出字符串，输出N条记录
0 B4 y/ R+ ]6 h: ~0 a/ v" s
# x+ ?8 Y# o0 X8 ~1 @例如：
输入文件A.txt
* h$ z( r& q% u1 dabc\t20
a\t30
& T1 b; g8 h8 @de\t50
  @* t8 g- P. _输入为：10

即 abc有20%的概率输出，a有30%的概率输出，de有50%的概率输出，输出10条记

录
5 a% L- t" r8 U, v6 j+ A4 K) W以下为一次输出的结果,多次输出的结果可能不相同。
4 d, a% x  \( z* \abc
( M' c4 d  _& Y' }/ S6 Ca
de
# _' S( }& e) j2 g6 l6 m6 fde
abc
% g3 Y3 H) R* @' ~de
a
" C' [1 `6 A" s5 Fde
a
: `+ f: Z' g% e/ C) }4 kde

, q3 r1 E6 J5 x二、算法题（35分）
题目描述：
设有n个正整数，将它们联接成一排，组成一个最小的多位整数。
: f5 }7 o+ ~% O: B
程序输入：n个数
3 B3 t/ z4 h2 H) p3 Q0 [" c程序输出：联接成的多位数

9 ^# \+ ]$ E9 M) t. m例如：
0 e4 Q$ Q- g: Kn=2时，2个整数32，321连接成的最小整数为：32132，
n=4时，4个整数55，31，312, 33 联接成的最小整数为：312313355

' @8 x8 A4 V5 y* m! {$ u[题目要求]
* T& j% a" `; R4 L1. 给出伪代码即可，请给出对应的文字说明，并使用上面给出的例子试验你的算

+ x. V* f0 E* L1 W  d& Q4 |法。
0 b, O. b3 W: X( p6 h7 _# k' Q2. 给出算法的时间空间复杂度。
3. 证明你的算法。（非常重要）

7 y/ g3 M3 U0 c三、系统设计题（35分）
在一个有1000万用户的系统中，设计一个推送(feed)系统。以下是一些预定义概

  D! I( R" i# }0 }: H& K念
1、用户：在这个系统中，每个用户用一个递增的unsigned int来表示user id(简

: j( m- X: `) @9 B写为uid)；则uid的范围是从1到1000万的正整数。
: ]4 n! P3 q9 e% I4 `  k' T2、好友：用户之间可以形成好友关系，好友是双向的；比如说uid为3和uid为4的

  M2 [. v% U+ q两个用户可以互为好友。每个用户好友的上限是500个；用户之间的好友关系可以
3 z" A+ z! r: u' W3 ?
% V# R& s: p5 N0 L& d% }0 J) J被解除
3、活动：每个用户只能发文章；文章可以被作者删除，其他人不能删除非自己发

) L! t1 f! f9 G* `表的文章；每篇文章通过一个blogid表示。
% b. |8 A! D* j% V0 `$ P4 X4、feed：我们希望，每个用户可以看到他所有好友的活动列表，在这个简化的系
3 n7 V' N" m. C* F& l1 [, ?: }
统中就是所有好友的文章更新列表。
, ]3 J0 E5 M  J2 `5、访问量要求：所有feed访问量每天在1亿量级；所有的blogid增加量每天在百

万量级。

题目：请在以上限制条件下，设计一个高效的feed访问系统。
# R8 j" i* F3 Q+ N
7 E, A& y& \6 q3 ~要求：
1、能够尽快的返回每个用户的好友feed列表，每个用户可以最多保留1000条feed
6 N# ]* c. d8 K9 s1 a( g
+ I8 F0 y# L* {；feed的展现按照时间倒排序，最新的在最前面
2、用户删除某篇文章后，被推出去的feed需要及时消失。即每个用户看到的好友
% d. I0 t) ^, ]9 W
# w. |4 N& X0 b% F( e, P! K+ ?feed都是未被删除的
3、尽可能高效。
9 f' f% i/ o* ~  _. M

, y5 X+ @6 q4 X3 }4 B' j& pZz


1 N  R. n7 q1 n2 p2 C——
百度历年校园招聘笔试题（2005-2009年）
0 K, p9 ]+ c! hhttp://www.aftjob.com/bbs/thread-417000-1-1.html
7 g7 J" d7 s6 x8 c' E
百度笔经大全
6 _, H6 ?) [1 U# Z- y  }% \http://www.aftjob.com/bbs/thread-263898-1-1.html

1 j: N+ s% |, z' R& X9 T/ A2006百度在线笔试题及答案
" [+ l- d+ E6 y. Q6 x" Uhttp://www.aftjob.com/bbs/thread-263888-1-1.html

. |: a& G6 x$ {5 _2 r3 S+ v% @百度在线笔试分享
http://www.aftjob.com/bbs/thread-164108-1-1.html

3 z+ g. i8 ]# s# d, @  wbaidu笔试
http://www.aftjob.com/bbs/thread-31644-1-1.html
* B6 ?& E" t; E
# P! P! E8 H9 {5 O4 a百度笔试题ZZ
http://www.aftjob.com/bbs/thread-170475-1-1.html
- w4 E4 Y7 N/ s: \4 Z, H
2 m# [  ]2 P2 y, v- y2 Dzt 百度非技术笔试题
http://www.aftjob.com/bbs/thread-31656-1-1.html
4 s' Q, l1 a6 A, H
百度川大站笔试题 Zz
" |- b# z& k- Xhttp://www.aftjob.com/bbs/thread-109752-1-1.html

+ m$ s" Z- r8 \) z# }2 X9 g/ m……

查看名企2012校园招聘最新进度，请关注阿凡提求职公共日历：http://www.aftjob.com/home.php?mod=space&do=calendar
$ `  G- ]6 E. n, C7 U百度历年校园招聘笔试题：http://bbs.aftjob.com/thread-417000-1-1.html
百度历年校园招聘笔试题：http://bbs.aftjob.com/thread-417000-1-1.html
2012腾讯求职手册:http://bbs.aftjob.com/thread-608477-1-1.html
2012百度求职手册:http://bbs.aftjob.com/thread-608484-1-1.html
2012阿凡提求职手册——IT行业篇 :http://bbs.aftjob.com/thread-607158-1-1.html