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