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

前言 随着越来越多IT 工程师寻找国外工作机会，介绍和总结国外热门IT 公司面试过程 及面试内容的需求尤为迫切。美国最新移民改革CIR 方案更倾向于技术移民，这将使得 今后会有更多国内程序员去美国工作。笔者亲身参与了国内和美国一些热门IT 公司的 面试，同时也作为面试官面试过不少人，熟知海内外IT 公司招聘流程和面试方式。通 常来说，去美国IT 公司工作有三种途径。 直接申请美国公司职位，拿H1B 签证工作。不少热门IT 公司直接在国内招人， 比如Facebook、Twitter、Microsoft、Google 等。越来越多的程序员选择这条路， 一方面是因为美国签证放宽了，另一方面是硅谷公司面试并没有比国内公司难多 少。 在国内的跨国公司工作一年后，内部转组到美国的分部，使用L1 签证。例如， 从微软中国转至微软西雅图总部工作。 申请攻读美国学校的计算机科学硕士或博士学位，毕业后再找工作，即由F1 签 证转为H1B 签证。 这三种途径都需要成功通过公司技术面试。热门IT 企业的面试方式大致相同：1～ 2 轮电话面试，通过之后，又有4～5 轮的现场面谈。其中80%的面试是技术面试，每 前言 V 轮技术面试大约45 分钟，扣除双方自我介绍和提问时间，花在技术面试的时间大约为 30 分钟。由于技术面试时间的限制，面试的题目一般不会太难，比大学生编程比赛 （ACM）的题目简单很多，但是，面试者需要一些编程面试技巧，以及对算法、数据结 构熟练掌握才能在限定时间内完成。这对要求在白板上写程序和无Bug（Bug free）的 公司来说尤其重要，比如Facebook。 在编程面试过程中，光有解法却写不出来代码是行不通的，这只会让面试官觉得你 只会夸夸其谈，不会编程而已。在编程面试里，切记“让代码说话”这条准则。在本书 面试题相关的章节中，笔者贴出了面试题的全部代码，是为了更多时候让代码来说话。 针对每道面试题，我们通常会有如下步骤。 复述/提问：用自己的话复述面试官的题目，以免偏题。面试官给出的面试题并 非一开始就很明确，需要多次问答来确定题意、边界条件、时间和数据结构限制 等。 举例：可以与提问同步进行，主要用来确认输入和输出结果。 观察：通过举例来总结规律，思考可能使用到的结构和算法，然后设计一种你认 为最优的算法。 编码：和面试官沟通你的算法之后，开始在白板编码。 测试：使用个别例子，把你的代码测试一遍。 在以上5 个步骤里，看时间是否充裕，有些步骤可以省略。比如，如果面试官已经 把问题说得很清楚了，那么复述可以省略。在本书当中，笔者也会按照这5 个步骤的解 题技巧来阐述面试题的解题方案。 笔者根据自身作为面试官的多年经历，并收集了网上众多的热门IT 公司面试题目， 精选了150 道题来代表当前热门和高频的面试题。本书内容覆盖了基础的数据结构：数 组、链表、树、堆栈、字符串等，以及高频率出现的算法，如动态规划、俩指针、排列 组合、优先遍历等。本书的内容分为以下四个部分。 进军硅谷 程序员面试揭秘 VI 硅谷求职和面试：硅谷公司文化、技术移民、简历、面试和录用谈判。 常见数据结构：数组、链表、树和图、堆栈、字符串。 算法：动态规划、俩指针、优先遍历、哈希、排列组合。 杂项：系统设计、海量数据分析、面向对象设计、数学和位操作。 此外，附录还提供了数据结构和算法总结以及海量数据分析，以供读者快速查阅。 本书含有以下几个特点。 本书是市面上第一本介绍硅谷求职和技术移民美国的书。 精选出的面试题是硅谷各家热门公司的高频题，极其具有代表性。 总结了常见数据结构的对应算法，提炼出一套解题规律。对于类似题目，有着强 烈的借鉴意义。 本书提供了完整的可运行的源代码。 对于每道题，本书尽可能给出多种解法，对我们在日常工作中遇到问题时有一定 启发性。 虽然本书大部分的代码是用Java 编写，但很容易转化为C++/.NET 代码，因此，本 书也适合C++/.NET 程序员阅读。 由于本人水平有限，书中的题目并不能完全代表当前热门公司的编程面试的各个方 面，虽然经过多轮审核，不少解法依然可能有漏洞或者错误，希望广大读者能给予指正。 我已经搭建了一个关于程序员出国工作的网站“i 码工”（http://www.imagong.com）和读 者交流。 在本书的写作过程中，我得到了很多朋友、同事的帮忙，包括汪纯子、周泽勇、俞 明辉、吴盛萱、杨超、尹杭锋和于东东等。感谢他们帮忙校对文字、审核代码。同时， 感谢电子工业出版社的工作人员，尤其是符隆美的帮助。感谢她从大到全书的架构，小 到文字的推敲，都给予了我极大的帮助，从而使本书的质量有了极大的提升。最后，我要衷心地感谢我的妻子徐淼。感谢她在过去几年中对我的理解和支持，为 我营造了一个温馨而浪漫的家，让我能够心无旁骛地写书。谨以此书献给她以及我们的 女儿Ella。 陈东锋 2013 年10 月于上海张江

目录 第一部分 硅谷求职 第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 Epic12 1.3 技术移民 13 1.3.1 签证和绿卡 14 1.3.2 税率和生活 16 第2 章 求职准备 19 2.1 职位选择 21 目录 IX 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 进军硅谷 程序员面试揭秘 X 面试题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 目录 XI 面试题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 进军硅谷 程序员面试揭秘 XII 第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 目录 XIII 面试题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 进军硅谷 程序员面试揭秘 XIV 第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 目录 XV 第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 进军硅谷 程序员面试揭秘 XVI 面试题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