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

aftyingjiesheng

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


' l' b" i" V/ r! ~/ o; ?- D) P4 F1 C5 J2009百度笔试题Zz

一、编程题（30分）
( E. _/ \3 x  L输入：N（整数）
输入：数据文件A.txt，不超过6条记录，字符串长度不超过15个字节
: E- E* {8 @6 O  s1 d0 k文件格式如下：
: l- i+ ]; S' i字符串\t数字\n

说明：
' r; d% N' R* J; F  ]每行为1条记录；字符串中不含有\t。
$ ]+ g& ^4 N' X- y" {1 {数字描述的是该字符串的出现概率，小于等于100的整数。
多条记录的出现概率之和为100，如果A.txt不满足该条件，程序则退出；
' ^+ b; d0 T1 k( c+ f* T0 p如果文件格式错误，程序也退出。

要求：
编写一个程序，输入为N（正整数），读入文件A.txt，按照字符串出现概率随机

地输出字符串，输出N条记录

例如：
输入文件A.txt
abc\t20
* v. \+ R  ?1 @' B/ z0 T- ia\t30
de\t50
) H' E1 F2 `. t# W输入为：10
' P5 @; |4 l( z5 q
; }* s5 |" Q( A即 abc有20%的概率输出，a有30%的概率输出，de有50%的概率输出，输出10条记

( k6 I; C7 K' i! V$ N录
以下为一次输出的结果,多次输出的结果可能不相同。
* H* Y) Y3 ~1 c5 X  e) Sabc
a
  p& n7 g2 [& y; c$ ude
0 e2 m7 Z6 H, I( L9 g. `* w8 M! V8 mde
abc
de
  a- E: K7 R* X, F* p, J4 Y( ha
) U( W. }: d, \de
. S& P" b9 R- w4 n( _a
de

9 a& z6 Q$ k+ B" g0 Q1 E( Q二、算法题（35分）
题目描述：
设有n个正整数，将它们联接成一排，组成一个最小的多位整数。
' Q7 N2 k) K  ]
程序输入：n个数
程序输出：联接成的多位数
% q2 Z/ `8 m$ S0 Y/ z* D' l8 F+ b+ w
例如：
- i% }" _7 s% _n=2时，2个整数32，321连接成的最小整数为：32132，
n=4时，4个整数55，31，312, 33 联接成的最小整数为：312313355

. u+ i3 G( s5 k% t/ _[题目要求]
1. 给出伪代码即可，请给出对应的文字说明，并使用上面给出的例子试验你的算
" u9 H! i9 {2 M6 J% ?4 ^6 f) V4 ]
法。
2. 给出算法的时间空间复杂度。
1 [4 D; C( d6 u$ G' N% Q3. 证明你的算法。（非常重要）

7 H9 S  W! c. N) k  I' l/ l三、系统设计题（35分）
3 f& v; A: f! Y& d  L+ M在一个有1000万用户的系统中，设计一个推送(feed)系统。以下是一些预定义概
1 `0 Z& {4 N3 k! [
- Z- p; n% V+ z. D6 g4 d念
6 D  ~( m1 f9 e8 f* q1、用户：在这个系统中，每个用户用一个递增的unsigned int来表示user id(简
: V  h! y+ z1 S, X0 G2 k
7 U3 w2 O1 k3 I2 L7 \写为uid)；则uid的范围是从1到1000万的正整数。
5 m* i" M3 J/ t$ s4 r2、好友：用户之间可以形成好友关系，好友是双向的；比如说uid为3和uid为4的

0 T( b8 P4 }4 ?, d+ u5 N两个用户可以互为好友。每个用户好友的上限是500个；用户之间的好友关系可以
8 u5 ^% @+ E7 s5 K) P3 m' j
. n1 i3 f$ @4 T; ]0 _; A5 g& T被解除
* G& o, a0 L" p* o8 i/ E) b3、活动：每个用户只能发文章；文章可以被作者删除，其他人不能删除非自己发
% Q; A! {( q* o7 C9 l
表的文章；每篇文章通过一个blogid表示。
2 {2 \* B: V! x1 M8 J4、feed：我们希望，每个用户可以看到他所有好友的活动列表，在这个简化的系

统中就是所有好友的文章更新列表。
" V" g# l2 u4 s5、访问量要求：所有feed访问量每天在1亿量级；所有的blogid增加量每天在百
# p* h7 \7 M8 o4 ]$ f1 U% _. v/ [
4 v: ?/ W. ]4 B) w: J% t万量级。
5 ~' f. V* K5 P8 j' U# q
题目：请在以上限制条件下，设计一个高效的feed访问系统。

要求：
1、能够尽快的返回每个用户的好友feed列表，每个用户可以最多保留1000条feed
7 p0 f5 E" X# ]# Z' m  ?2 z( |
；feed的展现按照时间倒排序，最新的在最前面
2、用户删除某篇文章后，被推出去的feed需要及时消失。即每个用户看到的好友

6 O; p; n9 B1 O# V8 Gfeed都是未被删除的
/ w  Q/ [" N* e( j5 j3 \. e! `3、尽可能高效。


4 y+ ?; A* g! v1 l& dZz
+ s+ c8 I- X; Z2 z
9 B  e0 N# n! m  d. g; n* E
——
% f& E8 H: O  N% O! S. [百度历年校园招聘笔试题（2005-2009年）
http://www.aftjob.com/bbs/thread-417000-1-1.html
7 d2 B. D3 Z2 p8 V+ _
' \) A) k; f/ S9 T百度笔经大全
/ U5 ]( P) R+ r6 H( l* P* khttp://www.aftjob.com/bbs/thread-263898-1-1.html
! }3 M- |6 J( W
2006百度在线笔试题及答案
http://www.aftjob.com/bbs/thread-263888-1-1.html
- h9 D* X' l) A% E% i
百度在线笔试分享
0 l9 T' z5 o4 {0 ahttp://www.aftjob.com/bbs/thread-164108-1-1.html
! u* q* F3 T2 y7 u0 f* P: [! r
baidu笔试
/ Q9 O, c1 U; |* [http://www.aftjob.com/bbs/thread-31644-1-1.html
+ {5 C! m/ R1 J! W, {5 A
百度笔试题ZZ
, B/ n- P$ e2 A% Whttp://www.aftjob.com/bbs/thread-170475-1-1.html
  v+ m; Z: i5 n& b( P( a
0 B6 ?5 {; l. tzt 百度非技术笔试题
! w( O2 d: U! O* khttp://www.aftjob.com/bbs/thread-31656-1-1.html

  Y# ^) o# T+ W: C- F% D" D百度川大站笔试题 Zz
8 @1 a' a  Q1 J- rhttp://www.aftjob.com/bbs/thread-109752-1-1.html

/ S2 B7 R! A. B……

查看名企2012校园招聘最新进度，请关注阿凡提求职公共日历：http://www.aftjob.com/home.php?mod=space&do=calendar
/ _' G2 L% O8 A百度历年校园招聘笔试题：http://bbs.aftjob.com/thread-417000-1-1.html
) g# H6 T9 u* s2 A' m) p百度历年校园招聘笔试题：http://bbs.aftjob.com/thread-417000-1-1.html
  j7 B+ x& t! M1 L) v) M2012腾讯求职手册:http://bbs.aftjob.com/thread-608477-1-1.html
2012百度求职手册:http://bbs.aftjob.com/thread-608484-1-1.html
0 H' Q5 p8 O" G% ?0 v2012阿凡提求职手册——IT行业篇 :http://bbs.aftjob.com/thread-607158-1-1.html