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

aftyingjiesheng

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


% K4 y2 a  x6 r' |+ J' v2009百度笔试题Zz
' `2 f# I' `2 H
* a0 x- V! |" r" l8 h" C一、编程题（30分）
2 o) J' s1 J2 u0 _" K输入：N（整数）
输入：数据文件A.txt，不超过6条记录，字符串长度不超过15个字节
4 i9 X' T& |, g" q1 a文件格式如下：
字符串\t数字\n

, `& @; C/ @4 _2 i* T" y说明：
每行为1条记录；字符串中不含有\t。
数字描述的是该字符串的出现概率，小于等于100的整数。
8 @- B0 k; n8 n多条记录的出现概率之和为100，如果A.txt不满足该条件，程序则退出；
如果文件格式错误，程序也退出。
4 Q) e, n7 H  ^) A+ }4 E* E
要求：
编写一个程序，输入为N（正整数），读入文件A.txt，按照字符串出现概率随机

! q% w) i! f- [5 a, M地输出字符串，输出N条记录

例如：
输入文件A.txt
abc\t20
; v! W8 D9 e8 k6 o1 s: da\t30
$ W- {, N3 X5 a! k  U* I; D9 ade\t50
输入为：10

9 w+ |$ v' m0 o5 Z' X, O即 abc有20%的概率输出，a有30%的概率输出，de有50%的概率输出，输出10条记
0 a; G2 `9 G% W# P: E* r# `
录
8 q) f, u3 G% k, `以下为一次输出的结果,多次输出的结果可能不相同。
0 N, q6 G4 U; l, Xabc
& f" W8 N& i3 ]5 {4 X$ t$ Fa
0 p) D* ]+ o* Kde
de
abc
de
; N0 v& d! p, }9 @/ m/ oa
de
# Z: T2 ^) ~1 c# U6 U6 B, aa
de
; ?. j( B! M, `2 U2 d- P
二、算法题（35分）
0 s( L- P3 e( v# F) h+ l) U题目描述：
2 I) V4 G, h! g5 ~/ o9 G; N设有n个正整数，将它们联接成一排，组成一个最小的多位整数。

程序输入：n个数
程序输出：联接成的多位数
: x, r! ~9 o1 b) h
5 h, H8 Y2 q) s5 }例如：
n=2时，2个整数32，321连接成的最小整数为：32132，
5 X$ F5 b* q5 l2 Q4 p' s) J, Jn=4时，4个整数55，31，312, 33 联接成的最小整数为：312313355

- h! H4 T; b3 y; ^  x" S[题目要求]
1. 给出伪代码即可，请给出对应的文字说明，并使用上面给出的例子试验你的算

法。
2. 给出算法的时间空间复杂度。
3. 证明你的算法。（非常重要）

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

念
# U3 c0 w! G4 A/ U' y1、用户：在这个系统中，每个用户用一个递增的unsigned int来表示user id(简

, \8 a$ @, P( x1 e& D* E+ O1 c写为uid)；则uid的范围是从1到1000万的正整数。
: s9 K; N8 K4 }$ k; P9 d2、好友：用户之间可以形成好友关系，好友是双向的；比如说uid为3和uid为4的
( x  W- |- A! A1 j
两个用户可以互为好友。每个用户好友的上限是500个；用户之间的好友关系可以

" r/ x+ {! F7 A+ n# U被解除
4 A* q. G, R- j7 b; u3、活动：每个用户只能发文章；文章可以被作者删除，其他人不能删除非自己发
* W" n& Y6 g  M3 x) k/ g2 l
表的文章；每篇文章通过一个blogid表示。
% V3 z% t3 M  O, P2 Z4、feed：我们希望，每个用户可以看到他所有好友的活动列表，在这个简化的系
( h0 \! {# o; Y! ~
* M! b: M+ }4 v( t* m5 D8 j统中就是所有好友的文章更新列表。
' {( k) M4 C! @9 G5、访问量要求：所有feed访问量每天在1亿量级；所有的blogid增加量每天在百

! W' ?2 l8 ~2 G' a2 T万量级。

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

6 [. l1 n5 ?% v! r- v* r要求：
1、能够尽快的返回每个用户的好友feed列表，每个用户可以最多保留1000条feed

( V  q7 b5 `' [; I+ u8 }& j/ J- R* r, `+ ]；feed的展现按照时间倒排序，最新的在最前面
2、用户删除某篇文章后，被推出去的feed需要及时消失。即每个用户看到的好友
9 v+ d3 [, Z, F8 I
feed都是未被删除的
  F7 F0 F, V6 t' f7 S) {9 L! C$ C* D: K3、尽可能高效。
; P1 [0 s% _. d3 }: `  I) U' h

Zz
& e. q+ S9 ~* Z1 V/ p2 I/ f

——
百度历年校园招聘笔试题（2005-2009年）
http://www.aftjob.com/bbs/thread-417000-1-1.html

! u3 ^9 k6 ^+ ]6 D百度笔经大全
http://www.aftjob.com/bbs/thread-263898-1-1.html
) j8 d- x, U4 T" H
2006百度在线笔试题及答案
( y8 [8 k. a. n4 N7 t$ ~$ c- P% l2 vhttp://www.aftjob.com/bbs/thread-263888-1-1.html
8 X( Q7 L) B# B2 l& @1 L% P
$ J+ F: g4 V) C百度在线笔试分享
0 E* C4 z! b8 v3 }8 vhttp://www.aftjob.com/bbs/thread-164108-1-1.html

baidu笔试
9 i% B! i4 h: K: t/ }http://www.aftjob.com/bbs/thread-31644-1-1.html

* K; R: \: H' V* g, S0 ~百度笔试题ZZ
http://www.aftjob.com/bbs/thread-170475-1-1.html
) g4 M; p$ h- w1 V: W" J! x
$ A' d2 o2 ?, q- [* H# T+ qzt 百度非技术笔试题
http://www.aftjob.com/bbs/thread-31656-1-1.html

1 i( s# `5 i: H; k& M$ g, B百度川大站笔试题 Zz
http://www.aftjob.com/bbs/thread-109752-1-1.html

7 {$ H; G; ]3 u" i+ q9 r) z& u5 N" x……
$ d. l2 E! \2 z0 X
. {; {3 M. m( v. B3 Y; h4 w查看名企2012校园招聘最新进度，请关注阿凡提求职公共日历：http://www.aftjob.com/home.php?mod=space&do=calendar
( M" Z, K$ O# n. G! J$ O% z6 N百度历年校园招聘笔试题：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
5 \) {7 h7 V4 ^2012阿凡提求职手册——IT行业篇 :http://bbs.aftjob.com/thread-607158-1-1.html