名企面試官精講典型編程題

第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道編程題的完整的源代碼，其中包含了每道題的測試用例。很多面試官在應聘者寫完程序之後，都會要求應聘者自己想一些測試用例來測試自己的代碼，一些沒有實際項目開發經驗的應聘者不知道如何做單元測試。相信讀者朋友在讀完這本書之後就會知道如何從基本功能測試、邊界值測試、性能測試等方面去設計測試用例，從而提高編寫高質量代碼的能力。

目錄

第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

面試題24：二叉搜索樹的後序遍歷序列140

面試題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

基於循環求骰子點數，時間性