原文鏈接：
一面：面試官很清瘦拒担，個頭很高兴喂。后來發(fā)現(xiàn)人很nice，很隨和~,至少面試過程中讓人感覺很舒服。一些我回答出來的問題可能記憶的不是很清楚了嘱腥，主要記錄一些我答的不是很好的問題耕渴。首先自我介紹，不過剛剛開始就被打斷開始進(jìn)行詢問了齿兔，從課程至項目橱脸，聊了很多，面試官在百度的職位or他隸屬于的部門屬于百度的框架開發(fā)類職位分苇，及相對于策略類的一個職位添诉。無論我的課程或者經(jīng)歷其實對于框架開發(fā)類職位比較不足，比較偏策略一些医寿。不過繼續(xù)面試嘛栏赴，我興趣廣泛，針對這個也很感興趣的~
1.linux多線程編程的知識靖秩，這個答的不是很好须眷，因為自己確實基本沒寫過多線程的知識竖瘾，只是并行程序設(shè)計利用MPI實現(xiàn)過簡單的算法，概念知識不是很了解花颗，所以針對linux多線程編程知識還需要補(bǔ)充一下捕传。當(dāng)時一個問題就是鎖的類型？
2.linux中文件描述符FD的概念扩劝？當(dāng)時想不到是什么庸论，然后面試官提示了一下，0,1,2棒呛，就想到了命令行中經(jīng)常用到1,2就答了一下才了解到平時用到的這些就是文件描述符聂示，自己卻不知道概念。
標(biāo)準(zhǔn)輸入（standard input）的文件描述符是 0条霜，標(biāo)準(zhǔn)輸出（standard output）是 1催什，標(biāo)準(zhǔn)錯誤（standard error）是 2。
3.因為是搜索公司宰睡，所以面試官讓我描述一下整個搜索引擎的過程蒲凶，包括用戶提交query之后的一系列工作，這部分概念缺失很多拆内，答的很差旋圆。準(zhǔn)備面試一家搜索公司，而且在搜索公司實習(xí)過一段時間麸恍，竟然無法完整答出這個問題灵巧，其實挺糟的。
這個搜索一下比較好的架構(gòu)~最好針對已經(jīng)有的開源項目分析其框架最好抹沪。針對我可能分析一下Nutch和Solr比較好刻肄。
4.針對數(shù)組A和數(shù)組B，兩個數(shù)組的元素內(nèi)容相同融欧，不過數(shù)組A是已經(jīng)排序的敏弃，數(shù)組B是亂序的，針對數(shù)組的中位數(shù)噪馏，存在以下兩組程序麦到，比較其效率并分析原因。
程序見原鏈接
這個題目之前在網(wǎng)上瀏覽到過欠肾，知道有序的數(shù)組的效率其實比無序的要高很多瓶颠，但是原因?qū)嵲谙氩怀鰜怼，F(xiàn)在搜一下刺桃，原來是stackoverflow上面的經(jīng)典問答呢粹淋，原因不是編譯器動手腳，而是CPU動的手腳，CPU有一個叫分支預(yù)測的技術(shù)廓啊，是這個技術(shù)導(dǎo)致有序數(shù)組的效率很高欢搜。 CPU指令執(zhí)行的過程是流水線，簡單的分支預(yù)測方案是針對當(dāng)前元素判斷下一個元素的指令跳轉(zhuǎn)方向谴轮，有序的話分支預(yù)測的準(zhǔn)確率很高炒瘟，無序的話分支預(yù)測技術(shù)就不生效了，無法提前裝載指令進(jìn)入流水線第步，這樣就損耗了一定的CPU時間疮装。
5.虛擬析構(gòu)函數(shù)的應(yīng)用場景。
當(dāng)時答的是指向父類的指針實際指的子類對象粘都，delete的時候需要調(diào)用子類析構(gòu)函數(shù)廓推！這是唯一應(yīng)用場景！當(dāng)時多嘴答了一下引用也可翩隧。其實引用必須顯示創(chuàng)建對象樊展，這樣編譯器就會自動調(diào)用其析構(gòu)函數(shù)，所以不屬于這一應(yīng)用場景堆生，即使指針和引用均可完成多態(tài)专缠。
實驗實例：見原鏈接
6.STL中l(wèi)ist的底層實現(xiàn)？雙鏈表淑仆，因為可以前進(jìn)后退涝婉。STL中的deque的默認(rèn)使用容器？其實當(dāng)時不太確定蔗怠，思考了一下墩弯，猜了一下vector，因為很多容器默認(rèn)容器均使用vector寞射。當(dāng)時如果問我deque的底層實現(xiàn)就好了渔工，這個我更加了解-_-。
7.vector的insert和erase操作桥温，這個也不是很熟悉引矩，但是屬于連續(xù)空間的插入和刪除，必須做內(nèi)存的調(diào)整~策治，翻看一下STL源碼具體的實現(xiàn)脓魏。
8.兩個簡單的算法題目兰吟，時間比較急通惫，代碼寫的比較冗余。
a.一個數(shù)組中只有一個數(shù)字出現(xiàn)1次混蔼，其他數(shù)字出現(xiàn)兩次履腋。
挺簡單的題目，因為見過，所以就跳過了這個題目遵湖，所以元素異或即可悔政。
b.一個m*n得棋盤，每個格子中有一個數(shù)字延旧，計算從左上角至右下角的最大路徑和谋国，每一步行只能夠向右或者向下行走。
一個簡單的動態(tài)規(guī)劃題目迁沫，第一種方法首先時間復(fù)雜度O(mn）空間復(fù)雜度O(mn）的寫了代碼芦瘾，代碼有些長，后來改進(jìn)了一個時間復(fù)雜度O(mn）空間復(fù)雜度O(min(m,n))的算法集畅，后來面試官問如果需要還原路徑如何做近弟？采用O(mn）的額外空間記錄每個單元走的路徑即可。
面試總結(jié)：算法題目其實挺簡單的挺智，只不過很多基礎(chǔ)知識不夠牢固祷愉，比如linux的一些基礎(chǔ)知識（復(fù)習(xí)下《鳥哥linux私房菜》），多線程的編程知識（學(xué)習(xí)下《posix多線程程序設(shè)計》并簡單實踐一下）赦颇，STL的知識和C++的知識也仍然需要鞏固復(fù)習(xí)（STL源碼剖析二鳄，Effective C++，More Effective C++沐扳，深度探索C++對象模型一本書內(nèi)容還是挺晦澀的泥从，還是要拜讀一下，面試的時候雖然可能不涉及這么深入的知識沪摄，但是還是要繼續(xù)學(xué)習(xí)）躯嫉，另外就是盡可能的逛一些技術(shù)社區(qū)，看一些東西了杨拐。因為像有序祈餐，無序數(shù)組那個題目，感覺完全是技術(shù)視野的問題哄陶，看到了就會帆阳，沒看到怎么能夠想到是CPU的優(yōu)化，我都以為是編譯器的優(yōu)化屋吨，答題方向都掌握錯了蜒谤。
二面：二面的面試官相對于一面的面試官不是那么的健談，更多的是讓我去說至扰，他去加一些提醒鳍徽，然后我繼續(xù)的回答。不過面試官也很nice敢课，因為答題的過程當(dāng)中給了我很多的引導(dǎo)阶祭，因為題目我答的都不是很完善T_T!
1.首先是問一個大數(shù)據(jù)處理的題目绷杜，兩個URL文件，分別有20億條記錄濒募，每個URL的項目大約1KB鞭盟。文件中有重復(fù)的URL記錄，如何去除重復(fù)瑰剃？
因為在一面的過程中了解到齿诉，有序的數(shù)組去除重復(fù)的時候能夠得到快速的去重，所以就考慮到了首先排序晌姚，但是兩個這么大的文件單機(jī)排序鹃两？外部排序，k路歸并排序舀凛，然后面試官就順勢的問了我k路歸并排序的知識俊扳，k路歸并排序的時間估計，因為k路歸并排序很多時間在磁盤的IO上面猛遍，所以我猜測可能磁盤的IO才是時間的平靜馋记，每個元素最終進(jìn)出磁盤4次，所以我估計的方法是元素數(shù)量*4*磁盤IO平均時間懊烤。不知道這個方法對不對梯醒。
多機(jī)的擴(kuò)展，MapReduce程序應(yīng)該可以完成腌紧，但是我對hadoop不是很了解（所以這個方法沒有答）茸习。自己想一下多機(jī)的擴(kuò)展吧，當(dāng)然也是分治壁肋，想想也可以多機(jī)k路歸并排序号胚，后來面試官引導(dǎo)我說可以不排序么？我才意識到原始問題只是為了去除重復(fù)浸遗，所以這里分治并且利用hash的方法應(yīng)該能夠達(dá)到很快速的算法（復(fù)習(xí)一下《大型網(wǎng)站架構(gòu)》這本書）一致性simhash方法應(yīng)該是解決這個問題的猫胁。
2.設(shè)計模式，單例設(shè)計模式的深入討論跛锌。（復(fù)習(xí)《head first》設(shè)計模式）
a.單例設(shè)計模式的應(yīng)用場景弃秆？
b.單例模式的代碼（白紙代碼）？
c.多線程安全的單例模式代碼（需要加鎖）髓帽？
d.如何實現(xiàn)一個高效的線程安全的單例模式代碼菠赚？（存在不加鎖的解決方案嗎？）
3.簡單的聊了項目之后就問了一個算法題目郑藏。中國象棋中帥衡查，將和一個將身邊的士，輸出其合理位置的方案译秦。
剛看到這個算法題目的時候還卡了一下峡捡，不過后來自己把棋盤編號為1,2,3,4,5,6,7,8,9之后豁然開朗~不過我的代碼if，else比較多筑悴，3類情況枚舉们拙，后來在面試官的提示下進(jìn)行條件合并，節(jié)省了很多的代碼阁吝。
程序見原鏈接
面試總結(jié)：對于系統(tǒng)設(shè)計海量數(shù)據(jù)的題目還是要準(zhǔn)備的砚婆，還是需要復(fù)習(xí)《大型網(wǎng)站架構(gòu)》一書，書中講述了很多海量數(shù)據(jù)處理的知識突勇。學(xué)習(xí)下july的博客装盯，了解一些常用的方法。另外就是設(shè)計模式中單例模式的掌握一定要非常的熟悉甲馋，不要讓面試官不斷的提醒修正錯誤埂奈，這樣會引出更多的問題，我這次面試就是定躏，雖然及時的修正問題账磺，但是都能夠引出其他的問題，比如講一下線程和進(jìn)程痊远？雖然這個問題比較普通垮抗，但是這種引出其他問題還是盡量避免。
三面：這一面真是等了一個下午碧聪，12：30-4:20這個過程真是等待的很漫長冒版，腦袋都秀逗了，面試官下午來了之后感覺就是聊天了逞姿，也沒有針對我問一些技術(shù)問題辞嗡，主要問了實習(xí)的一些工作，簡單的聊了半個小時就結(jié)束了滞造，也沒有說后續(xù)的消息欲间。不知道是不是還有后續(xù)，反正面試官還是很詳細(xì)的描述了一下百度的情況断部，也很認(rèn)真的解答了我問的幾個關(guān)于百度的問題猎贴。當(dāng)時也不好意思去問后續(xù)消息，就回來了蝴光。T_T她渴。
