技术移民宝典：程序员海外求职锦囊

专为应聘程序员相关职位的就业人员，特别是打算寻找美国IT公司工作，并想通过技术移民实现美国梦的程序员量身打造

《技术移民宝典：程序员海外求职锦囊》介绍了如何在硅谷求职，以及剖析了具有代表性的43 道热门硅谷公司的面试题，从面试技巧、基础知识、解题思路和效率优化等方面总结面试和解题规律。《技术移民宝典：程序员海外求职锦囊》分为四部分共15 章，包含出国工作途径、IT 求职准备、实战访谈，以及常见数据结构、算法、大数据、系统设计等方面的题目和解题思路，并提炼出解题的5 个步骤：复述/提问、举例、观察、编码和测试。《技术移民宝典：程序员海外求职锦囊》精选出的面试题是硅谷热门公司的高频题，可以用来作为面试前的练习。对于每道题，本书尽可能给出多种解法，对于解决日常工作中遇到的问题也有一定启发性。

《技术移民宝典：程序员海外求职锦囊》适合正在应聘程序员相关职位的就业人员阅读和参考，特别是打算寻求美国IT 公司职位并想通过技术移民实现美国梦的程序员。

陈东锋

曾是微软和IBM总部的软件研发工程师，目前在一家大型互联网公司从事广告、交易、架构等方面的研发和管理工作。

涂峰

2008年获得复旦大学计算机软件与理论专业硕士学位，现在硅谷某大数据创业公司担任系统架构师。在此之前，曾在百度商务搜索部商业知心广告业务担任高级软件工程师、EMC统一存储部和IBM系统技术部担任资深软件工程师，主要负责底层系统开发方向。

