圖書信息
書名：進軍矽谷 –程式設計師面試揭秘宣傳語：技術移民參考手冊
作者：陳東鋒 著
ISBN ：978-7-121-22566-6
出版時間：2014年3月出版
定價：55.00元
頁數：320頁
開本：16開
編輯推薦
?《進軍矽谷——程式設計師面試揭秘》是市面上第一本介紹矽谷求職和技術移民美國的書。精選矽谷各家熱門公司的高頻面試題，極具代表性。
總結常見數據結構的對應算法，提煉出一套解題規律供廣大求職者借鑑。
提供了完整可運行的原始碼。
對於每道題，儘可能給出多種解法，給日常工作中遇到問題的程式設計師更多啟發。
目錄
第一部分 矽谷求職第1章 矽谷公司 3
1.1 矽谷簡介 3
1.2 傳奇旗幟 7
1.2.1 微軟 8
1.2.2 谷歌 9
1.2.3 亞馬遜 10
1.2.4 Twitter 12
1.2.5 Epic 12
1.3 技術移民 13
1.3.1 簽證和綠卡 14
1.3.2 稅率和生活 16
第2章 求職準備 19
2.1 職位選擇 21
2.2 公司選擇 22
2.3 人際關係 24
2.4 求職渠道 27
第3章 簡歷 29
3.1 簡歷特點 30
3.2 簡歷結構 33
3.3 簡歷最佳化 35
第4章 面試 39
4.1 面試流程 40
4.2 編程面試 42
4.3 注意事項 43
第5章 聘書與職業發展 47
5.1 聘書 48
5.1.1 聘書要素 48
5.1.2 決策因子 49
5.1.3 薪酬談判 52
5.1.4 接受、延期或婉拒 54
5.2 職業發展 55
第二部分 數據結構
第6章 數組 59
面試題1：兩數之和I ☆☆ 59
面試題2：兩數之和II ☆☆☆ 61
面試題3：兩數之和III ☆☆☆☆ 62
面試題4：數組旋轉 ☆☆☆ 64
面試題5：最大下標距離 ☆☆☆☆ 65
面試題6：重疊區間個數 ☆☆ 67
面試題7：插入區間 ☆☆☆ 69
面試題8：合併區間 ☆☆☆☆ 71
面試題9：數組配對 ☆☆☆ 72
面試題10：數位重組 ☆☆☆ 73
面試題11：產生隨機數 ☆☆ 75
面試題12：Top K I ☆☆☆ 76
面試題13：Top K II ☆☆☆☆ 79
面試題14：兩數組第k個值 ☆☆☆☆☆ 80
面試題15：兩數組中值 ☆☆☆☆☆ 82
面試題16：旋轉數組最小值 ☆☆☆ 84
面試題17：旋轉數組搜尋 ☆☆☆ 85
面試題18：首個正數 ☆☆☆☆ 86
面試題19：合併有序數組 ☆☆ 88
面試題20：三角形 ☆☆ 89
面試題21：二維數組搜尋 ☆☆☆ 90
面試題22：區間搜尋 ☆☆☆☆ 92
面試題23：插入位置 ☆☆ 94
面試題24：矩陣清零 ☆☆☆ 95
面試題25：螺旋矩陣 ☆☆☆☆ 98
第7章 鍊表 101
面試題26：合併鍊表 ☆☆ 102
面試題27：環的長度 ☆☆☆ 103
面試題28：反轉鍊表 ☆☆ 105
面試題29：分組反轉鍊表 ☆☆☆☆ 109
面試題30：兩數相加 ☆☆☆ 110
面試題31：鍊表分區 ☆☆☆ 112
面試題32：鍊表去重 ☆ 114
第8章 樹 117
面試題33：二叉搜尋樹轉為雙向鍊表 ☆☆☆☆ 118
面試題34：最小公共祖先I ☆☆ 120
面試題35：最小公共祖先II ☆☆☆ 121
面試題36：最小公共祖先III ☆☆☆☆ 124
面試題37：最小公共祖先IV ☆☆☆☆ 125
面試題38：路徑和I ☆☆ 128
面試題39：路徑和II ☆☆☆☆ 129
面試題40：平衡二叉樹 ☆☆☆☆ 131
面試題41：樹的鏡像 ☆☆ 132
面試題42：中序下個節點 ☆☆☆ 134
面試題43：二叉搜尋樹近值 ☆☆☆ 135
面試題44：二叉搜尋樹KNN ☆☆☆☆ 136
面試題45：實現二叉搜尋樹疊代器 ☆☆☆☆ 138
面試題46：充實橫向指針 ☆☆☆ 140
面試題47：恢復二叉搜尋樹 ☆☆☆☆ 142
面試題48：按層遍歷二叉樹 ☆☆☆ 144
面試題49：二叉樹最大路徑和 ☆☆☆☆ 145
第9章 字元串 148
面試題50：字元判重 ☆☆☆ 148
面試題51：產生括弧 ☆☆☆☆ 150
面試題52：提取單詞I ☆☆☆☆ 151
面試題53：提取單詞II ☆☆☆☆ 153
面試題54：字元交替 ☆☆☆ 154
面試題55：字元串相乘 ☆☆☆☆ 155
面試題56：數字驗證 ☆☆☆ 157
面試題57：字元串轉為十進制數 ☆☆ 160
面試題58：提取IP位址 ☆☆☆ 161
面試題59：正則匹配 ☆☆☆☆☆ 163
第三部分 算法
第10章 倆指針 167
面試題60：有序數組去重 ☆ 167
面試題61：三數之和 ☆☆☆ 169
面試題62：股票買賣 ☆☆ 171
面試題63：三色排序 ☆☆☆☆ 172
面試題64：蛙跳 ☆☆☆ 174
面試題65：容器盛水I ☆☆☆ 176
面試題66：容器盛水II ☆☆☆☆ 177
面試題67：數組分水嶺 ☆☆☆ 179
第11章 動態規劃 181
面試題68：最長遞增子序列 ☆☆☆☆ 182
面試題69：最小化數組乘積 ☆☆☆☆ 183
面試題70：股票買賣II ☆☆☆☆ 185
面試題71：數組最大和 ☆☆☆ 186
面試題72：二維數組最小路徑和 ☆☆☆ 187
面試題73：三角形最小路徑 ☆☆☆ 188
面試題74：爬樓梯 ☆☆ 189
面試題75：迷宮路徑數 ☆☆ 190
面試題76：刷房子 ☆☆☆ 192
面試題77：數字解碼 ☆☆☆ 193
面試題78：子串個數 ☆☆☆☆ 194
面試題79：編輯距離 ☆☆☆☆ 196
面試題80：交替字元串 ☆☆☆☆☆ 197
面試題81：最長回文子串 ☆☆☆☆☆ 198
面試題82：回文分割 ☆☆☆☆ 199
面試題83：最大公共子串 ☆☆☆☆ 201
面試題84：字元串洗牌 ☆☆☆☆☆ 202
第12章 優先遍歷 205
面試題85：填充圖像 ☆☆☆☆ 205
面試題86：封閉區間個數 ☆☆☆☆ 206
面試題87：填充封閉區間 ☆☆☆☆☆ 208
面試題88：單詞查找 ☆☆☆ 210
面試題89：單詞變換 ☆☆☆☆ 211
面試題90：單詞替換規則 ☆☆☆☆ 213
面試題91：有向圖遍歷 ☆☆☆☆ 215
第13章 哈希 217
面試題92：最長連續序列 ☆☆☆☆ 217
面試題93：變位詞 ☆☆☆ 218
面試題94：最長不同字元的子串 ☆☆☆☆ 220
面試題95：最小字元視窗 ☆☆☆☆ 221
面試題96：單詞拼接 ☆☆☆☆☆ 223
面試題97：常數時間插入刪除查找 ☆☆☆ 224
面試題98：對數時間範圍查詢 ☆☆☆☆ 225
面試題99：實現LRU快取 ☆☆☆☆ 226
面試題100：經過最多點的直線 ☆☆☆ 229
第14章 堆疊 232
面試題101：局部最大值 ☆☆☆ 232
面試題102：數據流最大值 ☆☆☆☆ 234
面試題103：最大四方形 ☆☆☆☆☆ 235
面試題104：合併多個有序鍊表 ☆☆☆☆ 239
面試題105：產生逆波蘭式 ☆☆☆ 240
面試題106：逆波蘭式計算 ☆☆☆ 241
面試題107：簡化檔案路徑 ☆☆☆ 243
面試題108：括弧驗證 ☆☆ 244
面試題109：最長有效括弧 ☆☆☆ 245
面試題110：設計Min棧 ☆☆☆☆ 247
面試題111：中序遍歷 ☆☆☆ 248
面試題112：列印路徑 ☆☆☆☆ 249
面試題113：二叉搜尋樹兩點之和 ☆☆☆☆ 251
面試題114：矩陣Top K ☆☆☆☆ 253
第15章 排列組合 256
面試題115：翻譯手機號碼 ☆☆☆ 256
面試題116：數組簽名 ☆☆☆☆ 258
面試題117：組合和 ☆☆☆ 259
面試題118：子集合 ☆☆☆ 262
面試題119：全排列 ☆☆☆ 264
面試題120：下一個排列 ☆☆☆☆☆ 266
面試題121：N皇后 ☆☆☆☆ 268
第四部分 綜合面試題
第16章 數學 273
面試題122：Fibonacci數 ☆ 273
面試題123：求冪 ☆☆☆ 274
面試題124：求開方 ☆☆☆☆ 275
面試題125：隨機數產生器 ☆☆☆☆☆ 276
面試題126：找出明星 ☆☆☆ 277
面試題127：聚合數 ☆☆☆ 278
面試題128：根據機率分布產生隨機數 ☆☆☆☆ 279
面試題129：隨機採樣 ☆☆☆ 280
面試題130：數組元素乘積 ☆☆☆ 281
面試題131：訪問計數 ☆☆☆ 282
第17章 位操作 283
面試題132：isPowerOf2() ☆☆ 283
面試題133：isPowerOf4() ☆☆☆☆ 284
面試題134：兩數相除 ☆☆☆☆ 284
面試題135：不用加減乘除做加法 ☆☆☆ 285
面試題136：實現BitSet類 ☆☆☆ 286
面試題137：爬樓梯II ☆☆☆ 287
面試題138：只出現一次的數字 ☆☆ 288
第18章 面向對象 289
面試題139：實現疊代器peek() ☆☆☆ 289
面試題140：實現複雜的疊代器 ☆☆☆☆ 290
面試題141：實現BlockingQueue ☆☆☆ 292
面試題142：Java位元組碼編入 ☆☆ 293
面試題143：依賴注入 ☆☆ 294
第19章 雜項 295
面試題144：垃圾回收機制 ☆☆☆ 295
面試題145：程式崩潰 ☆☆☆☆ 296
面試題146：實現任意讀 ☆☆☆☆ 297
面試題147：實現讀一行 ☆☆☆ 298
面試題148：統計電話號碼個數 ☆☆☆ 299
面試題149：海量數據高頻詞 ☆☆☆ 300
面試題150：多台機器的中值 ☆☆☆☆ 300
附錄A 數據結構與算法 302
附錄B 海量數據結構 303
作者簡介
陳東鋒，博士畢業於北卡羅來納州立大學，就職於IBM總部、微軟總部和百度，創辦過一家網際網路公司。作為面試官，面試了中美兩地不下百個候選者。
前言
隨著越來越多IT工程師尋找國外工作機會，介紹和總結國外熱門IT公司面試過程及面試內容的需求尤為迫切。美國最新移民改革CIR方案更傾向於技術移民，這將使得今後會有更多國內程式設計師去美國工作。筆者親身參與了國內和美國一些熱門IT公司的面試，同時也作為面試官面試過不少人，熟知海內外IT公司招聘流程和面試方式。通常來說，去美國IT公司工作有三種途徑。直接申請美國公司職位，拿H1B簽證工作。不少熱門IT公司直接在國內招人，比如Facebook、Twitter、Microsoft、Google等。越來越多的程式設計師選擇這條路，一方面是因為美國簽證放寬了，另一方面是矽谷公司面試並沒有比國內公司難多少。
在國內的跨國公司工作一年後，內部轉組到美國的分部，使用L1簽證。例如，從微軟中國轉至微軟西雅圖總部工作。
申請攻讀美國學校的計算機科學碩士或博士學位，畢業後再找工作，即由F1簽證轉為H1B簽證。
這三種途徑都需要成功通過公司技術面試。熱門IT企業的面試方式大致相同：1～2輪電話面試，通過之後，又有4～5輪的現場面談。其中80%的面試是技術面試，每輪技術面試大約45分鐘，扣除雙方自我介紹和提問時間，花在技術面試的時間大約為30分鐘。由於技術面試時間的限制，面試的題目一般不會太難，比大學生編程比賽（ACM）的題目簡單很多，但是，面試者需要一些編程面試技巧，以及對算法、數據結構熟練掌握才能在限定時間內完成。這對要求在白板上寫程式和無Bug（Bug free）的公司來說尤其重要，比如Facebook。
在編程面試過程中，光有解法卻寫不出來代碼是行不通的，這只會讓面試官覺得你只會誇誇其談，不會編程而已。在編程面試里，切記“讓代碼說話”這條準則。在本書面試題相關的章節中，筆者貼出了面試題的全部代碼，是為了更多時候讓代碼來說話。針對每道面試題，我們通常會有如下步驟。
複述/提問：用自己的話複述面試官的題目，以免偏題。面試官給出的面試題並非一開始就很明確，需要多次問答來確定題意、邊界條件、時間和數據結構限制等。
舉例：可以與提問同步進行，主要用來確認輸入和輸出結果。
觀察：通過舉例來總結規律，思考可能使用到的結構和算法，然後設計一種你認為最優的算法。
編碼：和面試官溝通你的算法之後，開始在白板編碼。
測試：使用個別例子，把你的代碼測試一遍。
在以上5個步驟里，看時間是否充裕，有些步驟可以省略。比如，如果面試官已經把問題說得很清楚了，那么複述可以省略。在本書當中，筆者也會按照這5個步驟的解題技巧來闡述面試題的解題方案。
筆者根據自身作為面試官的多年經歷，並收集了網上眾多的熱門IT公司面試題目，精選了150道題來代表當前熱門和高頻的面試題。本書內容覆蓋了基礎的數據結構：數組、鍊表、樹、堆疊、字元串等，以及高頻率出現的算法，如動態規劃、倆指針、排列組合、優先遍歷等。本書的內容分為以下四個部分。
矽谷求職和面試：矽谷公司文化、技術移民、簡歷、面試和錄用談判。
常見數據結構：數組、鍊表、樹和圖、堆疊、字元串。
算法：動態規劃、倆指針、優先遍歷、哈希、排列組合。
雜項：系統設計、海量數據分析、面向對象設計、數學和位操作。
此外，附錄還提供了數據結構和算法總結以及海量數據分析，以供讀者快速查閱。
本書含有以下幾個特點。
本書是市面上第一本介紹矽谷求職和技術移民美國的書。
精選出的面試題是矽谷各家熱門公司的高頻題，極其具有代表性。
總結了常見數據結構的對應算法，提煉出一套解題規律。對於類似題目，有著強烈的借鑑意義。
本書提供了完整的可運行的原始碼。
對於每道題，本書儘可能給出多種解法，對我們在日常工作中遇到問題時有一定啟發性。
雖然本書大部分的代碼是用Java編寫，但很容易轉化為C++/.NET代碼，因此，本書也適合C++/.NET程式設計師閱讀。
由於本人水平有限，書中的題目並不能完全代表當前熱門公司的編程面試的各個方面，雖然經過多輪審核，不少解法依然可能有漏洞或者錯誤，希望廣大讀者能給予指正。我已經搭建了一個關於程式設計師出國工作的網站“i碼工”和讀者交流。
在本書的寫作過程中，我得到了很多朋友、同事的幫忙，包括汪純子、周澤勇、俞明輝、吳盛萱、楊超、尹杭鋒和於東東等。感謝他們幫忙校對文字、審核代碼。同時，感謝電子工業出版社的工作人員，尤其是符隆美的幫助。感謝她從大到全書的架構，小到文字的推敲，都給予了我極大的幫助，從而使本書的質量有了極大的提升。
最後，我要衷心地感謝我的妻子徐淼。感謝她在過去幾年中對我的理解和支持，為我營造了一個溫馨而浪漫的家，讓我能夠心無旁騖地寫書。謹以此書獻給她以及我們的女兒Ella。
陳東鋒
2013年10月於上海張江
