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

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

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

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

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

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

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

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

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

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

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

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

1.了解進程池嗎？
答：不了解，只知道線程池。

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

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

面試官后來提示說，這個任務隊列不一定要所有線程共用一個，可以讓一個線程有一個任務隊列，這相當于讓多消費者的模型變成了單消費者。這樣消費者之間就不用加鎖同步了。而生產者和消費者之間，要想不適用鎖的話，可以用循環隊列來實現。對于這個知識點，我會在另一個帖子中詳細說明。

2.咱們來看看進程池吧，首先，一個進程A，起了子進程H，H阻塞在讀取它的stdin上，A向H的stdin發送數據，這個怎么實現？

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

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

答：這個直接用一個循環，順序寫向每個進程就好了。

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

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

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

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

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

至此，二面結束。

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