第一部分 硅谷求职
第1 章 硅谷公司 3
1．1 硅谷简介 3
1．2 传奇旗帜 7
1．2．1 微软 8
1．2．2 谷歌 10
1．2．3 亚马逊 11
1．2．4 Facebook 13
1．2．5 Twitter 14
1．2．6 Epic 14
1．3 技术移民 15
1．3．1 签证和绿卡 16
1．3．2 税率和生活 19
第2 章 求职准备 21
2．1 职位选择 23
2．2 公司选择 24
2．3 人际关系 27
2．4 求职渠道 30
第3 章 简历 32
3．1 简历特点 33
3．2 简历结构 36
3．3 简历优化 39
第4 章 面试 43
4．1 面试准备 43
4．2 面试流程 49
4．3 编程面试 51
4．4 注意事项 52
第5 章 聘书与职业发展 56
5．1 聘书 57
5．1．1 聘书要素 57
5．1．2 决策因子 58
5．1．3 薪酬谈判 61
5．1．4 接受、延期或婉拒 63
5．2 职业发展 64
5．3 优秀工程师 66
5．4 职业晋升 70
第二部分 实战访谈
第6 章 对身在美国和即将赴美工作的工程师访谈 77
互联网资深大牛董飞 77
创业者徐淼华 82
留美计算机博士张� 85
微软软件工程师乔成 88
Broadcom 硬件测试工程师蒋波� 90
硅谷初创公司大数据处理软件工程师常新宇 93
第三部分 算法面试
第7 章 俩指针 99
面试题1：两数之和I ☆☆ 99
面试题2：两数之和II ☆☆☆☆ 101
面试题3：Top K☆☆☆ 103
面试题4：两数组第k 个值☆☆☆☆☆ 107
面试题5：有序数组去重☆ 109
面试题6：数组分水岭☆☆☆ 111
第8 章 动态规划 113
面试题7：最长递增子序列☆☆☆☆ 114
面试题8：最小化数组乘积☆☆☆☆ 116
面试题9：刷房子☆☆☆ 117
面试题10：编辑距离☆☆☆☆ 118
面试题11：最长回文子串☆☆☆☆☆ 120
面试题12：最大公共子串☆☆☆☆ 121
第9 章 优先遍历 123
面试题13：填充图像☆☆☆☆ 123
面试题14：单词替换规则☆☆☆☆ 124
面试题15：有向图遍历☆☆☆☆ 126
第10 章 哈希 128
面试题16：最长不同字符的子串☆☆☆☆ 128
面试题17：常数时间插入删除查找☆☆☆ 129
面试题18：对数时间范围查询☆☆☆☆ 130
面试题19：实现LRU 缓存☆☆☆☆ 130
面试题20：经过最多点的直线☆☆☆ 133
第11 章 堆栈 136
面试题21：局部最大值☆☆☆ 136
面试题22：数据流最大值☆☆☆☆ 138
面试题23：产生逆波兰式☆☆☆ 139
面试题24：逆波兰式计算☆☆☆ 140
面试题25：设计Min 栈☆☆☆☆ 142
面试题26：最小公共祖先☆☆ 143
扩展问题1 144
扩展问题2 147
第12 章 排列组合 149
面试题27：翻译手机号码☆☆☆ 149
面试题28：数组签名☆☆☆☆ 151
面试题29：组合和☆☆☆ 153
面试题30：N 皇后☆☆☆☆ 155
第13 章 杂项 157
面试题31：实现迭代器peek() ☆☆☆ 157
面试题32：实现复杂的迭代器☆☆☆☆ 158
面试题33：实现BlockingQueue ☆☆☆ 160
面试题34：随机数产生器☆☆☆☆☆ 161
面试题35：找出明星☆☆☆ 163
面试题36：根据概率分布产生随机数☆☆☆☆ 163
面试题37：随机采样☆☆☆ 164
面试题38：统计电话号码个数☆☆☆ 165
面试题39：海量数据高频词☆☆☆ 166
面试题40：多台机器的中值☆☆☆☆ 166
第四部分 系统设计
第14 章 实战技巧及准备 171
14．1 实战技巧 172
技巧1：不要惊慌 172
技巧2：与面试官积极交流 173
技巧3：厘清需求 173
技巧4：先框架再细节 174
技巧5：留意错误处理 174
14．2 常见知识点 175
14．3 如何准备 177
第15 章 系统设计例题 180
面试题41：大数据存储☆☆☆☆ 180
面试题42：大并发处理☆☆☆☆ 182
面试题43：大数据收集☆☆☆☆ 185
系统知识阅读 188
附录A 数据结构与算法 191
附录B 海量数据结构 192

随着越来越多IT 工程师寻找国外工作机会，介绍和总结国外热门IT 公司面试过程及面试内容的需求变得越来越迫切。美国最新移民改革CIR 方案更倾向于技术移民，这将使得今后会有更多国内程序员去美国工作。笔者亲身参与了国内和美国一些热门IT 公司的面试，同时也作为面试官面试过不少人，熟知海内外IT 公司招聘流程和面试方式。通常来说，去美国IT 公司工作有三种途径。

●直接申请美国公司职位，拿H1B 签证工作。不少热门IT 公司直接在国内招人，比如Facebook、Amazon、Microsoft、Google 等。越来越多的程序员选择这条路，一方面是因为美国签证的条件放宽了，另一方面是因为硅谷公司面试并没有比国内公司难多少。

●在国内的跨国公司工作一年后，内部转组到美国的分部，使用L1 签证。例如，从微软中国转至微软西雅图总部工作。

●申请攻读美国学校的计算机科学硕士或博士学位，毕业后再找工作，即由F1 签证转为H1B 签证。

这三种途径都需要成功通过公司的技术面试。热门IT 企业的面试方式大致相同：1 或2 轮电话面试，通过之后，又有4 或5 轮的现场面谈。其中80%的面试是技术面试，每轮技术面试大约45 分钟，扣除双方自我介绍和提问时间，花在技术面试的时间大约为30 分钟。由于技术面试时间的限制，面试的题目一般不会太难，比大学生编程比赛（ACM）的题目简单很多，但是，面试者需要具备一些编程面试技巧，并对算法、数据结构熟练掌握才能在限定时间内完成。这对要求在白板上写程序和无Bug（Bug free）的公司来说尤其重要，比如Facebook。

