《劍指Offer——名企面試官精講典型編程題》已經出版

非常感謝博客上的讀者，是大家的關心、支持和鼓勵讓我有信心寫完這本書并最終出版發行（ china-pub互動網、 亞馬遜卓越網、 淘寶網、 京東網、 當當網上有售）。網友們的鼓勵讓我在 博客上的寫作從2007 年2 月開始堅持到了現在。也正是由于網友們的鼓勵，我最終下定決心把博客整理成一本書。
　　 本書特點
　　本書的原型是我過去4 年多陸陸續續發表的幾十篇博客，但這本書也不僅僅是這些博客的總和，它在博客的基礎上添加了大量內容。正如出版社編輯在書的封底寫的推薦詞一樣，這本書有如下特點：
　　(1)面試官的視角
　　從面試官視角剖析考題構思、現場心理、解題方法優劣與面試心得，尚屬首例。
　　(2)50余道編程題
　　本書精選谷歌、微軟等知名IT企業的50余道與數據結構、算法相關的典型面試題，提供多角度的解題輔導。這些題目現今仍被大量面試官反復采用，實戰參考價值頗高。
　　(3)系統的解題方法
　　本書系統總結了如何在面試時寫出高質量代碼，如何優化代碼效率，以及分析、解決難題的常用方法。
　　(4)超寫實體驗與感悟
　　Autodesk->微軟->思科，作者一路跳槽一路“面”，既親歷被考，也做過考官，更是資深程序員，大量的一線面試與編程經驗，足當確保本書品質。
　　 本書內容
　　全書分為7 章，各章的主要內容如下：
　　第 1 章介紹面試的流程。通常整個面試過程可以分為電話面試、共享桌面遠程面試和現場面試3 個階段，每一輪面試又可以分為行為面試、技術面試和應聘者提問3 個環節。本章詳細討論了面試中每一環節需要注意的問題。其中第1.3.2 節深入討論了技術面試中的5 個要素，是全書的大綱，接下來的第2～6 章逐一討論每個要點。
　　第 2 章梳理應聘者接受技術面試時需要用到的基礎知識。本章從編程語言、數據結構及算法三方面總結了程序員面試的知識點。
　　第 3 章討論應聘者在面試時寫出高質量代碼的3 個要點。通常面試官除了期待應聘者寫出的代碼能夠完成基本的功能之外，還能應對特殊情況并對非法輸入進行合理的處理。讀完這一章，讀者將學會如何從規范性、完整性和魯棒性3 個方面提高代碼的質量。
　　第 4 章總結在編程面試中解決難題的常用思路。如果在面試過程中遇到復雜的難題，應聘者最好在寫代碼之前形成清晰的思路。讀者在讀完這一章之后將學會如何用畫圖、舉例和分解復雜問題3 種思路來解決問題。
　　第 5 章介紹如何優化代碼的時間效率和空間效率。如果一個問題有多種解法，面試官總是期待應聘者能找到最優的解法。讀完這一章，讀者將學會優化時間效率及空間換時間的常用算法。
　　第 6 章總結面試中的各項能力。面試官在面試過程中會一直關注應聘者的學習能力和溝通能力。除此之外，有些面試官還喜歡考查應聘者的知識遷移能力、抽象建模能力和發散思維能力。讀完這一章，讀者將學會如何培養和運用這些能力。

　　第 7 章是兩個面試的案例。在這兩個案例中，我們將看到應聘者在面試過程中的哪些舉動是不好的行為，而哪些表現又是面試官所期待的行為。衷心地希望應聘者能在面試時少犯甚至不犯錯誤，完美地表現出自己的綜合素質，最終拿到心儀的Offer。

　　如果朋友們覺得這個博客寫得還不錯，那么這本書也不會讓大家失望。歡迎朋友們關注、閱讀這本書。對這本書有任何評論、建議或者意見，都請在博客評論中告訴我，或者在微博上 @何海濤Harry。

　　再次感謝大家的關注。

編程技術面試的五大要點

（寫在前面的話：本文最初發表于 《程序員》雜志2011年10月刊，并收錄到《 劍指Offer——名企面試官精講典型編程題》一書中。）

