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

随着越来越多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 月于上海张江

第一部分 硅谷求职 第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

陈东锋 __eol__曾是微软和IBM总部的软件研发工程师，目前在一家大型互联网公司从事广告、交易、架构等方面的研发和管理工作。__eol____eol__涂峰 __eol__2008年获得复旦大学计算机软件与理论专业硕士学位，现在硅谷某大数据创业公司担任系统架构师。在此之前，曾在百度商务搜索部商业知心广告业务担任高级软件工程师、EMC统一存储部和IBM系统技术部担任资深软件工程师，主要负责底层系统开发方向。