原文鏈接：
一面：面試官很清瘦，個(gè)頭很高。后來(lái)發(fā)現(xiàn)人很nice，很隨和~,至少面試過(guò)程中讓人感覺很舒服。一些我回答出來(lái)的問題可能記憶的不是很清楚了，主要記錄一些我答的不是很好的問題。首先自我介紹，不過(guò)剛剛開始就被打斷開始進(jìn)行詢問了，從課程至項(xiàng)目，聊了很多，面試官在百度的職位or他隸屬于的部門屬于百度的框架開發(fā)類職位，及相對(duì)于策略類的一個(gè)職位。無(wú)論我的課程或者經(jīng)歷其實(shí)對(duì)于框架開發(fā)類職位比較不足，比較偏策略一些。不過(guò)繼續(xù)面試嘛，我興趣廣泛，針對(duì)這個(gè)也很感興趣的~
1.linux多線程編程的知識(shí)，這個(gè)答的不是很好，因?yàn)樽约捍_實(shí)基本沒寫過(guò)多線程的知識(shí)，只是并行程序設(shè)計(jì)利用MPI實(shí)現(xiàn)過(guò)簡(jiǎn)單的算法，概念知識(shí)不是很了解，所以針對(duì)linux多線程編程知識(shí)還需要補(bǔ)充一下。當(dāng)時(shí)一個(gè)問題就是鎖的類型？
2.linux中文件描述符FD的概念？當(dāng)時(shí)想不到是什么，然后面試官提示了一下，0,1,2，就想到了命令行中經(jīng)常用到1,2就答了一下才了解到平時(shí)用到的這些就是文件描述符，自己卻不知道概念。
標(biāo)準(zhǔn)輸入（standard input）的文件描述符是 0，標(biāo)準(zhǔn)輸出（standard output）是 1，標(biāo)準(zhǔn)錯(cuò)誤（standard error）是 2。
3.因?yàn)槭撬阉鞴?，所以面試官讓我描述一下整個(gè)搜索引擎的過(guò)程，包括用戶提交query之后的一系列工作，這部分概念缺失很多，答的很差。準(zhǔn)備面試一家搜索公司，而且在搜索公司實(shí)習(xí)過(guò)一段時(shí)間，竟然無(wú)法完整答出這個(gè)問題，其實(shí)挺糟的。
這個(gè)搜索一下比較好的架構(gòu)~最好針對(duì)已經(jīng)有的開源項(xiàng)目分析其框架最好。針對(duì)我可能分析一下Nutch和Solr比較好。
4.針對(duì)數(shù)組A和數(shù)組B，兩個(gè)數(shù)組的元素內(nèi)容相同，不過(guò)數(shù)組A是已經(jīng)排序的，數(shù)組B是亂序的，針對(duì)數(shù)組的中位數(shù)，存在以下兩組程序，比較其效率并分析原因。
程序見原鏈接
這個(gè)題目之前在網(wǎng)上瀏覽到過(guò)，知道有序的數(shù)組的效率其實(shí)比無(wú)序的要高很多，但是原因?qū)嵲谙氩怀鰜?lái)。現(xiàn)在搜一下，原來(lái)是stackoverflow上面的經(jīng)典問答呢，原因不是編譯器動(dòng)手腳，而是CPU動(dòng)的手腳，CPU有一個(gè)叫分支預(yù)測(cè)的技術(shù)，是這個(gè)技術(shù)導(dǎo)致有序數(shù)組的效率很高。 CPU指令執(zhí)行的過(guò)程是流水線，簡(jiǎn)單的分支預(yù)測(cè)方案是針對(duì)當(dāng)前元素判斷下一個(gè)元素的指令跳轉(zhuǎn)方向，有序的話分支預(yù)測(cè)的準(zhǔn)確率很高，無(wú)序的話分支預(yù)測(cè)技術(shù)就不生效了，無(wú)法提前裝載指令進(jìn)入流水線，這樣就損耗了一定的CPU時(shí)間。
5.虛擬析構(gòu)函數(shù)的應(yīng)用場(chǎng)景。
當(dāng)時(shí)答的是指向父類的指針實(shí)際指的子類對(duì)象，delete的時(shí)候需要調(diào)用子類析構(gòu)函數(shù)！這是唯一應(yīng)用場(chǎng)景！當(dāng)時(shí)多嘴答了一下引用也可。其實(shí)引用必須顯示創(chuàng)建對(duì)象，這樣編譯器就會(huì)自動(dòng)調(diào)用其析構(gòu)函數(shù)，所以不屬于這一應(yīng)用場(chǎng)景，即使指針和引用均可完成多態(tài)。
實(shí)驗(yàn)實(shí)例：見原鏈接
6.STL中l(wèi)ist的底層實(shí)現(xiàn)？雙鏈表，因?yàn)榭梢郧斑M(jìn)后退。STL中的deque的默認(rèn)使用容器？其實(shí)當(dāng)時(shí)不太確定，思考了一下，猜了一下vector，因?yàn)楹芏嗳萜髂J(rèn)容器均使用vector。當(dāng)時(shí)如果問我deque的底層實(shí)現(xiàn)就好了，這個(gè)我更加了解-_-。
7.vector的insert和erase操作，這個(gè)也不是很熟悉，但是屬于連續(xù)空間的插入和刪除，必須做內(nèi)存的調(diào)整~，翻看一下STL源碼具體的實(shí)現(xiàn)。
8.兩個(gè)簡(jiǎn)單的算法題目，時(shí)間比較急，代碼寫的比較冗余。
a.一個(gè)數(shù)組中只有一個(gè)數(shù)字出現(xiàn)1次，其他數(shù)字出現(xiàn)兩次。
挺簡(jiǎn)單的題目，因?yàn)橐娺^(guò)，所以就跳過(guò)了這個(gè)題目，所以元素異或即可。
b.一個(gè)m*n得棋盤，每個(gè)格子中有一個(gè)數(shù)字，計(jì)算從左上角至右下角的最大路徑和，每一步行只能夠向右或者向下行走。
一個(gè)簡(jiǎn)單的動(dòng)態(tài)規(guī)劃題目，第一種方法首先時(shí)間復(fù)雜度O(mn）空間復(fù)雜度O(mn）的寫了代碼，代碼有些長(zhǎng)，后來(lái)改進(jìn)了一個(gè)時(shí)間復(fù)雜度O(mn）空間復(fù)雜度O(min(m,n))的算法，后來(lái)面試官問如果需要還原路徑如何做？采用O(mn）的額外空間記錄每個(gè)單元走的路徑即可。
面試總結(jié)：算法題目其實(shí)挺簡(jiǎn)單的，只不過(guò)很多基礎(chǔ)知識(shí)不夠牢固，比如linux的一些基礎(chǔ)知識(shí)（復(fù)習(xí)下《鳥哥linux私房菜》），多線程的編程知識(shí)（學(xué)習(xí)下《posix多線程程序設(shè)計(jì)》并簡(jiǎn)單實(shí)踐一下），STL的知識(shí)和C++的知識(shí)也仍然需要鞏固復(fù)習(xí)（STL源碼剖析，Effective C++，More Effective C++，深度探索C++對(duì)象模型一本書內(nèi)容還是挺晦澀的，還是要拜讀一下，面試的時(shí)候雖然可能不涉及這么深入的知識(shí)，但是還是要繼續(xù)學(xué)習(xí)），另外就是盡可能的逛一些技術(shù)社區(qū)，看一些東西了。因?yàn)橄裼行?，無(wú)序數(shù)組那個(gè)題目，感覺完全是技術(shù)視野的問題，看到了就會(huì)，沒看到怎么能夠想到是CPU的優(yōu)化，我都以為是編譯器的優(yōu)化，答題方向都掌握錯(cuò)了。
二面：二面的面試官相對(duì)于一面的面試官不是那么的健談，更多的是讓我去說(shuō)，他去加一些提醒，然后我繼續(xù)的回答。不過(guò)面試官也很nice，因?yàn)榇痤}的過(guò)程當(dāng)中給了我很多的引導(dǎo)，因?yàn)轭}目我答的都不是很完善T_T!
1.首先是問一個(gè)大數(shù)據(jù)處理的題目，兩個(gè)URL文件，分別有20億條記錄，每個(gè)URL的項(xiàng)目大約1KB。文件中有重復(fù)的URL記錄，如何去除重復(fù)？
因?yàn)樵谝幻娴倪^(guò)程中了解到，有序的數(shù)組去除重復(fù)的時(shí)候能夠得到快速的去重，所以就考慮到了首先排序，但是兩個(gè)這么大的文件單機(jī)排序？外部排序，k路歸并排序，然后面試官就順勢(shì)的問了我k路歸并排序的知識(shí)，k路歸并排序的時(shí)間估計(jì)，因?yàn)閗路歸并排序很多時(shí)間在磁盤的IO上面，所以我猜測(cè)可能磁盤的IO才是時(shí)間的平靜，每個(gè)元素最終進(jìn)出磁盤4次，所以我估計(jì)的方法是元素?cái)?shù)量*4*磁盤IO平均時(shí)間。不知道這個(gè)方法對(duì)不對(duì)。
多機(jī)的擴(kuò)展，MapReduce程序應(yīng)該可以完成，但是我對(duì)hadoop不是很了解（所以這個(gè)方法沒有答）。自己想一下多機(jī)的擴(kuò)展吧，當(dāng)然也是分治，想想也可以多機(jī)k路歸并排序，后來(lái)面試官引導(dǎo)我說(shuō)可以不排序么？我才意識(shí)到原始問題只是為了去除重復(fù)，所以這里分治并且利用hash的方法應(yīng)該能夠達(dá)到很快速的算法（復(fù)習(xí)一下《大型網(wǎng)站架構(gòu)》這本書）一致性simhash方法應(yīng)該是解決這個(gè)問題的。
2.設(shè)計(jì)模式，單例設(shè)計(jì)模式的深入討論。（復(fù)習(xí)《head first》設(shè)計(jì)模式）
a.單例設(shè)計(jì)模式的應(yīng)用場(chǎng)景？
b.單例模式的代碼（白紙代碼）？
c.多線程安全的單例模式代碼（需要加鎖）？
d.如何實(shí)現(xiàn)一個(gè)高效的線程安全的單例模式代碼？（存在不加鎖的解決方案嗎？）
3.簡(jiǎn)單的聊了項(xiàng)目之后就問了一個(gè)算法題目。中國(guó)象棋中帥，將和一個(gè)將身邊的士，輸出其合理位置的方案。
剛看到這個(gè)算法題目的時(shí)候還卡了一下，不過(guò)后來(lái)自己把棋盤編號(hào)為1,2,3,4,5,6,7,8,9之后豁然開朗~不過(guò)我的代碼if，else比較多，3類情況枚舉，后來(lái)在面試官的提示下進(jìn)行條件合并，節(jié)省了很多的代碼。
程序見原鏈接
面試總結(jié)：對(duì)于系統(tǒng)設(shè)計(jì)海量數(shù)據(jù)的題目還是要準(zhǔn)備的，還是需要復(fù)習(xí)《大型網(wǎng)站架構(gòu)》一書，書中講述了很多海量數(shù)據(jù)處理的知識(shí)。學(xué)習(xí)下july的博客，了解一些常用的方法。另外就是設(shè)計(jì)模式中單例模式的掌握一定要非常的熟悉，不要讓面試官不斷的提醒修正錯(cuò)誤，這樣會(huì)引出更多的問題，我這次面試就是，雖然及時(shí)的修正問題，但是都能夠引出其他的問題，比如講一下線程和進(jìn)程？雖然這個(gè)問題比較普通，但是這種引出其他問題還是盡量避免。
三面：這一面真是等了一個(gè)下午，12：30-4:20這個(gè)過(guò)程真是等待的很漫長(zhǎng)，腦袋都秀逗了，面試官下午來(lái)了之后感覺就是聊天了，也沒有針對(duì)我問一些技術(shù)問題，主要問了實(shí)習(xí)的一些工作，簡(jiǎn)單的聊了半個(gè)小時(shí)就結(jié)束了，也沒有說(shuō)后續(xù)的消息。不知道是不是還有后續(xù)，反正面試官還是很詳細(xì)的描述了一下百度的情況，也很認(rèn)真的解答了我問的幾個(gè)關(guān)于百度的問題。當(dāng)時(shí)也不好意思去問后續(xù)消息，就回來(lái)了。T_T。