　　近年來找工作一直是一個很熱門的話題。我們要想找到心儀的工作，難免需要經過很多輪面試。編程面試是程序員面試過程中最為重要的一個環節。如果能在編程面試的環節充分展示自己的能力，那么拿到中意的Offer就是水到渠成的事情。筆者先后在歐特克、微軟和思科等知名公司任軟件工程師，多次接受他人的面試，同時也面試過很多人。總結面試與被面試的經驗，筆者發現盡管面試官的背景、性格各不相同，但都關注應聘者五種素質：（1）扎實的基礎知識、（2）能寫高質量的代碼、（3）分析問題時思路清晰、（4）能優化時間效率和空間效率、（5）具備包括學習能力、溝通能力、發散思維能力等在內的綜合能力。

扎實的基礎知識

　　扎實的基本功是成為優秀程序員的前提條件，因此面試官首要關注應聘者的素質就是是否具備扎實的基礎。通常基本功在編程面試環節體現在兩個方面：一是編程語言，二是數據結構和算法。

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

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

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

高質量的代碼

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

　　舉個很多應聘者都被問過的一個問題：寫一個函數，把字符串轉化成整數。這道題看似很簡單，絕大部分計算機專業的畢業生都能用十行以內的代碼實現最基本的功能。可是在實際面試過程中，十個應聘者中只有一個人能通過這道題的面試，因為絕大部分應聘者不能全面各種特殊輸入，比如輸入的字符串含中有非數字的符號、在字符串的開頭有正負號、字符串中有正負號但其位置不是在字符串的開頭。除此之外，面試官還希望應聘者能考慮的邊界條件包括2147483647（0x7FFFFFFF，int能表示的最大正整數）和-2147483648（0x80000000，int能表示的最小負整數）。

　　除了邊界條件和特殊輸入考慮不足之外，面試官還有一個不能容忍的錯誤就是程序崩潰。面試的時候有很多應聘者都會忘了對空指針做特殊處理而導致程序崩潰。如果面試的時候遇到鏈表、二叉樹相關的題目，應聘者一定要特別小心。因為這兩種題目對應的代碼里通常會有大量的指針操作，如果考慮不周到，就有可能對空指針進行操作而使程序崩潰。比如這樣的一道題：輸入一個鏈表的頭指針和一個無符號整數k，輸出該鏈表的倒數第k個結點。這個題目很多人都能想到用兩個指針來解決這個問題：第一個指針先在鏈表上移動k-1步，然后同時讓第一個指針和第二個指針在鏈表上移動。當第一個指針移動到尾指針的時候，第二個指針指向的就是倒數第k個結點。然而不是每個應聘者都能根據正確思路寫出完整的代碼。不少應聘者會忽略兩種可能：一是輸入的鏈表頭指針有可能是空指針；二是鏈表上結點的數目有可能少于k個。忽略這兩點的代碼都存在崩潰的可能，不是魯棒的程序，從而很也很難獲得面試官的青睞。

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

清晰的思路

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

　　應聘者可以用幾個簡單的方法幫助自己形成清晰的思路。首先是舉幾個簡單的具體例子讓自己理解問題。當我們一眼看不出問題中隱藏的規律的時候，可以試著用一兩個具體的例子模擬操作的過程，這樣說不定就能通過具體的例子找到抽象的規律。其次可以試著用圖形表示抽象的數據結構。像分析與鏈表、二叉樹相關的題目，我們都可以畫出它們的結構圖來簡化題目。最后可以試著把復雜的問題分解成若干個簡單的子問題，再一一解決。很多基于遞歸的思路，包括分治法和動態規劃法，都是把復雜的問題分解成一個或者多個簡單的子問題。

　　比如把二叉搜索樹轉化排序的雙向鏈表這個問題就很復雜。碰到這個問題，我們不妨先畫出一兩個具體的二叉搜索樹及其對應的排序雙向鏈表，直觀地感受二叉搜索樹和排序的雙向鏈表有哪些聯系。如果一下子找不出轉換的規律，我們可以把整個二叉樹看出三部分：根結點、左子樹和右子樹。當我們遞歸地把轉換左右子樹這兩個子問題解決之后，再把轉換左右子樹得到的鏈表和根結點鏈接起來，整個問題也就解決了。

優化代碼的能力

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

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

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

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

優秀的綜合能力

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

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

