文 / 何海濤

扎實的基礎(chǔ)知識、高質(zhì)量的代碼,、清晰的思路,、優(yōu)化代碼的能力、優(yōu)秀的綜合能力是編程技術(shù)面試的五大要點,。

找工作一直是一個熱門話題,。要想找到心儀的工作，難免需要經(jīng)過多輪面試,。編程面試是程序員面試過程中最為重要的一個環(huán)節(jié),。如果能在編程面試的環(huán)節(jié)充分展示自己的能力，那么拿到中意的Offer就是水到渠成的事情,。

我先后在歐特克,、微軟和思科等公司任軟件工程師，多次接受他人的面試,，同時也面試過很多人,。總結(jié)面試與被面試的經(jīng)驗,，我發(fā)現(xiàn)盡管面試官的背景,、性格各不相同，但都關(guān)注應(yīng)聘者五種素質(zhì)：扎實的基礎(chǔ)知識；能寫高質(zhì)量的代碼,；分析問題時思路清晰,；能優(yōu)化時間效率和空間效率；具備包括學(xué)習(xí)能力,、溝通能力,、發(fā)散思維能力等在內(nèi)的綜合能力。

扎實的基礎(chǔ)知識

扎實的基本功是成為優(yōu)秀程序員的前提條件,，因此面試官首要關(guān)注應(yīng)聘者的素質(zhì)即是否具備扎實的基礎(chǔ),。通常基本功在編程面試環(huán)節(jié)體現(xiàn)在兩個方面：一是編程語言,，二是數(shù)據(jù)結(jié)構(gòu)和算法,。

每個程序員至少要熟練掌握1~2門編程語言。面試官從應(yīng)聘者在面試過程中寫的代碼以及跟進的提問中,，能看出他編程語言掌握的熟練程度,。以大部分公司面試要求的C++為例，如果函數(shù)需要傳入一個指針,，面試官可能會問是否需要為該指針加上const,，把const加在指針不同的位置有什么區(qū)別；如果寫的函數(shù)需要傳入的參數(shù)是一個復(fù)雜類型的實例,，面試官可能會問傳入值參數(shù)或者引用參數(shù)有什么區(qū)別,，什么時候需要為傳入的引用參數(shù)加上const。

數(shù)據(jù)結(jié)構(gòu)通常是編程面試過程中考查的重點,。在參加面試之前,，應(yīng)聘者需要熟練掌握鏈表、樹,、棧,、隊列以及哈希表等數(shù)據(jù)結(jié)構(gòu)以及它們的操作。如果我們留心各大公司的面試題,，就會發(fā)現(xiàn)鏈表和二叉樹相關(guān)的問題是很多面試官喜歡問的問題,。這方面的問題看似簡單，但真正掌握也很不容易,，特別適合在短短幾十分鐘的面試時間內(nèi)檢驗應(yīng)聘者的基本功,。如果應(yīng)聘者事先對鏈表的插入和刪除結(jié)點了如指掌，對二叉樹的各種遍歷方法的循環(huán)和遞歸寫法都爛熟于胸,，那么真正到了面試時也就游刃有余了,。

大部分公司對算法的要求都只是考查查找和排序。應(yīng)聘者可以在了解各種查找和排序算法的基礎(chǔ)上,，重點掌握二分查找、歸并排序和快速排序,，因為很多面試題都只是這些算法的變體而已,。比如把排序好的數(shù)組的前面若干個數(shù)字移到數(shù)組的后面,，然后問怎樣在這個數(shù)組之中找到最小的數(shù)字。這道題其本質(zhì)就是考查二分查找,。少數(shù)對算法很重視的公司比如谷歌或者百度,，還會要求應(yīng)聘者熟練掌握動態(tài)規(guī)劃和貪婪算法。如果對這種類型的公司感興趣,，那么應(yīng)聘者在參加面試之前就應(yīng)該加強對相關(guān)算法題目的練習(xí),。

