編輯推薦
劍指offer：名企面試官精講典型編程題從面試官視角剖析考題構思、現場心理、解題方法優劣與面試心得，尚屬首例。
50餘道編程題
本書精選谷歌、微軟等知名IT企業的50餘道典型面試題，提供多角度的解題輔導。這些題目現今仍被大量面試官反覆採用，實戰參考價值頗高。
系統的解題方法
本書系統總結了如何在面試時寫出高質量代碼，如何最佳化代碼效率，以及分析、解決難題的常用方法。
超寫實體驗與感悟
Autodesk->微軟->思科，作者一路跳槽一路“面”，既親歷被考，也做過考官，更是資深程式設計師，大量的一線面試與編程經驗，足當確保本書品質。
內容簡介
本書剖析了50個典型的程式設計師面試題，從基礎知識、代碼質量、解題思路、最佳化效率和綜合能力五個方面系統整理了影響面試的5個要點。全書分為7章，主要包括：
1、面試的流程：討論面試流程中每一環節需要注意的問題；
2、面試需要的基礎知識：從程式語言、數據結構及算法三方面總結了程式設計師面試的知識點；
3、高質量的代碼：討論影響代碼質量的的3個要素（規範性、完整性和魯棒性），強調高質量的代碼除了能夠完成基本的功能之外，還能考慮到特殊情況並對非法輸入進行合理的處理；
4、解決面試題的思路：總結在編程面試中解決難題的常用思路，如果在面試過程中遇到了複雜的難題，應聘者可以利用畫圖、舉例和分解複雜問題3種方法化繁為簡，先形成清晰的思路再動手編程；
5、最佳化時間和空間效率：介紹如何最佳化代碼的時間效率和空間效率，讀完這一章讀者將學會常用的最佳化時間效率及空間換時間的常用算法，從而在面試中找到最優的解法；
6、面試中的各種能力：本章總結應聘者在面試過程中如何表現學習能力和溝通能力，並通過具體的面試題討論如何培養知識遷移能力、抽象建模能力和發散思維能力；
7、兩個面試案例：這兩個案例總結了應聘者在面試過程中哪些舉動是不好的行為，而哪些表現又是面試官所期待的行為。
本書適合即將走向工作崗位的大學生閱讀，也適合作為正在應聘軟體行業的相關就業人員和計算機愛好者的參考書。
推薦序
海濤2008年在我的團隊做過軟體開發工程師。他是一個很細心的員工，對面試這個話題很感興趣，經常和我及其他員工討論，積累了很多面試方面的技巧和經驗。他曾跟我提過想要寫本有關面試的書，三年過後他把書寫出來了！他是一個有目標、有耐心和持久力的人。
我在微軟做了很多年的面試官，後面七年多作為把關面試官也面試了很多應聘者。應聘者要想做好面試，確實應把面試當作一門技巧來學習，更重要的是要提高自身的能力。我遇到很多應試者可能自身能力也不差但因為不懂得怎樣回答提問，不能很好發揮。也有很多校園來的應聘者也學過數據結構和算法分析，可是到處理具體問題時不能用學過的知識來有效地解決問題。這些朋友讀讀海濤的這本書，會很受益，在面試中的發揮也會有很大提高。這本書也可以作為很好的教學補充資料，讓學生不只學到書本知識，也學到解決問題的能力。
在向我匯報的員工中有面試發揮很好但工作平平的，也有面試一般但工作優秀的。對於追求職業發展的人來說，通過面試只是邁過一個門檻而不是目的，真正的較量是在入職後的成長。就像學釣魚，你可能在有經驗的垂釣者的指導下能釣到幾條魚，但如果沒有學到垂釣的真諦，離開了指導者你可能就很難釣到很多魚。我希望讀這本書的朋友不要只學一些技巧來對付面試，而是通過學習如何解決面試中的難題來提高自己的編程和解決問題的能力，進而提高自信心，在職場中能迅速成長。
徐鵬陽（Pung Xu）
Principal Development Manager, Search Technology Center Asia
Microsoft
前言
2011年9月份以來，我的面試題部落格點擊率上升很快，累計點擊量超過了70萬，並且平均每天還會增加約3000次點擊。每一年隨著秋季新學期的開始，新一輪招聘高峰也即將來到。這不禁讓我想起幾年前自己找工作的情形。那個時候的我，也是在網路的各個角落搜尋面試經驗，儘可能多地收集各個公司的面試題。
當時網上的面試經驗還很零散，應聘者如果想系統地收集面試題，需要付出很大的努力。於是我萌生了一個念頭，在部落格上系統地收集、整理有代表性的面試題，這樣可以極大地方便後來人。經過一段時間的準備，我於2007年2月在網易部落格上發表了第一篇關於編程面試題的部落格。
在過去4年多的日子裡，我陸續發表了60餘篇關於面試題的部落格。隨著部落格數目的增加，我也逐漸意識到一篇篇部落格仍然是零散的。一篇部落格只是單純地分析一個面試題，但對解題思路缺乏系統性的梳理。於是在2010年10月我有了把部落格整理成一本書的想法。經過一年的努力，這本書終於和讀者見面了。
本書內容
 全書分為7章，各章的主要內容如下：