　　知識遷移能力是一種特殊的學習能力。如果我們能夠把已經掌握的知識遷移到其他領域，那么學習新技術或者解決新問題就會變得容易。面試官經常會先問一個簡單的問題，再問一個很復雜但和前面的簡單問題相關的問題。這個時候面試官期待應聘者能夠從簡單問題中得到啟示，從而找到解決復雜問題的竅門。比如面試官先要求應聘者寫一個函數求斐波那契數列，再問一個青蛙跳臺階的問題：一只青蛙一次可以跳上1級臺階，也可以跳上2即臺階。請問這只青蛙跳上n級的臺階總共有多少種跳法？應聘者如果具有較強的知識遷移能力，就能分析出青蛙跳臺階問題實質上只是斐波那契數列的一個應用。

　　還有不少面試官喜歡考查應聘者的抽象建模能力和發散思維能力。面試官從日常生活中提煉出問題，比如如何判斷5張撲克牌是不是順子，考查應聘者能不能把問題抽象出來用合理的數據結構表示，并找到其中的規律解決這個問題。面試官也可以限制應聘者不得使用常規方法，這要求應聘者具備創新精神，能夠打開思路從多角度去分析、解決問題。比如面試官要求應聘者不用加減乘除四則運算實現兩個整數的加法。此時面試官期待應聘者能夠打開思路，用位運算實現整數的加法。

小結

　　我們可以用下圖總結應聘者需要具備的素質。

　　從中我們可以看出，應聘者在面試之前需要做足準備，對編程語言、數據結構和算法等基礎知識有全面的了解。面試的時候如果碰到簡單的問題應聘者一定要注重細節寫出完整、魯棒的代碼。如果碰到復雜的問題應聘者可以通過畫圖、舉具體例子分析和分解復雜問題等方法先理清思路再動手編程。除此之外，應聘者還應該不斷優化時間效率和空間效率，力求找到最優的解法。在面試過程中，應聘者還應該主動提問弄清楚題目的要求，表現自己的溝通能力。當面試官前后問的兩個問題有相關性的時候，盡量把解決前面問題的思路遷移到后面的問題中去，展示自己良好的學習能力。如果能做到這么幾點，那么應聘者順利通過面試獲得心儀的職位將是瓜熟蒂落的事情。

善用時間，發展副業

（寫在前面的話：本文在《程序員雜志》的2011年12月刊上發表。）

??? ??? 過去一年，我在保證不能影響本職工作的前提下，完成了《劍指Offer——名企面試官精講典型編程題》一書的寫作。下面來分享一下寫作過程中踐行的時間管理經驗。

明確任務與目標

??? ??? 從2010年下定決心寫書開始，我就設定了比較明確的目標。面試類的書籍有其特殊的時效性，最佳時間是在今年7月交稿，恰好能趕上2011年秋季的校園招聘。明確了任務與目標后，行動就有了方向。

??? ??? 在制訂目標時，需要注意可操控性，除了計算正常工作量，一定需要保證適量的緩沖時間。畢竟只是副業，無法與本職工作有同等的優先級。目標如果過于激進，在突發狀況發生時，進度就很難掌控。一般情況下，建議預留全部工作時間的25%~35%作為緩沖。

細化目標，執行計劃

??? ??? 除了整體的計劃外，還需要進行目標細化。在寫書時，我不僅會進行每月的計劃，同時會有每周甚至具體到每天完成多少內容的目標。計劃的粒度越細，也越 容易掌控。當某一天不能按時完成計劃的工作量時，馬上就能作出調整，而不至于到最后漏洞大了才恍然大悟。同時，寫書是一個持久戰，最考驗人的不一定是文字 能力，更多的是毅力。一個個小目標的實現，都是自我鼓勵的基礎，也是自信心的來源。

??? ??? 制訂計劃之后就要嚴格執行計劃，盡量要求自己完成計劃的工作量。

善用閑散時間

??? ??? 之前曾在網上看到一句話，說一個人的成就很大程度上決定于每天晚上8點到10點他在做什么。這是很多人晚餐之后看電視或者上網的時間。如果自己想在工作之余做出點成績，就可以把這個休閑時間好好利用起來。

