職位類型：程序員
面試地點(diǎn)：北京
招聘公司：奇虎360

現(xiàn)在這大環(huán)境也不好，找工作這么難，找個好工作就跟難了，但是我相信，只要你有真本事，就不會發(fā)愁找工作滴！最近我就開始想我向往的公司發(fā)出了求職信，并且成功獲得了面試邀請，所以現(xiàn)在先讓我們一起看看面試問題吧。

一面主要是考察算法和數(shù)據(jù)結(jié)構(gòu)，難度因面試官而異。聽同學(xué)說他一面的時候，面試官就讓他寫了個堆排序，然后就是不聽地問項目，感覺很輕松。我就沒那么好運(yùn)了，至少問了五六個算法，還好hold住。

1.寫個快速排序吧。
答：這個算是基本功吧，對于想要互聯(lián)網(wǎng)公司offer的筒子們，最基本的幾個排序都得做到能隨時隨地手寫代碼，而且不出錯。手寫代碼也是對基本功的考察，千萬不要覺得能在電腦上寫代碼就ok了，記住，一定要在白紙上寫下來，你才能確定你會寫。

2.IP的有效值是1.0.0.1~255.255.255.255，寫個程序，參數(shù)是一個char*的IP，返回這個IP是否合法。

答：這題在考察程序員對邊界條件的考慮。至少有以下幾點(diǎn)是要考慮到的：1.IP超過或不足四位；2.某一位超過了合法范圍；3.某一位除了數(shù)字，還包含了其他非法符號。這一題可以使用strtok取出IP的每一位，然后檢查該位是否合法(數(shù)值范圍，是否包含非法字符)，最后檢查是否有四位。

3.一個字符串?dāng)?shù)組char *A[]={"China"，"Chinese"，"Chese"，...}，求這個數(shù)組中字符串的最長公共前綴，例如這三個字符串的最長公共前綴是Ch。

答：使用字典樹，類似的問題還有給你一些QQ號，讓你求這些QQ號的最長公共前綴。字典樹大家可以去網(wǎng)上搜一搜。

4.求兩個字符串的最大公共子串，例如"abcdefg"和"zxdefy"，最長公共子串是"def"。
答：動態(tài)規(guī)劃。具體的解法和代碼在我的隨筆Algorithm分類中有。

5.單向鏈表反序。
答：這個簡單，網(wǎng)上一大堆解法。

6.多個已序數(shù)組求交集。
答：這個問題攜程也考了，具體做法是將這些數(shù)組兩兩分組，求交集，再將結(jié)果繼續(xù)兩兩分組，求交集，直到最后得出結(jié)果。對于兩個已序數(shù)組A，B，求交集的方法是令i，j=0if A==B[j]，則A是交集中的值，i ，j ； if A>B[j]，j ； if A

一面總算是抗住了。本以為二面會輕松一點(diǎn)，誰知道二面更難。

1.了解進(jìn)程池嗎？
答：不了解，只知道線程池。

追問：那你說說線程池。
答：線程池的思想是這樣的：一臺服務(wù)器有許多任務(wù)要處理，同時不斷有新的任務(wù)進(jìn)來。從前是來一個任務(wù)就起一個線程，起的線程來完成任務(wù)，完成以后就銷毀該線程。如果任務(wù)很多的話，這樣不斷地起線程，銷毀線程，會很費(fèi)時間。于是就有了線程池。線程池就是一次起多個線程，將任務(wù)放在一個隊列中，線程池中的線程從隊列中取出任務(wù)去執(zhí)行，執(zhí)行完了以后檢查隊列是否為空，如果為空，說明所有任務(wù)都執(zhí)行完了，線程就會休眠(注意不是銷毀)，等到又有新的任務(wù)時，主線程會去喚醒線程池中的線程，讓他們繼續(xù)工作，這樣就避免了不斷地分配和銷毀線程。簡單的線程池實現(xiàn)代碼可以在網(wǎng)上搜到。

追問：在線程從任務(wù)隊列中取任務(wù)時，有沒有辦法不適用鎖？
答：這個問題騰訊也問了，騰訊的問法是，進(jìn)程間的共享內(nèi)存，有沒有辦法不適用鎖而同步地讀寫？我完全不會，誒。

面試官后來提示說，這個任務(wù)隊列不一定要所有線程共用一個，可以讓一個線程有一個任務(wù)隊列，這相當(dāng)于讓多消費(fèi)者的模型變成了單消費(fèi)者。這樣消費(fèi)者之間就不用加鎖同步了。而生產(chǎn)者和消費(fèi)者之間，要想不適用鎖的話，可以用循環(huán)隊列來實現(xiàn)。對于這個知識點(diǎn)，我會在另一個帖子中詳細(xì)說明。

