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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.寫(xiě)個(gè)memcpy吧。
答：這個(gè)簡(jiǎn)單，只要注意如果dest或者src為空的時(shí)候，就直接返回。

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

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

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