08.13 – 百度日文图搜1,2面 - 余总

aftyingjiesheng

08.13 – 百度日文图搜1,2面 - 余总

+ T, C' K$ z- p% g
0 {( q# J& l2 W$ w
在朋友的帮助下，今天面百度 一共面了两面，第一个人面完，喊出另外一个工程师接着面。
面试三点开始。我去得比较早，就在大厅里面等了个把钟头，环境看上去不错。哈哈。具体后面说。
2 R- |# T; q  X# t. Q& S
第一面
% I9 a2 l5 m2 c. |' D4 u8 ]一个哥哥，挺kind的。聊天知道貌似是浙大ACM的，而且还跟我们大组的一个博士gg是好朋友。
首先，自我介绍，稍微说了下。这里我觉得是每个人唯一可以准备得最好的了。说条理点，给人家一个立体印象会很好。然后就要“例行公事了”，开搞：
第一题，据说中的经典算法，数组a[len]，找出其中最大的三个数。写程序，写个意思就行。
7 c$ T. u1 W+ a# M9 n+ `" p第二题 ，貌似搞算法的人都知道，应该也是据说中的经典题。有一个单向链表。对于单链表，链表尾部是NULL。突然有一天，某人没事把尾部的指针指向了链表中间的某个元素，这样就形成了一个网球拍状的链表，一个柄，然后前面一个圈。  
  问题1：如何遍历链表（可以重复访问）（hint：简单next访问的话，会死循环在圈里的哦，所以得想点办法）
: E; \5 M" `& O# ^) r  问题2：如何确定柄和圈相接位置的元素是哪个？
$ @; s7 H, ^* T' Y% H第三题，开放题，关于图片搜索。
+ d$ V  N2 o! k- V一个页面，例如http://esfang.house.sina.com.cn/n_news/news_show.php?id=20439这个link里面，有个图片。图片搜索的基本思想是候根据页面正文的内容来推测图片内容。这个页面中，除了正文上有文字，顶上、边上都有链接和广告，是与图片不相关的内容，需要过滤掉。如何过滤这些五官内容，提取正文？ 请说出你的思路。方法可以不拘一格，可以多种方法并用。我扯出了六七种，应该都还蛮靠谱。
$ {$ S6 m: P) U3 e4 B9 n  c. ?
+ F9 [# t4 s, }" }) U& o+ q9 zOK，就这么多面试问题。我看了下表，刚好一个小时。这个gg喊了另外一个gg来接着面。
5 b& }( [6 @/ W: g
二面开始
还是先自我介绍，让随便讲讲。很快进入主题，开始做题：
2 E: M, |9 C' P% Z- v第一题 ： 100万行ip地址区间，已排序。给出一个ip地址，从100万行中找出该ip地址所属行。如果找不到，输出找不到即可。
已知，区间首尾两个ip的前三节的ip地址相等，只有最后一节不同。
例如：
127.0.0.3   ~  127.0.0.6
# j( p- P3 ?3 }127.0.0.16 ~  127.0.0.49        
( A+ \3 V0 W+ U  ~( u8 x8 q.....
210.2.0.16 ~  210.2.0.233
: U; C; P/ @2 A) }.....
* P3 R, k; n: A9 s' D' I上面每个区间前三节都等。
& ]) ?. [3 k# q. e, h. }210.2.0.16 ~  210.4.0.233这样的区间不合法，不回出现在给出的
数据中。
给出输入127.0.0.18，输出为127.0.0.16 ~  127.0.0.49。
5 W) x: O% F1 [" N2 ?3 O' n4 c
6 Q3 S  d% M& o这个题目补充一句，最容易想到的算法就是二分查找了。可行。面试的人非得让我想出个更快的方法。没想出来，到最后结束的时候问了下他答案，也就是加快查找那些事，恩，你知道的。
% c, T' ]# M5 j: n. M! C
, {2 H8 y( m# x$ m% q第二题 ，你知道Cache替换算法有哪些嘛？你学过吗？
0 n: M' G$ K/ t) W1 E& e恩，我当然学过。blablabla
5 J% Q; h# q$ }  z6 o3 x, _那么你能实现一个LRU Cache算法吗？
/ R8 I- u3 e; T1 R, o( Q+ C9 W我走偏了。。。。。直接以为要实现一个硬件Cache LRU替换算法。。。太失误了。。。他一个搞软件的，关心硬件Cache干吗。。。
/ j& X% m% T3 S$ m; eOK，软件LRU算法如何实现大家肯定都知道。
这个题目是他一个引子，后面开始才是重点。题目大意，百度贴吧这么多帖子，动不动还有“贾君鹏你妈喊你回家吃饭”的爆吧行为。如何设计一套存储系统以满足贴吧的需求。设计包括Cache、磁盘文件数据块的布局、结构、安排等等。总之，设计一个存储系统！我真有点汗。。。这个题目突然冒出来，挺不合适的吧。反正给我的感觉是太大了。
( L, g. L0 B1 A: x; [5 y注，贴吧特征：
1、 老帖子一旦回复了，就跑到顶上了。玩bbs的同学都了解。
2、偶尔存在暴吧行为，如何抗住这种压力（这里指存储压力），如何保证这种帖子还能被正常阅读
' K1 {! C- _& k3 H3 |3、很多用户只看贴吧头几页的帖子，所有针对这个特点应该可以做一些优化（Cache）。
2 N: M1 f2 h0 S& ~; X: `" q+ _0 W( YOK，设计吧。。。反正这个题目把我搞得很不爽。我猜，他是揣着答案了，总希望我说的跟贴吧的设计相似：（
/ {, L  p" ~% g# N  y
面完大概五点，说下周等消息。他直接撤了，一人在那，哈哈，正好可以乘机溜达一下百度。先电话我偶像，用她门卡到处溜了一圈，然后去百度健身房跑了半个小时的步，到了饭点，直接去百度地下食堂吃了顿饭，还凑合。OVER。
- A7 J3 v( ], `* J2 i8 {' b( R
总结下，算法我有点卡，因为没有任何准备。我总觉得他们问的问题，《编程之美》上都涉及到了，并且比他们问的还深。所以，我决定开始好好看看《编程之美》了。 另外，他们都重复地问，能来实习么。不能
3 Y3 A2 s& i8 `1 N$ ?/ h


: `/ Z& W8 X+ J* S) o6 j文章摘自2012阿凡提求职手册——IT行业篇
; A9 j! R& Q) U, shttp://bbs.aftjob.com/thread-607158-1-1.html
% q" L  G* C$ C7 W+ E) |6 j" Y5 r——
阿凡提百度(Baidu)求职俱乐部
- K9 F0 O1 Y% h! d7 @2 {$ P9 [http://bbs.aftjob.com/group-4-1.html
  L) K/ G) e: r0 p! Z——
关于Web前端及百度web前端笔试面试题目
http://bbs.aftjob.com/thread-31614-1-1.html
百度质量部测试一面面经
# a# b# G9 y4 k# Y6 t+ P# _  R4 nhttp://bbs.aftjob.com/forum-viewthread-tid-31594-fromuid-35176.html
! T! s8 i' d( g3 I4 X/ @5 s百度面经篇
1 w, Z; Z! h# Y& _http://bbs.aftjob.com/forum-viewthread-tid-469368-fromuid-35176.html
$ b7 b8 w* p# \' D: u——
2 h( u4 r, n/ h1 u+ _2 y+ `. M阿凡提(aftjob.com)求职社区
; o- j! y$ T8 C3 |7 n阿凡提求职俱乐部－国内第一家网络求职俱乐部，提供企业求职俱乐部和高校求职俱乐部交流平台。
——