第1章介紹面試的流程。通常整個面試過程可以分為電話面試、共享桌面遠程面試和現場面試3個階段，每一輪面試又可以分為行為面試、技術面試和應聘者提問3個環節。本章詳細討論了面試中每一環節需要注意的問題。其中第1.3.2節深入討論了技術面試中的5個要素，是全書的大綱，接下來的第2～6章逐一討論每個要點。
第2章梳理應聘者接受技術面試時需要用到的基礎知識。本章從程式語言、數據結構及算法三方面總結了程式設計師面試的知識點。
第3章討論應聘者在面試時寫出高質量代碼的3個要點。通常面試官除了期待應聘者寫出的代碼能夠完成基本的功能之外，還能應對特殊情況並對非法輸入進行合理的處理。讀完這一章，讀者將學會如何從規範性、完整性和魯棒性3個方面提高代碼的質量。
第4章總結在編程面試中解決難題的常用思路。如果在面試過程中遇到複雜的難題，應聘者最好在寫代碼之前形成清晰的思路。讀者在讀完這一章之後將學會如何用畫圖、舉例和分解複雜問題3種思路來解決問題。
第5章介紹如何最佳化代碼的時間效率和空間效率。如果一個問題有多種解法，面試官總是期待應聘者能找到最優的解法。讀完這一章，讀者將學會最佳化時間效率及空間換時間的常用算法。
第6章總結面試中的各項能力。面試官在面試過程中會一直關注應聘者的學習能力和溝通能力。除此之外，有些面試官還喜歡考查應聘者的知識遷移能力、抽象建模能力和發散思維能力。讀完這一章，讀者將學會如何培養和運用這些能力。
第7章是兩個面試的案例。在這兩個案例中，我們將看到應聘者在面試過程中的哪些舉動是不好的行為，而哪些表現又是面試官所期待的行為。衷心地希望應聘者能在面試時少犯甚至不犯錯誤，完美地表現出自己的綜合素質，最終拿到心儀的Offer。
本書特色
 正如前面提到的那樣，本書的原型是我過去4年多陸陸續續發表的幾十篇部落格，但這本書也不僅僅是這些部落格的總和，它在部落格的基礎上添加了如下內容。