??? ??? 當然人總是需要一定的休息時間的，就比如一塊肥沃的土地，連續幾季都種同樣的作物，土壤的肥力也會枯竭，收成就會越來越差。為解決這個問題，農民在 土地上輪換種植不同的作物，或者同時種植幾種作物，這樣能提高土地的使用效率。其實時間也類似。寫作之余我會到各論壇看看有沒有關于程序員面試話題的討 論。這樣一邊休閑，一邊為寫書積累素材，休閑和正事兩不誤。

區分使用小段時間和大段時間

??? ??? 大腦思維在切換工作時需要一定的過程，并不能立即高效率地進入深度思考與完全工作狀態。一般而言大腦需要10~15分鐘才能集中精神進入工作狀態，因此不宜用小段時間來做只有靜下心來認真思考才能做好的工作。

??? ??? 如果空余時間不足1小時，我會選擇把這段時間用來整理、修改已寫好的書稿。這樣即使大腦沒有完全集中精神也能開展。通常我會為撰寫新內容安排一大段時間，從而避免大腦頻繁切換工作場景，提高用腦效率。

小結

??? ??? 一旦下定決心完成某一任務，就要在確定總體目標之后細化每一周甚至每一天的工作量，盡量確保每個時間節點都能按時完成。由于副業擠占了休息時間，可 能會很累。雖然不是說完全不能有休閑活動，但如果有可能還是可以把閑散時間利用起來，做一些工作相關的事情，這樣既放松了大腦，又有效利用了時間。如果能 堅持一段時間，就會小有所成。

提高面試代碼質量的三要素

（寫在前面的話：本文在《程序員》雜志2012年1月刊上發表，并收錄到《劍指Offer——名企面試官精講典型編程題》一書中。）

??? 程序員在職業生涯中難免要接受編程面試。有些程序員由于平時沒有養成良好的編程習慣，在面試時寫出的代碼質量不高，最終遺憾地與心儀的公司和職位失之交臂。因此，如何在面試時能寫出高質量的代碼，是很多程序員關心的問題。

代碼的規范性

??? 面試官是根據應聘者寫出的代碼來決定是否錄用一個應聘者的。應聘者首先要把代碼寫得規范，才可以避免很多低級錯誤。如果代碼寫得不夠規范，會影響面試官閱讀代碼的興致，至少印象分會打折扣。書寫、布局和命名都決定著代碼的規范性。

??? 規范的代碼書寫清晰。絕大部分面試都要求應聘者在白紙或者白板上書寫。由于現代人已經習慣了敲鍵盤打字，手寫變得越發不習慣，因此寫出來的字潦草難辨。雖然應聘者沒有必要為了面試特意去練字，但在面試過程中減慢寫字速度、盡量把每個字母寫清楚還是很有必要的。不用擔心沒有時間去寫代碼。通常編程面試的代碼量都不會超過50行，書寫不用花多少時間，關鍵是在寫代碼之前形成清晰的思路并能把思路用編程語言清楚地書寫出來。

??? 規范的代碼布局清晰。平時程序員在集成開發環境如Visual Studio里面寫代碼，依靠專業工具調整代碼的布局，加入合理的縮進并讓括號對齊成對呈現。離開這些工具，應聘者就要格外注意布局問題。當循環、判斷較多邏輯較復雜時，縮進的層次可能比較多。如果布局不夠清晰，縮進也不能體現體現代碼的邏輯，這樣的代碼將會讓人頭暈腦脹。

??? 規范的代碼命名合理。很多初學編程的人在寫代碼時總是習慣用最簡單的名字來命名，變量名是i、j、k，函數名是f、g、h。由于這樣的名字不能告訴讀者對應的變量或者函數的意義，代碼一長就會變得非常晦澀難懂。強烈建議應聘者在寫代碼時，用完整的英文單詞組合命名變量和函數，比如函數需要傳入一個二叉樹的根結點作為參數，則可以把該參數命名為BinaryTreeNode* pRoot。不要因為這樣會多寫幾個字母而覺得麻煩。如果一眼能看出變量、函數的用途，應聘者就能避免自己搞混淆而犯一些低級的錯誤。同時合理的命名也能讓面試官一眼就能讀懂代碼的意圖，而不是讓他去猜變量到底是數組中的最大值還是最小值。

代碼的完整性

??? 在面試的過程中，面試官會非常關注應聘者考慮問題是否周全。面試官通過檢查代碼是否完整來考查應聘者的思維是否全面。通常面試官會檢查應聘者的代碼是否完成了基本功能、輸入邊界值是否能得到正確的輸出、是否對各種不合規范的非法輸入做出了合理的錯誤處理。