高質(zhì)量的代碼

只有注重質(zhì)量的程序員，才能寫出魯棒穩(wěn)定的大型軟件,。在面試過程中,，面試官總會格外關(guān)注邊界條件、特殊輸入等看似細枝末節(jié)但實質(zhì)至關(guān)重要的地方,，以此來分析應(yīng)聘者是否注重代碼質(zhì)量,。很多時候，面試官發(fā)現(xiàn)應(yīng)聘者寫出來的代碼只能完成最基本的功能,，一旦輸入特殊的邊界條件參數(shù)就會錯誤百出甚至程序崩潰,。

舉個很多應(yīng)聘者都被問過的一個問題：寫一個函數(shù)，把字符串轉(zhuǎn)化成整數(shù),。這道題看似很簡單,，絕大部分計算機專業(yè)的畢業(yè)生都能用十行以內(nèi)的代碼實現(xiàn)最基本的功能?？墒窃趯嶋H面試過程中,，十個應(yīng)聘者中只有一個人能通過這道題的面試，因為絕大部分應(yīng)聘者不能全面考慮到各種特殊輸入,，比如輸入的字符串含中有非數(shù)字的符號,、在字符串的開頭有正負號、字符串中有正負號但其位置不是在字符串的開頭,。

除此之外,，面試官還希望應(yīng)聘者能考慮的邊界條件包括2147483647（0×7FFFFFFF，int能表示的最大正整數(shù)）和-2147483648（0×80000000,，int能表示的最小負整數(shù)）,。

除了邊界條件和特殊輸入考慮不足之外，面試官還有一個不能容忍的錯誤就是程序崩潰,。面試時很多應(yīng)聘者都會忘記對空指針做特殊處理而導(dǎo)致程序崩潰,。如果面試時遇到鏈表、二叉樹相關(guān)的題目,，應(yīng)聘者一定要特別小心,。因為這兩種題目對應(yīng)的代碼里通常會有大量的指針操作，如果考慮不周到，就有可能對空指針進行操作而使程序崩潰,。

比如這樣一道題：輸入一個鏈表的頭指針和一個無符號整數(shù)k,，輸出該鏈表的倒數(shù)第k個結(jié)點。這個題目很多人都能想到用兩個指針來解決：第一個指針先在鏈表上移動k-1步,，同時讓第一個指針和第二個指針在鏈表上移動,。當(dāng)?shù)谝粋€指針移動到尾指針時,，第二個指針指向的就是倒數(shù)第k個結(jié)點,。然而不是每個應(yīng)聘者都能根據(jù)正確思路寫出完整的代碼。不少應(yīng)聘者會忽略兩種可能：一是輸入的鏈表頭指針有可能是空指針,；二是鏈表上結(jié)點的數(shù)目有可能少于k個,。忽略這兩點的代碼都存在崩潰的可能,，從而很難獲得面試官的青睞。

要想寫出魯棒的高質(zhì)量代碼,，需要在動手寫代碼之前想好測試用例,。在寫代碼之前，先要想好各種邊界條件和特殊輸入作為測試用例,。當(dāng)代碼寫好之后,，自己在心里用之前想好的測試用例來檢驗自己寫出的代碼，這樣就能在面試官之前發(fā)現(xiàn)并解決問題,。以求鏈表的倒數(shù)第k個結(jié)點為例,，如果事先想到了輸入頭指針為空指針和鏈表上的結(jié)點總數(shù)少于k這兩個測試用例，并且在寫好代碼之后在心里模擬代碼的運行過程,，確保能夠通過這兩個測試用例的測試,，那么這輪面試必然是能夠通過的。

清晰的思路