本書試圖以面試官的視角來剖析面試題。本書前6章的第一節都是“面試官談面試”，收錄了分布在不同IT企業（或者IT部門）的面試官們對代碼質量、應聘者如何形成及表達解題思路等方面的理解。在本書中穿插著幾十條“面試小提示”，是我作為面試官給應聘者在面試方法、技巧方面的建議。在第7章的案例中，“面試官心理”揭示了面試官在聽到應聘者不同回答時的心理活動。應聘者如果能了解面試官的心理活動，無疑能在面試時更好地表現自己。
本書總結了解決面試難題的常用方法，而不僅僅只是解決一道道零散的題目。在仔細分析、解決了幾十道典型的面試題之後，我發現其實是有一些通用的方法可以在面試的時候幫助我們解題的。舉個例子，如果面試的時候遇到的題目很難，我們可以試圖把一個大的複雜的問題分解成若干個小的簡單的子問題，然後遞歸地去解決這些子問題。再比如，我們可以用數組實現一個簡單的哈希表解決一系列與字元串相關的面試題。在詳細分析了一道面試題之後，很多章節都會在“相關題目”中列舉出同類型的面試題，並在“舉一反三”中總結解決這一類型題目的方法和要點。
本書收集的面試題是都是各大公司的編程面試題，極具實戰意義。包括谷歌、微軟在內的知名IT企業在招聘的時候，都非常重視應聘者的編程能力，編程技術面試也是整個面試流程中最為重要的一個環節。本書選取的題目都是被各大公司面試官反覆採用的編程題。如果讀者一開始覺得書中的有些題目比較難，那也正常，沒有必要感到氣餒，因為像谷歌、微軟這樣的大企業的面試本身就不簡單。讀者逐步掌握了書中總結的解題方法之後，編程能力和分析複雜問題的能力將會得到很大的提升，再去大公司面試將會輕鬆很多。
本書附帶提供了50道編程題的完整的原始碼，其中包含了每道題的測試用例。很多面試官在應聘者寫完程式之後，都會要求應聘者自己想一些測試用例來測試自己的代碼，一些沒有實際項目開發經驗的應聘者不知道如何做單元測試。相信讀者朋友在讀完這本書之後就會知道如何從基本功能測試、邊界值測試、性能測試等方面去設計測試用例，從而提高編寫高質量代碼的能力。
本書體例
在本書的正文中間或者章節的末尾，穿插了不少特殊體例。這些體例或用來給應聘者提出建議，或用來總結解題方法，希望能夠引起讀者的注意。
面試小提示：
本條目是從面試官的角度對應聘者的建議或者希望應聘者能夠注意到的細節。
原始碼：
讀者將在本條目中看到一個格式為XX_YYYYY或者XX_Y_ZZZZZ的項目名稱，該名稱與用Visual Studio打開檔案之後看到的項目名稱對應。本書附帶的原始碼請到電子工業出版社的官方網站下載。讀者下載原始碼並解壓縮之後，請用Visual Studio 2008或者更新的版本閱讀或者運行代碼。
測試用例：
本條目列舉應聘者在面試時可以用來測試代碼是否完整、魯棒的單元測試用例。通常本書從基本功能、邊界值、無效的輸入等方面測試代碼的完整性和魯棒性，針對在時間效率或者空間效率有要求的面試題還包含性能測試的測試用例。
本題考點：
本條目總結面試官採用一道面試題的考查要點。
相關題目：
本條目列舉一些和詳細分析的面試例題相關或者類似的面試題。
舉一反三：
本條目從解決面試例題中提煉出常用的解題方法。這些解題方法能夠套用到解決其他同類型的問題中去，達到舉一反三的目的。
面試官心理：
在第七章的面試案例中，本條目用來模擬面試官聽到應聘者的回答之後的心理活動。
關於遺漏的問題
由於時間倉促，再加上筆者的能力有限，書中難免會有一些遺漏。今後一旦發現遺漏的問題，我將第一時間在部落格上公布勘誤信息。讀者如果發現任何問題或者有任何建議，也請在部落格上留言、評論，或者通過微博和我聯繫。
致謝
在寫部落格及把部落格整理成書的過程中，我得到了很多人的幫助。沒有他們，也就沒有這本書。因此，我想在這裡對他們誠摯地說一聲：謝謝！
首先我要謝謝個人部落格上的讀者。網友們的鼓勵讓我在部落格上的寫作從2007年2月開始堅持到了現在。也正是由於網友們的鼓勵，我最終下定決心把部落格整理成一本書。
在本書的寫作過程中，我得到了很多同學、同事的幫忙，包括Autodesk的馬凌洲、劉景勇、王海波，支付寶殷焰，百度的張珺、張曉禹，Intel的尹彥，交通銀行的朱麟，淘寶的堯敏，微軟的陳黎明、田超，NVidia的吳斌，SAP的何幸傑和華為的韓偉東（在書稿寫作階段他還在盛大工作）。感謝他們和大家分享了對編程面試的理解和思考。同時還要感謝GlaxoSmithKline Investment的Recruitment &HRISManager蔡詠來（也是2008年把我招進微軟的HR）和大家分享了微軟所推崇的STAR簡歷模型。還要感謝在微軟期間我的兩個老闆徐鵬陽和Matt Gibbs，他們都是在微軟有十幾年面試經驗的資深面試官，對面試有著深刻的理解。感謝二位在百忙之中抽時間為本書寫序，為本書增色不少。
我同樣要感謝現在思科的老闆Min Lu及TQSG上海團隊的同事王劦、趙斌和朱波對我的理解。他們在我寫作期間替我分擔了大量的工作，讓我能夠集中更多的精力來寫書。
感謝電子工業出版社的工作人員，尤其是張春雨和趙樹剛的幫助。兩位編輯大到全書的構架，小到文字的推敲，都給予了我極大的幫助，從而使本書的質量有了極大的提升。
本書還得到了很多朋友的支持和幫助，限於篇幅，雖然不能在此一一說出他們的名字，但我一樣對他們心存感激。
最後，我要衷心地感謝我的愛人劉素雲。感謝她在過去一年中對我的理解和支持，為我營造了一個溫馨而又浪漫的家，讓我能夠心無旁騖地寫書。我無以為謝，謹以此書獻給她及我們尚未出生的小寶寶。
2011年9月8日清晨於上海三涇南宅
目錄
第1章 面試的流程 1
1.1 面試官談面試 1
1.2 面試的三種形式 2
1.2.1 電話面試 2
1.2.2 共享桌面遠程面試 3
1.2.3 現場面試 4
1.3 面試的三個環節 5
1.3.1 行為面試環節 5
應聘者的項目經驗 6
應聘者掌握的技能 7
回答“為什麼跳槽” 8
1.3.2 技術面試環節 10
紮實的基礎知識 10
高質量的代碼 11
清晰的思路 14
最佳化效率的能力 15
優秀的綜合能力 16
1.3.3 應聘者提問環節 17
1.4 本章小結 18
第2章 面試需要的基礎知識 20
2.1 面試官談基礎知識 20
2.2 程式語言 22
2.2.1 C++ 22
面試題1：賦值運算符函式 24
經典的解法，適用於初級程式設計師 25
考慮異常安全性的解法，高級程式設計師必備 26
2.2.2 C# 27
面試題2：實現Singleton模式 31
不好的解法一：只適用於單執行緒 31
不好的解法二：可用於多執行緒但效率不高 32
可行的解法：同步鎖前後兩次判斷 33
推薦的解法一：利用靜態構造函式 34
推薦的解法二：按需創建實例 34
解法比較 35
2.3 數據結構 36
2.3.1 數組 36
面試題3：二維數組中的查找 38
2.3.2 字元串 42
面試題4：替換空格 44
O(n2)的解法，不足以拿到Offer 45
O(n)的解法，搞定Offer就靠它 46
2.3.3 鍊表 49
面試題5：從尾到頭列印鍊表 51
2.3.4 樹 53
面試題6：重建二叉樹 55
2.3.5 棧和佇列 58
面試題7：用兩個棧實現佇列 59
2.4 算法和數據操作 62
2.4.1 查找和排序 63
面試題8：旋轉數組的最小數字 66
2.4.2 遞歸和循環 71
面試題9：斐波那契數列 73
效率很低的解法，面試官不會喜歡 73
面試官期待的實用解法 74
O(logn)但不夠實用的解法 74
解法比較 75
2.4.3 位運算 77
面試題10：二進制中1的個數 78
可能引起死循環的解法 79
常規解法 79
能給面試官帶來驚喜的解法 80
2.5 本章小結 82
第3章 高質量的代碼 84
3.1 面試官談代碼質量 84
3.2 代碼的規範性 86
3.3 代碼的完整性 87
從3方面確保代碼的完整性 87
3種錯誤處理的方法 88
面試題11：數值的整數次方 90
自以為題目簡單的解法 90
全面但不夠高效的解法，離Offer已經很近了 90
全面又高效的解法，確保能拿到Offer 92
面試題12：列印1到最大的n位數 94
跳進面試官陷阱 94
在字元串上模擬數字加法94
把問題轉換成數字排列 97
面試題13：在O(1)時間刪除鍊表結點 99
面試題14：調整數組順序使奇數位於偶數前面 102
只完成基本功能的解法，僅適用於初級程式設計師 102
考慮可擴展性的解法，能秒殺Offer 104
3.4 代碼的魯棒性 106
面試題15：鍊表中倒數第k個結點 107
面試題16：反轉鍊表 112
面試題17：合併兩個排序的鍊表 114
面試題18：樹的子結構 117
3.5 本章小結 121
第4章 解決面試題的思路 123
4.1 面試官談面試思路 123
面試題19：二叉樹的鏡像 125
4.2 畫圖讓抽象問題形象化 125
面試題20：順時針列印矩陣 127
4.3 舉例讓抽象問題具體化 131
面試題21：包含MIN函式的棧 132
面試題22：棧的壓入、彈出序列 134
面試題23：從上往下列印二叉樹 137
面試題25：二叉樹中和為某一值的路徑 143
4.4 分解讓複雜問題簡單化 146
面試題26：複雜鍊表的複製 147
面試題27：二叉搜尋樹與雙向鍊表 151
面試題28：字元串的排列 154
4.5 本章小結 158
第5章 最佳化時間和空間效率 160
5.1 面試官談效率 160
5.2 時間效率 162
面試題29：數組中出現次數超過一半的數字 163
基於Partition函式的O(n)算法 163
利用數組特點的O(n)算法 165
解法比較 166
面試題30：最小的k個數 167
O(n)的算法，只當可以修改輸入數組時可用 167
O(nlogk)的算法，適合處理海量數據 168
解法比較 169
面試題31：連續子數組的最大和 171
舉例分析數組的規律 171
套用動態規劃法173
面試題32：從1到n整數中1出現的次數 174
不考慮效率的解法，想拿Offer有點難 174
明顯提高效率的解法，讓面試官耳目一新 175
面試題33：把數組排成最小的數 177
5.3 時間效率與空間效率的平衡 181
面試題34：醜數 182
逐個判斷整數是不是醜數的解法 182
創建數組保存已經找到的醜數的解法 183
面試題35：第一個只出現一次的字元 186
面試題36：數組中的逆序對189
面試題37：兩個鍊表的第一個公共結點193
5.4 本章小結 196
第6章 面試中的各項能力 198
6.1 面試官談能力 198
6.2 溝通能力和學習能力 200
溝通能力 200
學習能力 200
善於學習、溝通的人也善於提問 201
6.3 知識遷移能力 203
面試題38：數字在排序數組中出現的次數 204
面試題39：二叉樹的深度 207
重複遍歷結點的解法，不足以打動面試官 209
只遍歷結點一次的解法，正是面試官喜歡的 209
面試題40：數組中只出現一次的數字 211
面試題41：和為s的兩個數字VS和為s的連續正數序列 214
面試題42：翻轉單詞順序VS左旋轉字元串 218
6.4 抽象建模能力 222
面試題43：n個骰子的點數 223
基於遞歸求骰子點數，時間效率不夠高 223
基於循環求骰子點數，時間性能好 224
面試題44：撲克牌的順子 226
面試題45：圓圈中最後剩下的數字 228
經典的解法，用循環鍊表模擬圓圈 229
創新的解法，拿到Offer不在話下 230
6.5 發散思維能力 232
面試題46：求1+2+…+n 233
利用構造函式求解 234
利用虛函式求解 234
利用函式指針求解 235
利用模板類型求解 236
面試題47：不用加減乘除做加法 237
面試題48：不能被繼承的類 239
常規的解法：把構造函式設為私有函式 239
新奇的解法：利用虛擬繼承240
6.6 本章小結 241
第7章 兩個面試案例 243
7.1 案例一：（面試題49）把字元串轉換成整數 244
7.2 案例二：（面試題50）樹中兩個結點的最低公共祖先 252
