百度筆經(jīng)&面經(jīng)(zz,詳細(xì)！贊！)
2007年10月20日 星期六 16:34發(fā)信人: ptlj (PT), 信區(qū): Job_Discuss
?標(biāo) 題: 百度筆經(jīng)&面經(jīng) 發(fā)信站: 武漢白云黃鶴站 (2007年10月08日12:50:13 星期一)
?看了一下精華區(qū)，好像關(guān)于百度的筆經(jīng)和面經(jīng)很少，所以上來發(fā)一下，積攢RP～～PS:我投的是商務(wù)搜索部的引擎研發(fā)工程師。
【筆試】百度的在華科的筆試在9月21號晚上宣講會后馬上舉行。宣講會那叫一個人山人海， 很多不是畢業(yè)班的人也來湊熱鬧感受一下百度招聘。筆試題目有選擇題，編程題，系統(tǒng)設(shè) 計題三種類型。選擇題難度不是很大，但我太水了，很多基礎(chǔ)知識都不記得了，正則表達(dá) 式，shell編程～～～汗死，不說了，好多都是蒙的。 編程題有3題，第一題是找出字符串 的最長不重復(fù)子串，輸出長度。我想了半天，只會O(n^2)的算法，是個人都可以想出來的 笨辦法，想著寫下來也沒啥意義，題目問有沒O（n）的，那看來肯定有O（n）的，就不寫 了，看后面的題算了。第二題是找出一個字符串的最長回文子串。這個問題好像以前考研 復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)時看過，想起來判斷一個回文串可以用棧來實(shí)現(xiàn)，稍微回憶一下，算法思路 就出來了。于是提筆寫下了個O(n^3)的算法。汗死了，自己太笨了，只能想出這種垃圾算 法，看來百度不好混啊。第三題是在2.5億個整數(shù)中找出不重復(fù)的整數(shù)，內(nèi)存空間不足以容 納這2.5億個整數(shù)。這種題是百度的特色，海量數(shù)據(jù)處理，我也沒啥思路。既然不能一次扔 進(jìn)內(nèi)存，我就分批扔進(jìn)去，盡量減少從外存讀進(jìn)內(nèi)存的次數(shù)，然后算了一下，分2批扔進(jìn)內(nèi) 存。然后每批排序，找出每批里面不重復(fù)的數(shù)，把這些不重復(fù)的再在另一批數(shù)中過一遍，去掉重復(fù)的，然后匯總。寫不出具體代碼，只把思路寫了一下。當(dāng)時心情沮喪極了，想著，掛了，代碼不會寫，難得寫出一題又是效率極低的。最后那道系統(tǒng) 設(shè)計題，我壓根沒啥好思路，題目大概是海量數(shù)據(jù)分布在100臺電腦中，想個辦法高效統(tǒng)計 出這批數(shù)據(jù)的TOP10。草草寫了幾筆，時間就到了，交卷～～～看來，這次除非有奇跡，不 然筆試肯定被BS了。
考完回到寢室，和兄弟們討論一下題目，第一題原來可以用Hash實(shí)現(xiàn)，時間復(fù)雜度降 到O(n)。自己仔細(xì)想了一下，整個算法的思路就清晰了，郁悶啊，這么簡單的題居然沒想 出來，看來自己還是太菜了。ZZ對第二題還有個新穎的算法，學(xué)習(xí)了一下，贊啊，虧他想 得出來，呵呵。第二天還有Microsoft的筆試，趕緊拿Primer來抱抱佛腳，這么好的一本書 ，我學(xué)C++時怎么就沒看啊？后悔，懊惱充斥著我的大腦，大有相見恨晚的感覺。 雖然自己筆試很爛，但是還是寄希望于奇跡出現(xiàn)，能有機(jī)會去面試。于是晚上睡覺開著手機(jī)，因為座談會時百度說如果筆試通過，當(dāng)晚凌晨就會出面試通知了。晚上輾轉(zhuǎn)反側(cè) ，難以入睡，期待手機(jī)鈴聲響起，都不知道幾點(diǎn)才睡著。早上起床一照鏡子，大熊貓再現(xiàn)拉，唉，為百度消得我憔悴啊。自己空想也沒用，眼前還有MS等著我呢。考MS時，手機(jī)都沒關(guān)，就等著百度電話，希望考試時能有電話來。果然，早上11點(diǎn)多還在考試時，手機(jī)響起，掛掉，我還在為了MS筆試而撓頭呢。幾分鐘后，又響了一次，再次掛掉。考完試，出 考場拿手機(jī)一看，咦，是027的哦，好像是個小靈通。回?fù)埽煌ǎ^續(xù)回?fù)埽€是不通， 不死心，我就不信撥不通你。結(jié)果撥了10多次還是不通，算了，只好等他再打來。回實(shí)驗 室，上Q問問這個號碼是不是百度的，JG他們說是的，驚喜，Oh，yeah，百度面試來臨了， Miracle居然發(fā)生了。于是和JG，DJ，Q拼車去弘毅面百度。結(jié)果面官說我不接電話，他們安排了其它同學(xué)面試，叫我第二天早上10點(diǎn)再來面。FT，怎么這么曲折啊，不過給我點(diǎn)時 間復(fù)習(xí)準(zhǔn)備，也好。
【一面】 晚上好好看了一下項目，把重點(diǎn)溫習(xí)了一下。又問了下JG面試問了啥，心里有個底了 。第二天，一個人飛的去了弘毅，花了22大洋，好心疼啊。去到昨天那個房間，看見面官 了，一個光頭，和JG昨天的面官一樣。果然，他上來就問了我昨天問JG的同樣問題，設(shè)計 一種數(shù)據(jù)結(jié)構(gòu)，結(jié)合了鏈表和數(shù)組的優(yōu)點(diǎn)。我想了一下，說用Hash鏈表，這樣插入和查找 的效率都比較高，但是有conflict問題要解決。他馬上就問我如何解決conflict問題，有沒什么好方法。我說修改hash函數(shù)，使得hash值產(chǎn)生的conflict概率盡可能低。他問那你怎么設(shè)計？我倒，這個問題我可沒想過啊。當(dāng)場郁悶了，立馬陷入苦思狀態(tài)。想出幾個點(diǎn) 子，都不管是否可以降低conflict的概率，都和面官說了。他很快就舉例否定我好不容易 想出的點(diǎn)子，說你的辦法還是不行哦，有沒更好的？打擊死了，我已經(jīng)盡力了啊，沒想到這么快就被他找到反例，郁悶死我了。不過面官人很好，看我實(shí)在想不出更好的了，就不為難我了，換下一個題目。后面一題是海量日志數(shù)據(jù)，提取出某日訪問百度次數(shù)最多的那個IP。想了一下，說了個思路。面官就問你這樣需要的存儲空間太大，有沒優(yōu)化方法。看 來思路是正確的了，但是優(yōu)化問題嘛，好棘手啊。我又說了個優(yōu)化的方法，面官不太滿意，搖頭。完了，實(shí)在想不出來了。。。。面官見我苦思冥想，也不為難我了。接著就問了下項目經(jīng)驗，我balabala一通，他對我的項目不太感冒，沒問什么問題。 然后就問筆試卷子了，他問我第一題干嘛空白？我說了原因，他問我現(xiàn)在有好的想法 沒？我就把自己考完后想的O（n）的算法說了一下，他比較滿意，沒問我什么就問第二題 了。我又說了下我當(dāng)時的算法思想，他問有沒更好的優(yōu)化算法？我說可以做到O（n^2）， 把思路說了下。似乎不是他的滿意答案，也沒問我啥。接著問第三題，我把我的想法說了 。他說，你最后還需要折半查找這么麻煩嗎？對2個有序的數(shù)組，查找A數(shù)組的元素是否在 B數(shù)組中出現(xiàn)有沒更好的算法？我想了一下，突然靈機(jī)一動，想起歸并排序的算法。就說， 是不是像歸并數(shù)組那樣，直接在B中定位出A的位置，這樣就可以在O(m+n)內(nèi)實(shí)現(xiàn)。他比較滿意，說：“是啊，都有序了，你還折半這么麻煩啊？”暴汗，看來面官水平比我高太多了，思維跟不上。然后看面官總算露出點(diǎn)笑容，忍不住問句：“你覺得我這個算法可以接受不？”他的回答讓我很吃驚，他說：“當(dāng)然可以接受拉，我覺得挺好的啊，不過你的算法要訪外存，可能時間效率不是很高。不過先要完成題目的任務(wù)，再考慮優(yōu)化。”我趕緊補(bǔ)一句：“是啊，先要讓它work，再考慮如何讓它work better。”面官還來句：“不過這個題最好的算法可以一次把2.5億數(shù)據(jù)扔進(jìn)內(nèi)存，這需要你設(shè)計一個好的數(shù)據(jù)結(jié)構(gòu)。”我問：“這個，怎么設(shè)計哦？”面官表示不能告訴我答案，讓我自己回去想。 這時，面官看看表，我也看看表，已經(jīng)面了50分鐘了。他說：“現(xiàn)在我們再做2道數(shù)學(xué)推理題。第一題，2個盒子，容量足夠大，現(xiàn)在有50個紅球，50個藍(lán) 球，你如何安放這 些球進(jìn)盒子，使得我隨機(jī)抽取一個盒子，然后從里面隨機(jī)抽一個球，這個球是紅球的概率 最大？給你2分鐘時間考慮，直觀分析給出結(jié)果。”當(dāng)場我就暈倒了，從小到大，我都不會 做IQ題的啊，這可是我的最弱項。沒辦法，不能直接說我不會啊。只好硬著頭皮上，分析 一下，我說：“列條概率的表達(dá)式，求最值，可以求出結(jié)果。”他說：“你這樣搞2個小時 都算不出結(jié)果。從直觀上分析就可以知道結(jié)果了。你再想想”，被打擊了。只好繼續(xù)想， 我想，那把50個紅球放到一個盒子，另一個盒子全放藍(lán)球，這樣一個有100％，另一個是0 ％，平均下來有50％。也不理想啊，這個時候，靈感再次突現(xiàn)，50個紅球全放一個盒子不 是浪費(fèi)嘛？放1個也是100％，2個也是100%，那就放一個好了，其它全部扔到另一個盒子和 藍(lán)球一起。再想一下，這樣概率有75％，應(yīng)該很高了。也沒仔細(xì)想是不是正確答案，就脫 口而出，說了這種放法。面官再次露出笑容，說“正確！”我那時心里好激動啊，沒想到 運(yùn)氣這么好，居然還答對了。接著又來下一題，A射擊命中率80%,B60%,C40%，A,B,C互為競爭對手，每人都知道另外2人的命中率，3個人同場 競技互相射擊，同時開了第一槍，問第一槍射后，誰最有可能掛掉？我分析了一下，說了答案，他問我思路，我說了我的思路后，他居然來句：“你的思維和別人不 一樣。”FT，我和別人不一樣，估計說錯了，自己確實(shí)回答IQ題比別人笨一截，沒辦法。面官說：“好了，時間差不多了。你有什么問題問我不？”我問：“如 果我有幸通過一面，什么時候會二面？”“通過的話，明早就二面。”然后，和面官握了下手，就這樣結(jié)束了我的一面。 面完一面后，去找LP吃飯，下午陪她上自習(xí)，感覺自己一面還行吧，大部分題都答出了思路，雖然進(jìn)一步的優(yōu)化沒有想完整，而且運(yùn)氣也好得不得了，連最后2題居然還被我蒙對1題，如果進(jìn)不了2面，只能說明自己離百度的要求還是差距太大了。結(jié)果好運(yùn)再次降臨，晚上6點(diǎn)多接到電話，通知第二天早上10點(diǎn)去二面，呵呵，竟然進(jìn)了二面，真是 too lucky。
【二面】 第二天準(zhǔn)時去到面試房間，換了位面官面我。一上來就問我一道海量數(shù)據(jù)處理題。題目是：很多記錄數(shù)據(jù)，有ID號，還有幾個不同的屬性域，現(xiàn)在要根據(jù)ID號高速查詢到對應(yīng) ID號的數(shù)據(jù)，設(shè)計個算法。然后，現(xiàn)在要根據(jù)特定的屬性域排序查詢，既要高效找到排名 在第N-M名的記錄，還要經(jīng)常插入，刪除記錄。我說，查詢ID可以用Hash表查詢，把ID號hash，然后可以在O(1)查到對應(yīng)的記錄。第二個問題，有點(diǎn)復(fù)雜，類似于結(jié)合數(shù)組和鏈表的優(yōu)點(diǎn)設(shè)計數(shù)據(jù)結(jié)構(gòu)。我說了好幾種方案，問他這樣行不行。他說：“你自己覺得行不行啊 ，現(xiàn)在是我面你，不是你面我啊，你自己考慮答案啊。”暈倒，我實(shí)在想不出更好的，也 不知道應(yīng)該如何抉擇，備選方案都各有優(yōu)缺點(diǎn)啊。最后，還是選了其中一種，回答了這個 問題。面官說：“其實(shí)這個問題很難有最佳方案，就看你怎么選擇，權(quán)衡，選一種較好的 方案。”唉，也不知道我的答案可不可以接受，完全沒了一面時的靈感了。然后面官看了 下我簡歷，驚訝地說道：“你是武漢理工畢業(yè)的？”我也很驚訝：“你聽說過這個學(xué)校？ ”因為我感覺，武漢理工又不是很有名，在北方，連華中科技名氣都不是很響，沒想到面 官竟然知道武漢理工。結(jié)果面官說：“我就是武漢理工畢業(yè)的啊。”一聽，心中竊喜，居然還有校友，趕緊套一下親近。問他哪一級的，什么時候畢業(yè)啊，加入百度多久了之類的問題。然后自己又說了一下個人對武漢理工的感覺，尤其是當(dāng)年放棄保研名額，選擇去考研。他聽著也覺得有點(diǎn)意思，我就繼續(xù)說：“覺得學(xué)習(xí)氛圍很重要，身邊的同學(xué)對自己的影響很大。本科時，很多同學(xué)沉溺于網(wǎng)游，都墮落了，自己想找個人討論問題都沒有。現(xiàn)在去了華中科技，身邊的同學(xué)都很優(yōu)秀，經(jīng)常和同學(xué)討論問題，一起進(jìn)步，感覺很好。”他聽了后點(diǎn)點(diǎn)頭，說：“你這個決定挺正確的。......blabala一通，他也不感冒。他又問我：“干嘛想加入百度公司？”我說：“自己對互聯(lián)網(wǎng)技術(shù)很感興趣，從本科起對數(shù)據(jù)結(jié)構(gòu)和算法就有濃厚的興趣。 加上自己將來想搞研發(fā)，百度公司的技術(shù)很吊，里面的人很強(qiáng)，加入百度可以得到很好的鍛煉，學(xué)到很多東西。百度公司現(xiàn)在發(fā)展很快，對自己的職場生涯很有幫助。”然后，他問我：“你對搜索引擎了解不？”我說：“之前不了解，聽了座談會后了解了一些。”他又問：“你對自然語言分析處理了解不？”“不懂”說完， 我汗死了，完全不懂，有點(diǎn)不祥的預(yù)感了。誰知道，更郁悶的事還在后頭。他接著來一句：“你做的項目都是網(wǎng)絡(luò)安全方面的，和我們的活不對口啊？”最讓我擔(dān)心 的事終于發(fā)生了，我故作鎮(zhèn)定說：“恩，既有網(wǎng)絡(luò)安全，也有網(wǎng)絡(luò)應(yīng)用和管理方面的。”然后面官就說：“好了，我的問題差不多了，你有什么問題要問嗎？”我看了下表，倒，才面了30分鐘就沒問題了，看來我方向不對口，他對我已經(jīng)沒興趣了，不行，這樣草草了結(jié)，二面肯定掛掉了，得扯點(diǎn)他感興趣的問題才行。馬上把自己本科的那個畢業(yè)設(shè)計網(wǎng)絡(luò)五子棋里面涉及的算法問題拿出來問問他，看看他有什么優(yōu)化的方法。他想了一會，說：“這個問題有點(diǎn)復(fù)雜哦。”我竊喜，哈哈，該不會把你難倒了吧？接著他來句：“你當(dāng)時是怎么做的？”我心想，你還真行，把問題又丟回來給我了。我就說了我當(dāng)時的做法，也得到了他的認(rèn)可和贊許。恩，第一步目標(biāo)達(dá)成。 然后又問他我投的那個職位對哪方面的要求比較高？他說：“良好的算法和數(shù)據(jù)結(jié)構(gòu)的基 礎(chǔ)最重要。”我又問：“那數(shù)據(jù)庫，腳本語言，網(wǎng)絡(luò)編程方面呢？”這些都是我的弱項哦 。他說：“這些都有很多現(xiàn)成的成果可以直接利用了，算法和數(shù)據(jù)結(jié)構(gòu)可能比較難提高， 所以需要有個良好的基礎(chǔ)才行。”聽完，心里有點(diǎn)高興，自己的強(qiáng)項就是算法和數(shù)據(jù)結(jié)構(gòu) 方面，既然弱項不是很重要，那看來對我的影響不大。這又讓我想起李開復(fù)的一句話：“ 你進(jìn)MS時，懂C＃很好，不懂也不要緊，來了可以學(xué)。但是如果你不懂得如何學(xué)習(xí)，那就糟 糕了。”看來，基礎(chǔ)和學(xué)習(xí)能力是很多大公司所看重得。然后又和面官聊一下武漢理工的 變化，和在華中科技讀研的一些生活。最后，面官說了句：“其實(shí)，你的技術(shù)還是不錯的 。”聽了這句后，很高興，但是自己對搜索引擎的不了解和專業(yè)的不對口又讓自己產(chǎn)生一絲隱憂。最后問了下“還會有3面不？”“Maybe。”和面官say goodbye，然后結(jié)束了二面。
【后記】 二面后就是漫長的等待（其實(shí)也就等了6天而已，但是自己已經(jīng)覺得很漫長了）。期間沒有任何消息，BBS說二面過了就發(fā)offer，二面不過就去三面。對這個說法，我持保留意見，身邊很多大牛都去3面了，3面是非技術(shù)面，都問你期望的月薪的，自己覺得應(yīng)該是過了2面的才有3面機(jī)會吧。自己一直沒等來3面的電話通知，已經(jīng)覺得自己掛了。期間找 LP訴苦，她安慰我說：“說不定就像BBS說的那樣，二面過了就不用三面了吧。你干著急也沒用啊，好好復(fù)習(xí)等消息吧。”雖然是安慰我的話，但是在等待的日子里有個人可以訴苦感覺還是挺好的。聯(lián)系了一下內(nèi)推的那個人，他說他也不知道結(jié)果，問我是誰面我的。我說一面是光頭，把二面面官的名字報了一下。他說：“光頭是他們部門經(jīng)理。”我很驚訝 ，啊？部門經(jīng)理？看不出來啊，既然部門經(jīng)理都讓我過1面了，應(yīng)該機(jī)會還挺大的啊，自我感覺一面比二面好多了。每天逛BBS，不僅看白云，還看珞珈山水，交大思源，還有天大求 實(shí)。等待真是種煎熬啊，雖然各方面的信息都是朝著不利的一面發(fā)展，但是自己還是不死心，一天沒發(fā)offer，就還有機(jī)會；既然沒發(fā)據(jù)信，那就還有希望。等啊等，終于在國慶前 一天發(fā)offer了，居然自己也有！ 回顧這次百度之旅，感覺運(yùn)氣太好了。一面是部門經(jīng)理，其實(shí)過了他這關(guān)基本問題就不大了。恰好自己那天狀態(tài)超好，靈感不時出現(xiàn)，臨場超水平發(fā)揮，總算過了第一關(guān)。第二關(guān)在形勢很不利的情況下（連說幾個“不懂”），自己給自己找加分項目，朝著職位的要求往上靠。既然算法和數(shù)據(jù)結(jié)構(gòu)要求高，我就要表現(xiàn)出自己這個方面有優(yōu)勢，扯畢業(yè)設(shè) 計的算法設(shè)計和面官聊，表示自己對這方面有興趣，基礎(chǔ)不差。還有突出一下自己其它方 面的優(yōu)點(diǎn)，例如上進(jìn)，好學(xué)，對技術(shù)有偏執(zhí)（百度系統(tǒng)部老大的經(jīng)典說法）等。覺得面試時還有一點(diǎn)做得不錯的就是，當(dāng)面對一個自己沒什么思路的問題時，只要你有什么新想法 ，不要管這個想法是否可行，是否可以真的解決問題，先把它說給面官聽，讓他覺得你的 思考問題的能力還是很強(qiáng)的。一定不要想了半天，結(jié)果說“不知道”這樣面官對你的印象 就會很差。雖然你的idea可能不是很work,但是只要是朝著正確的方向前進(jìn)就OK拉，面試官會給你一定的指引的。你繼續(xù)朝著那個方向想，說不定很快就可以解決問題了。 以前都是看別人的面經(jīng)，獲益良多，這次自己寫寫筆經(jīng)，面經(jīng)，希望對大家有幫助。 最后，希望大家都能找到自己滿意的工作，其實(shí)付出和收獲真是成正比的。可以從事自己 喜歡的工作，真是很高興。目標(biāo)和準(zhǔn)備方向的正確可能是我這次應(yīng)聘成功的最主要因素之一吧。我投簡歷只投研發(fā)的崗位，對不搞技術(shù)的公司壓根沒投，不管公司有多大有多好， 像P&G，MARS，國企，公務(wù)員等。一來不想占用別人的機(jī)會，二來也知道自己更適合在技術(shù) 方面發(fā)展，去非技術(shù)類公司自己的發(fā)展可能不如技術(shù)類公司。呵呵，寫得我好累啊，就寫到這吧，希望能對大家有用。