只有思路清晰,，應(yīng)聘者才有可能在面試過程中解決復(fù)雜的問題,。有時面試官會有意出一些比較復(fù)雜的問題，以考查能否在短時間內(nèi)形成清晰的思路并解決問題,。對于確實很復(fù)雜的問題,，面試官甚至不期待應(yīng)聘者能在面試不到一個小時的時間里給出完整的答案，他更看重的可能還是應(yīng)聘者是否有清晰的思路,。面試官通常不會喜歡應(yīng)聘者在沒有形成清晰思路之前就草率地開始寫代碼,，結(jié)果寫出來的代碼容易邏輯混亂、錯誤百出,。

應(yīng)聘者可以用幾個簡單的方法幫助自己形成清晰的思路,。

首先是舉幾個簡單的具體例子讓自己理解問題。當(dāng)一眼看不出問題中隱藏的規(guī)律時,，可以試著用1~2個具體的例子模擬操作的過程,，這樣說不定就能通過具體的例子找到抽象的規(guī)律,。

其次可以試著用圖形表示抽象的數(shù)據(jù)結(jié)構(gòu)。像分析與鏈表,、二叉樹相關(guān)的題目時,，可以畫出它們的結(jié)構(gòu)圖來簡化題目。

最后可以試著把復(fù)雜的問題分解成若干個簡單的子問題,，再一一解決。很多基于遞歸的思路,，包括分治法和動態(tài)規(guī)劃法,，都是把復(fù)雜的問題分解成一個或者多個簡單的子問題。

比如把二叉搜索樹轉(zhuǎn)化排序的雙向鏈表這個問題就很復(fù)雜,。碰到這個問題,，不妨先畫出1~2個具體的二叉搜索樹及其對應(yīng)的排序雙向鏈表，直觀地感受二叉搜索樹和排序的雙向鏈表有哪些聯(lián)系,。如果一下子找不出轉(zhuǎn)換的規(guī)律,，可以把整個二叉樹看出三部分：根結(jié)點、左子樹和右子樹,。當(dāng)遞歸地把轉(zhuǎn)換左右子樹這兩個子問題解決之后,，再把轉(zhuǎn)換左右子樹得到的鏈表和根結(jié)點鏈接起來，整個問題也就解決了,。

優(yōu)化代碼的能力

優(yōu)秀的程序員對時間和空間的消耗錙銖必較,，他們很有激情不斷優(yōu)化自己的代碼。當(dāng)面試官出的題目有多種解法時,，通常他會期待應(yīng)聘者最終能夠找到最優(yōu)解,。這就要求應(yīng)聘者在面試官提示還有更好的解法時，不能放棄思考,，而應(yīng)該努力尋找在時間消耗或者空間消耗上可以優(yōu)化的地方,。

要想優(yōu)化時間或者空間效率，首先要知道如何分析效率,。即使是同一個算法,，用不同方法實現(xiàn)的效率可能也會大不相同，要能夠分析出算法及其代碼實現(xiàn)的效率,。例如求斐波那契數(shù)列,，很多人喜歡用遞歸公式f(n)=f(n-1)+f(n-2)求解。如果分析它的遞歸調(diào)用樹,，就會發(fā)現(xiàn)有大量的計算是重復(fù)的,，時間效率是以n的指數(shù)增加。但如果先求f(1),、f(2),，再根據(jù)f(1)和f(2)求出f(3),，接下來根據(jù)f(2)、f(3)求出f(4),，并以此類推用一個循環(huán)求出f(n),，這種計算方法的時間效率就只有O(n)，比前面遞歸的方法要好很多,。

要想優(yōu)化代碼的效率,，還要熟知各種數(shù)據(jù)結(jié)構(gòu)的優(yōu)缺點，并能選擇合適的數(shù)據(jù)結(jié)構(gòu)解決問題,。我們在數(shù)組中根據(jù)下標(biāo)可以用O(1)完成查找,。數(shù)組的這個特征可以用來實現(xiàn)簡單的哈希表解決很多面試題，比如在字符串中找到第一個只出現(xiàn)一次的字符,。再比如為了找出n個數(shù)字中最小的k個數(shù),，需要一個數(shù)據(jù)容器來存儲k個數(shù)字。在這個數(shù)據(jù)容器中,，我們希望能夠快速地找到最大值并且能快速地替換其中的數(shù)字,。經(jīng)過權(quán)衡，我們發(fā)現(xiàn)二叉樹比如最大堆或者紅黑樹都是實現(xiàn)這個數(shù)據(jù)容器的理想選擇,。

