技术移民宝典_程序员海外求职锦囊.pdf

CMYCMMYCYCMYK技术移民宝典2fy.pdf 1 2016/3/15 14:39:07 内 容 简 介 本书介绍了如何在硅谷求职，以及剖析了具有代表性的 43 道热门硅谷公司的面试题，从面试技巧、基础知识、解题思路和效率优化等方面总结面试和解题规律。全书分为四部分共 15 章，包含出国工作途径、IT 求职准备、实战访谈，以及常见数据结构、算法、大数据、系统设计等方面的题目和解题思路，并提炼出解题的 5 个步骤：复述/提问、举例、观察、编码和测试。本书精选出的面试题是硅谷热门公司的高频题，可以用来作为面试前的练习。对于每道题，本书尽可能给出多种解法，对于解决日常工作中遇到的问题也有一定启发性。本书适合正在应聘程序员相关职位的就业人员阅读和参考，特别是打算寻求美国 IT 公司职位并想通过技术移民实现美国梦的程序员。未经许可，不得以任何方式复制或抄袭本书之部分或全部内容。版权所有，侵权必究。图书在版编目（CIP）数据 技术移民宝典：程序员海外求职锦囊/陈东锋，涂峰著.北京：电子工业出版社，2016.4 ISBN 978-7-121-28195-2.技.陈 涂.电子计算机工程技术人员职业选择基本知识美国.TP3 中国版本图书馆 CIP 数据核字(2016)第 033614 号 策划编辑：符隆美 责任编辑：徐津平 印 刷：三河市华成印务有限公司 装 订：三河市华成印务有限公司 出版发行：电子工业出版社 北京市海淀区万寿路 173 信箱 邮编 100036 开 本：7201000 1/16 印张：13 字数：250 千字 版 次：2014 年 3 月第 1 版 2016 年 4 月第 2 版 印 次：2016 年 4 月第 1 次印刷 印 数：4000 册 定价：45.00 元 凡所购买电子工业出版社图书有缺损问题，请向购买书店调换。若书店售缺，请与本社发行部联系，联系及邮购电话：（010）88254888。质量投诉请发邮件至 ，盗版侵权举报请发邮件至 。服务热线：（010）88258888。前 言 随着越来越多 IT 工程师寻找国外工作机会，介绍和总结国外热门 IT 公司面试过程及面试内容的需求变得越来越迫切。美国最新移民改革 CIR 方案更倾向于技术移民，这将使得今后会有更多国内程序员去美国工作。笔者亲身参与了国内和美国一些热门 IT 公司的面试，同时也作为面试官面试过不少人，熟知海内外 IT 公司招聘流程和面试方式。通常来说，去美国 IT 公司工作有三种途径。直接申请美国公司职位，拿 H1B 签证工作。不少热门 IT 公司直接在国内招人，比如 Facebook、Amazon、Microsoft、Google 等。越来越多的程序员选择这条路，一方面是因为美国签证的条件放宽了，另一方面是因为硅谷公司面试并没有比国内公司难多少。在国内的跨国公司工作一年后，内部转组到美国的分部，使用 L1 签证。例如，从微软中国转至微软西雅图总部工作。申请攻读美国学校的计算机科学硕士或博士学位，毕业后再找工作，即由 F1 签证转为 H1B 签证。这三种途径都需要成功通过公司的技术面试。热门 IT 企业的面试方式大技术移民宝典 程序员海外求职锦囊 IV 致相同：1 或 2 轮电话面试，通过之后，又有 4 或 5 轮的现场面谈。其中 80%的面试是技术面试，每轮技术面试大约 45 分钟，扣除双方自我介绍和提问时间，花在技术面试的时间大约为 30 分钟。由于技术面试时间的限制，面试的题目一般不会太难，比大学生编程比赛（ACM）的题目简单很多，但是，面试者需要具备一些编程面试技巧，并对算法、数据结构熟练掌握才能在限定时间内完成。这对要求在白板上写程序和无 Bug（Bug free）的公司来说尤其重要，比如 Facebook。在编程面试过程中，光有解法却写不出来代码是行不通的，这只会让面试官觉得你夸夸其谈，不会实际编程。在编程面试里，切记“让代码说话”这条准则。在本书面试题相关的章节中，笔者贴出了面试题的全部代码，是为了更多时候让代码来说话。针对每道面试题，我们通常会有如下步骤。复述/提问：用自己的话复述面试官的题目，以免偏题。面试官给出的面试题并非一开始就很明确，需要多次问答来确定题意、边界条件、时间和数据结构限制等。举例：可以与提问同步进行，主要用来确认输入和输出结果。观察：通过举例来总结规律，思考可能使用到的结构和算法，然后设计一种你认为最优的算法。编码：和面试官沟通你的算法之后，开始在白板编码。测试：使用个别例子，把你的代码测试一遍。在以上 5 个步骤里，看时间是否充裕，有些步骤可以省略。比如，如果面试官已经把问题说得很清楚了，那么复述可以省略。在本书当中，笔者也会按照这 5 个步骤的解题技巧来阐述面试题的解题方案。笔者根据自身作为面试官的多年经历，并收集了网上众多的热门 IT 公司面试题目，精选了 43 道题来代表当前热门和高频的面试题。本书内容覆盖了基础的数据结构：数组、链表、树、堆栈、字符串等，以及高频率出现的算法，前 言 V如动态规划、俩指针、排列组合、优先遍历等。此外，还覆盖了系统设计解题思路和案例分析。涂峰加入了再版的写作，以自身“肉身翻墙”的经历为本书丰富了求职准备、实战访谈、系统设计等章节。本书的内容分为以下四个部分。硅谷求职：硅谷公司文化、技术移民、简历、面试、录用谈判和职业发展。实战访谈：先行者所传授的出国途径、面试技巧、硅谷企业文化、职业规划。算法面试：动态规划、俩指针、优先遍历、哈希、排列组合。系统设计：实战技巧、案例分析、阅读推荐。此外，附录还提供了数据结构和算法总结及海量数据分析，以供读者快速查阅。本书有以下几个特点。本书是市面上第一本介绍硅谷求职和技术移民美国的书。本书也是第一本对已实现技术移民美国的先行者进行访谈的书。精选出的面试题是硅谷各家热门公司的高频题，极其具有代表性。完整介绍了系统设计题的实战技巧，对应聘高级职位者很有借鉴意义。总结了常见数据结构的对应算法，提炼出一套解题规律。对于类似题目，有很强的借鉴意义。本书提供了完整的可运行的源代码。对于每道题，本书尽可能给出多种解法，对解决我们在日常工作中遇到的问题有一定启发性。虽然本书大部分的代码是用Java编写的，但很容易转化为C+/.NET代码，因此，本书也适合 C+/.NET 程序员阅读。由于本人水平有限，书中的题目并不能完全代表当前热门公司的编程面试技术移民宝典 程序员海外求职锦囊 VI 的各个方面，虽然经过多轮审核，不少解法依然可能有漏洞或者错误，希望广大读者能给予指正。在本书的写作过程中，我得到了很多朋友、同事的帮忙，包括汪纯子、周泽勇、俞明辉、吴盛萱、杨超、尹杭锋和于东东等。感谢他们帮忙校对文字、审核代码。同时，感谢电子工业出版社的工作人员，尤其是符隆美大到全书的架构，小到文字的推敲，她都给予了我极大的帮助，从而使本书的质量有了极大的提升。最后，我要衷心地感谢我的妻子 Emily。感谢她在过去几年中对我的理解和支持，为我营造了一个温馨而浪漫的家，让我能够心无旁骛地写书。谨以此书献给她以及我们的女儿 Ella。陈东锋 2015 年 11 月于上海张江 目 录 VII 目 录 第一部分 硅谷求职 第 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 技术移民宝典 程序员海外求职锦囊 VIII 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 目 录 IX创业者徐淼华.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 技术移民宝典 程序员海外求职锦囊 X 第 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 目 录 XI面试题 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 第一部分 硅谷求职 技术移民宝典 程序员海外求职锦囊 2 第 1 章 硅谷公司 3 第1章 硅谷公司 硅谷是世界 IT 中心，汇聚了顶级的电子、芯片、软件、互联网等 IT 公司。本章将介绍硅谷的地理位置和发展历程，简述六家具有代表性的硅谷公司的文化和特点，最后描述国内的软件工程师寻找美国工作的三种途径及技术移民美国的方法。1.1 硅谷简介 硅谷（Silicon Valley）指美国加利福尼亚州的旧金山以南，沿着 101 公路从门罗公园、帕拉托、山景城、太阳谷到硅