2.咱們來看看進(jìn)程池吧，首先，一個進(jìn)程A，起了子進(jìn)程H，H阻塞在讀取它的stdin上，A向H的stdin發(fā)送數(shù)據(jù)，這個怎么實現(xiàn)？

答：完全懵了，什么叫一個進(jìn)程A起了子進(jìn)程H？后來我才弄明白，原來他的意思是，A進(jìn)程fork產(chǎn)生了一個子進(jìn)程，然后子進(jìn)程調(diào)用exec函數(shù)，啟動了H。我原來的想法是，既然H是A的子進(jìn)程，如果不設(shè)置FD_CLOEXEC標(biāo)志，那么H的文件描述符0(標(biāo)準(zhǔn)輸入)應(yīng)該和A的是共享文件表項的。那直接讓A往自己的標(biāo)準(zhǔn)輸入里寫不就行了嗎？后來面試官的意思是用管道，讓H將stdin打開在管道的一端上(fdopen)，然后A向管道里寫數(shù)據(jù)。這個應(yīng)該更穩(wěn)妥吧。誰能保證FD_CLOEXEC不會被設(shè)置呢？

追問：現(xiàn)在A能向H發(fā)命令，然后H讀取命令，開始工作。如果A起了多個H，那么，A就成了控制進(jìn)程，而多個H就成了工作進(jìn)程，這就是進(jìn)程池了。現(xiàn)在，A讀取一個文件，每讀取一行，就將內(nèi)容發(fā)送給工作進(jìn)程H，然后由H寫到自己的標(biāo)準(zhǔn)輸出上，這個怎么實現(xiàn)？

答：這個直接用一個循環(huán)，順序?qū)懴蛎總€進(jìn)程就好了。

追問：那如果在寫第一個進(jìn)程的時候就發(fā)生阻塞了呢？而后面的進(jìn)程可以正常工作。
答：傻了，應(yīng)該用select嘛。將要寫的文件描述符都加到select的可寫描述符集中，這樣哪個可寫就寫哪個。

追問：現(xiàn)在將A的標(biāo)準(zhǔn)輸出重定向到另一個文件上，然后讓H的輸出結(jié)果都寫到該文件上，怎么實現(xiàn)？
答：想了老半天，終于想出來了。還是select嘛。再建一個管道，將H的標(biāo)準(zhǔn)輸出打開在管道的一端，另一端放在select的可讀字符集中，如果可讀，A就可以讀到H的輸出了，然后再寫到標(biāo)準(zhǔn)輸出上，就行了。

3.用過epoll沒？
答：沒有。大家趕緊去學(xué)一下吧，太多面試官問了。

4.寫個memcpy吧。
答：這個簡單，只要注意如果dest或者src為空的時候，就直接返回。

5.非遞歸地中序遍歷二叉樹。
答：其實面試官之前問的是后續(xù)遍歷，不過他看我沒寫過非遞歸的，就降低了一點(diǎn)難度，讓我寫個中序遍歷。遞歸的寫法很簡單，相信大家都會。這里為什么要用非遞歸呢？因為非遞歸的效率更高。我以前就偷懶，想著會一種寫法就夠了，誰知道今天恰恰考了非遞歸。不過咱也不能直接來句不會。你可以不會，但不要馬上說不會，這體現(xiàn)出你遇到困難很容易就放棄。應(yīng)該先想一想，如果實在不會，有的面試官會給你一些提示，如果你能按照提示答出結(jié)果，也許面試官會更欣賞你，這證明你很會學(xué)習(xí)，一點(diǎn)就通。面試官看我無從下筆，說你先給我花花棧的結(jié)構(gòu)吧。我一聽，棧？莫非這一題要用棧才能解？其實遞歸不就是程序自己調(diào)用自己，而程序不就是在棧里運(yùn)行的嗎？簡單來說，遞歸的最后一層，就像棧頂元素。最后一個進(jìn)去，最先解出來。順著這個思路，我居然寫出了代碼。面試官看了看，ok。

至此，二面結(jié)束。

后來和面試官談了談職業(yè)發(fā)展方面的內(nèi)容，頗有收獲。面試官年紀(jì)也不大，3年前從華科畢業(yè)的，如今已經(jīng)是一個頭目了。他說，咱們是碼農(nóng)，不過碼農(nóng)分幾個等級，對于那些你交給他個任務(wù)，他能寫出代碼的，那是最初級的。如果他能把代碼分成個幾層，層次分明。那是較高一級的。如果他能指出你這結(jié)構(gòu)不對，應(yīng)該怎么怎么樣更好，那是更高級別的。如果想要發(fā)展，就要朝著高級別努力，不過前提是你得寫得出代碼，連代碼都寫不出來的，那就是要被開掉的。