要想優(yōu)化代碼的效率,，也要熟練掌握常用的算法。面試中最常用的算法是查找和排序,。如果從頭到尾順序掃描一個數(shù)組,，需要O(n)時間才能完成查找操作。但如果數(shù)組是排序的,，應(yīng)用二分查找算法就能把時間復(fù)雜度降低到O(logn),。排序算法除了能夠給數(shù)組排序之外，還能用來解決其他問題,。比如快速排序算法中的Partition函數(shù)能夠用來在n個數(shù)里查找第k大的數(shù)字,，從而可以用O(n)的時間在數(shù)組中找到出現(xiàn)次數(shù)超過數(shù)組長度一半的數(shù)字。如果面試題是一個求最大值或者最小值的題目,，則可以嘗試用動態(tài)規(guī)劃法或者貪婪算法,，比如用動態(tài)規(guī)劃法求出數(shù)組中連續(xù)子數(shù)組的最大和。

優(yōu)秀的綜合能力

在面試過程中,，應(yīng)聘者除了展示自己的編程能力和技術(shù)功底之外,，還需要展示自己的軟技能，諸如溝通能力和學(xué)習(xí)能力,。隨著軟件系統(tǒng)的規(guī)模越來越大,，軟件開發(fā)已經(jīng)告別了單打獨斗的年代，程序員與他人的溝通變得越來越重要,。在面試過程中,，面試官會觀察應(yīng)聘者在介紹項目經(jīng)驗或者算法思路時是否觀點明確,、邏輯清晰，并以此判斷他溝通能力的強弱,。另外,，面試官也會從應(yīng)聘者說話的神態(tài)和語氣來判斷他是否有團隊合作的意識。通常面試官不會喜歡高傲或者輕視合作者的人,。

IT行業(yè)知識更新很快,，因此程序員只有具備很好的學(xué)習(xí)能力才能跟上知識更替的步伐。通常面試官有兩種辦法考查應(yīng)聘者的學(xué)習(xí)能力,。第一種方法是詢問應(yīng)聘者最近在看什么書,、從中學(xué)到了哪些新技術(shù)。面試官可以用這個問題了解應(yīng)聘者的學(xué)習(xí)愿望和學(xué)習(xí)能力,。第二種方法是拋出一個新概念，接下來他會觀察應(yīng)聘者能不能在較短時間內(nèi)理解這個新概念并解決相關(guān)的問題,。比如面試官要求應(yīng)聘者計算第1500個丑數(shù),。很多人都沒有聽說過丑數(shù)這個概念。這時面試官就會觀察應(yīng)聘者面對丑數(shù)這個新概念,，能不能經(jīng)過提問,、思考、再提問的過程,，最終找出丑數(shù)的規(guī)律從而找到解決方案,。

知識遷移能力是一種特殊的學(xué)習(xí)能力。如果我們能夠把已經(jīng)掌握的知識遷移到其他領(lǐng)域,，那么學(xué)習(xí)新技術(shù)或者解決新問題就會變得容易,。面試官經(jīng)常會先問一個簡單的問題，再問一個很復(fù)雜但和前面的簡單問題相關(guān)的問題,。這時面試官期待應(yīng)聘者能夠從簡單問題中得到啟示,，從而找到解決復(fù)雜問題的竅門。比如面試官先要求應(yīng)聘者寫一個函數(shù)求斐波那契數(shù)列,，再問一個青蛙跳臺階的問題：一只青蛙一次可以跳上1級臺階,，也可以跳上2級臺階，請問這