三種測試用例確保代碼的完整性

??? 應聘者在寫代碼之前，首先要把可能的輸入都想清楚，從而避免在程序中出現各種各樣的質量漏洞。也就是說在編碼之前要考慮單元測試。如果能夠設計全面的單元測試用例并在代碼中體現出來，那么寫出的代碼自然也就是完整正確的了。通常程序員可以從功能測試、邊界測試和負面測試三方面設計測試用例，以確保代碼的完整性。

• 首先要考慮的普通功能測試的測試用例。應聘者首先要保證寫出的代碼能夠完成面試官要求的基本功能。比如面試題要求完成的功能是把字符串轉換成整數，應聘者就可以考慮輸入字符串“123”來測試自己寫的代碼。這里要把零、正數（比如123）和負數（比如-123）都考慮進去。

??? 考慮功能測試時，應聘者要盡量突破常規思維的限制，避免忽視某些隱含的功能需求。比如“打印從1到最大的n位數”，很多人覺得很簡單。最大的3位數是999、最大的4位數是9999。這些數字很容易就能算出來。但最大的n位數都能用int型表示嗎？如果超出int的范圍可以考慮long long類型。超出long long能夠表示的范圍呢？面試官是不是要求考慮任意大的數字？如果面試官確認題目要求的是任意大的數字，那么這個題目就是一個大數問題。此時需要特殊的數據結構來表示數字，比如用字符串或者數組來表示大的數字，才能確保不會溢出。

• 其次需要考慮各種邊界值的測試用例。很多代碼都包含有循環或者遞歸。如果代碼是基于循環，那么結束循環的邊界條件是否正確？基于循環的代碼要特別注意開區間和閉區間的使用（也就是區分<與<=、>與>=）。如果代碼是基于遞歸，遞歸終止的邊界值是否正確？這些都是邊界測試時要考慮的用例。還是以字符串轉換成整數的問題為例，應聘者寫出的代碼應該確保能夠正確轉換最大的正整數和最小的負整數。

• 再次還需要考慮各種可能的錯誤的輸入，也就是負面測試的測試用例。應聘者寫出的函數除了要順利地完成要求的功能之外，當輸入不符合要求時，面試官還希望他能做出合理的錯誤處理。在設計把字符串轉換成整數的函數時，應聘者就要考慮當輸入的字符串不是一個數字，比如“1a2b3c”，怎么告訴函數的調用者這個輸入是非法的。

??? 前面討論的都是要全面考慮當前需求對應的各種可能輸入。在軟件開發過程中，永遠不變的就是需求會一直改變。如果應聘者在面試時寫出的代碼能夠把將來需求可能的變化都考慮進去，在需求發生變化時能夠盡量減少代碼改動的風險，那他就向面試官展示了自己對程序可擴展性和可維護性的理解，必定能得到面試官的青睞。如果應聘者在解答面試題“調整數組順序使奇數位于偶數前面”時能夠考慮可擴展性，他寫出的代碼不僅僅只是解決調整奇數和偶數的問題，還能考慮到把調整數字順序的功能和判斷一個數字是奇數還是偶數的功能解耦。這樣當今后需求功能擴展要求解決類似的問題，比如調整負數和非負數的順序、調整能被3整除的數字和不能被3整除的數字的順序，只需要添加很少的代碼都能做到，于是提高了代碼的可擴展性和可維護性。

三種錯誤處理的方法

??? 通常有三種方式把錯誤信息傳遞給函數調用者。

• 函數用返回值來告知調用者是否出錯。比如很多Windows的API就是這個類型。Windows中很多API的返回值為0表示API調用成功，而返回值不為0表示在API調用的過程中出錯了。微軟為不同的非零返回值定義了不同的意義，調用者可以根據這些返回值判斷出錯的原因。這種方式最大的問題是使用不便，因為函數不能直接把計算結果通過返回值直接賦值給其他變量，同時也不能把這個函數計算的結果直接作為參數傳遞給其他函數。