在编程面试过程中，光有解法却写不出来代码是行不通的，这只会让面试官觉得你夸夸其谈，不会实际编程。在编程面试里，切记“让代码说话”这条准则。在本书面试题相关的章节中，笔者贴出了面试题的全部代码，是为了更多时候让代码来说话。针对每道面试题，我们通常会有如下步骤。

●复述/提问：用自己的话复述面试官的题目，以免偏题。面试官给出的面试题并非一开始就很明确，需要多次问答来确定题意、边界条件、时间和数据结构限制等。

●举例：可以与提问同步进行，主要用来确认输入和输出结果。

● 观察：通过举例来总结规律，思考可能使用到的结构和算法，然后设计一种你认为最优的算法。

●编码：和面试官沟通你的算法之后，开始在白板编码。

●测试：使用个别例子，把你的代码测试一遍。

在以上5 个步骤里，看时间是否充裕，有些步骤可以省略。比如，如果面试官已经把问题说得很清楚了，那么复述可以省略。在本书当中，笔者也会按照这5 个步骤的解题技巧来阐述面试题的解题方案。

笔者根据自身作为面试官的多年经历，并收集了网上众多的热门IT 公司面试题目，精选了43 道题来代表当前热门和高频的面试题。本书内容覆盖了基础的数据结构：数组、链表、树、堆栈、字符串等，以及高频率出现的算法，如动态规划、俩指针、排列组合、优先遍历等。此外，还覆盖了系统设计解题思路和案例分析。涂峰加入了再版的写作，以自身“肉身翻墙”的经历为本书丰富了求职准备、实战访谈、系统设计等章节。本书的内容分为以下四个部分。

●硅谷求职：硅谷公司文化、技术移民、简历、面试、录用谈判和职业发展。

●实战访谈：先行者所传授的出国途径、面试技巧、硅谷企业文化、职业规划。

●算法面试：动态规划、俩指针、优先遍历、哈希、排列组合。

●系统设计：实战技巧、案例分析、阅读推荐。

此外，附录还提供了数据结构和算法总结及海量数据分析，以供读者快速查阅。

本书有以下几个特点。

●介绍硅谷求职和技术移民美国。

●对已实现技术移民美国的先行者进行访谈。

●精选出的面试题是硅谷各家热门公司的高频题，极其具有代表性。

●完整介绍了系统设计题的实战技巧，对应聘高级职位者很有借鉴意义。

●总结了常见数据结构的对应算法，提炼出一套解题规律。对于类似题目，有很强的借鉴意义。

●本书提供了完整的可运行的源代码。

●对于每道题，本书尽可能给出多种解法，对解决我们在日常工作中遇到的问题有一定启发性。

虽然本书大部分的代码是用Java 编写的，但很容易转化为C++/.NET 代码，因此，本书也适合C++/.NET 程序员阅读。由于本人水平有限，书中的题目并不能完全代表当前热门公司的编程面试的各个方面，虽然经过多轮审核，不少解法依然可能有漏洞或者错误，希望广

大读者能给予指正。

在本书的写作过程中，我得到了很多朋友、同事的帮忙，包括汪纯子、周泽勇、俞明辉、吴盛萱、杨超、尹杭锋和于东东等。感谢他们帮忙校对文字、审核代码。同时，感谢电子工业出版社的工作人员，尤其是符隆美——大到全书的架构，小到文字的推敲，她都给予了我极大的帮助，从而使本书的质量有了极大的提升。

最后，我要衷心地感谢我的妻子Emily。感谢她在过去几年中对我的理解和支持，为我营造了一个温馨而浪漫的家，让我能够心无旁骛地写书。谨以此书献给她以及我们的女儿Ella。

陈东锋

2015 年11 月于上海张江