• 當發生錯誤時設置一個全局變量。此時可以在返回值中傳遞計算結果了。這種方法比第一種方法使用起來更加方便，因為調用者可以直接把返回值賦值給其他變量或者作為參數傳遞給其他函數。Windows的很多API運行出錯之后，也會設置一個全局變量。函數調用者可以通過調用函數GetLastError分析這個表示錯誤的全局變量從而得知出錯的原因。但這個方法有個問題：調用者很容易就會忘記去檢查全局變量，因此在調用出錯時忘記做相應的錯誤處理，從而留下安全隱患。

• 異常。當函數運行出錯時，程序就拋出一個異常。程序員可以根據不同的出錯原因定義不同的異常類型。因此函數的調用者可以根據異常的類型就能知道出錯的原因，從而可以做相應的處理。另外，由于顯式劃分了程序正常運行的代碼塊（try模塊）和處理異常的代碼塊（catch模塊），代碼的邏輯比較清晰。異常在高級語言如C#中是強烈推薦的錯誤處理方式，但有些早期的語言比如C語言還不支持異常。另外，當拋出異常時，程序的執行會打亂正常的順序，對程序的性能有很大的影響。

??? 上述三種錯誤處理的方式各有優缺點。那么面試時應聘者該采用哪種方式呢？這要看面試官的需求。在聽到面試官的題目之后，應聘者要盡快分析出可能存在哪些非法輸入，并和面試官討論該如何處理這些非法輸入。和面試官進行這樣的討論對應聘者是有益的，因為面試官會覺得他對錯誤處理有著全面的了解，并且還會覺得他有很好的溝通能力。

代碼的魯棒性

??? 魯棒性是指程序能夠判斷輸入是否合乎規范要求，并對不合要求的輸入予以合理的處理。容錯性是魯棒性的一個重要體現。不魯棒的軟件在發生異常事件時，比如用戶輸入錯誤的用戶名、試圖打開的文件不存在或者網絡不能連接，就會出現不可預見的詭異行為，或者干脆整個軟件崩潰。這樣的軟件對于用戶而言，不亞于一場災難。
由于魯棒性對軟件開發非常重要，面試官在招聘時對應聘者寫出的代碼是否魯棒也非常關注。提高代碼的魯棒性的有效途徑是進行防御性編程。防御性編程是一種編程習慣，是指預見在什么地方可能會出現問題，并為這些可能出現的問題制定處理方式。

??? 在面試時，最簡單也最實用的防御性編程就是在函數入口添加代碼以驗證用戶輸入是否符合要求。通常面試要求的是寫一兩個函數，應聘者需要格外關注這些函數的輸入參數。如果輸入的是一個指針，那指針是空指針怎么辦？如果輸入的是一個字符串，那么字符串的內容為空怎么辦？如果應聘者能把這些問題都提前考慮到，并作相應的處理，那么面試官就會覺得他有防御性編程的習慣，能夠寫出魯棒的軟件。

??? 當然并不是所有與魯棒性相關的問題都只是檢查輸入的參數這么簡單。應聘者看到問題時，要多問幾個“如果不……那么……”這樣的問題。比如面試題“鏈表中倒數第k個結點”，這里隱含著一個條件就是鏈表中結點的個數大于k。應聘者就要問自己如果鏈表中的結點不是大于k個，那么代碼會出什么問題？這樣的思考方式，能夠幫助發現潛在的問題并提前解決問題。這比事后讓面試官發現問題之后應聘者再去慌忙分析代碼查找問題的根源要好很多。

小結

??? 本文從規范性、完整性和魯棒性三方面介紹了應聘者如何在面試時寫出高質量代碼（如下圖所示）。

???

??? 第一，應聘者在白紙或者白板上手寫代碼時要注意規范性，盡量清晰地書寫每個字母，通過縮進和對齊括號讓代碼布局合理，同時還要合理命名代碼中的變量和函數。第二，應聘者最好在編碼之前全面考慮所有可能的輸入，確保寫出的代碼在完成了基本功能之外，還考慮了邊界條件，并做好了錯誤處理。只有全面考慮到這三方面的代碼才是完整的代碼。第三，應聘者要重視代碼的魯棒性，確保自己寫出的程序不會輕易崩潰。平時在寫代碼時，應聘者最好養成防御式編程的習慣，在函數入口判斷輸入是否有效并對各種無效輸入做好相應的處理。應聘者如果能夠做到這三點，自然就能寫出高質量的代碼，最終通過面試拿到Offer也將是水到渠成的事情。