程序员生存手册

本书融合作者近20年在顶级IT企业工作和招聘的经验，基于对大量真实面试题目的分析，梳理出IT行业程序员应该掌握的知识和应该具备的素质及能力。本书内容涉及数据结构与算法、数据库、程序设计、网络以及当前最受关注的大数据、软件定义一切等方面的知识和面试题目，有助于程序员提升自己的能力，顺利找到工作。

RickySun（孙宇熙）现任EMC中国研究院院长、卓越研发集团CTO、技术委员会主席，中国电子学会云计算专家委员会专家委员，哈尔滨工业大学计算机与软件学院客座教授。
在EMC集团主要负责大数据、软件定义的数据中心、云计算、超融合架构、高性能计算、高校科研合作等领域的研发、战略合作与创新工作。
具有在硅谷和国内十余年工作和创业的经验：既有在大型跨国公司（微软、Yahoo!）的工作经历，也有过成功的创业经历。在Web2.0、无线网络优化管理、混合云架构、大数据快数据基础架构、软件定义存储等领域有着多年的工作经验、专利及业界的影响力。近年专业著作有：《软件定义的数据中心——技术与实践》、《大数据——战略、技术、实践》等。

前 言
致 谢
第一篇 基 础 篇
第1章 数据结构 2
1.1 链表 2
1.2 数组 9
1.3 字符串 11
1.4 比特与字节 14
1.5 堆栈及其他 17
第2章 算法与优化 22
2.1 排序 22
2.2 算法复杂性 26
第3章 操作系统 29
3.1 文件系统 29
3.2 多线程 31
3.3 网络 33
3.4 编译与内核 40
第4章 面向对象 57
4.1 C++ 58
4.2 软件设计模式 79
4.3 STL 86
第二篇 工 程 篇
第5章 五花八门的语言 94
5.1 Perl 94
5.2 PHP 109
5.3 Java 118
第6章 数据库 138
6.1 基础知识 139
6.2 数据库设计与优化 148
第7章 网络 160
7.1 HTTP与Web Server 160
7.2 VPN 169
第8章 面试题集锦 172
第三篇 潮 流 篇
第9章 大数据 196
9.1 大数据基本概念 196
9.2 大数据流派 199
9.3 大数据实战 215
第10章 云计算 219
10.1 基本概念 219
10.2 云计算与大数据 229
10.3 软件定义网络 231
10.4 软件定义存储 236
10.5 软件定义的数据中心 242
第11章 Android开发 253
第四篇 软 技 能 篇
第12章 面试基础 276
12.1 何为软技能 276
12.2 怎样提高软技能 276
12.3 演讲与报告也是一种能力 278
第13章 过HR这一关 280
13.1 HR关心什么 280
13.2 HR的问题表 281
第14章 offer是起点而不是终点 282
14.1 如何拿到好的offer 282
14.2 程序员的职业生涯 283
14.3 程序员的英文修养 284
14.4 成为卓有成效的沟通者 284

前  言上个世纪末，硅谷的高科技产业（Hi-Tech Industry）发展得如火如荼，整个硅谷呈现出一派欣欣向荣的景象，每天都有新兴的公司涌现，各种各样的招聘活动风起云涌，每个创新型公司在人力资源投资上的重头戏无一例外都是程序员（在“码农”或“DevOps”这些新新人类的词汇诞生之前，我们还保留严格意义上的程序员这一荣誉称号吧）。 说到程序员招聘，它和其他所有职位最大的不同就是技术面试，“会写代码才是王道”在相当长的时间里都是程序员这个行当里颠扑不破的真理。整个招聘流程中对编程、代码调试、编译、优化、架构理解与设计等技术能力的考查贯穿始终，甚至从HR（或招聘经理）最初联系你时便已开始。记得当年在Santa Clara Convention Center（会议中心）参加一次硅谷招聘大会时，逛到一个展台前，被一美国大姐问道：“What抯 your favorite language？”（你最喜欢什么语言？）我没过脑子就回答道：“C、C++”。在以硅谷为背景的对话中，语言=编程语言，俨然是个约定俗成的事儿。 程序员面试中，除了有那么几个著名的公司喜欢对大学毕业生们提一些脑筋急转弯类的问题（比如：读完“Stanford大学”需要多久？答案：一秒足矣）以外，绝大多数还是相当简朴、实在的。面试的形式可能多种多样，包括电话约谈（phone screen）、面谈（这类最简单、最轻松）、笔试（过不了这关就甭想进入下一关）、上机（实战，这类面试虽然不多，但也是不得不防的）、做主题报告（这是相当学院派的做法，不过很多研究院、CTO性质的机构会常用）等。本书的内容基本上覆盖了以上列出的所有面试形式中常见的问题并提供了较为详尽的解答，值得指出的是很多问题答案并不唯一，特别是设计类的问题，几乎没有标准、统一的正确答案。面试所要检验或者观察的是你在遇到问题时的第一反应、思维逻辑、思考方法、解决问题的方式、偏好等，面试官将综合这些因素来评估你在未来的团队中的位置和融入的可能性。 本书的内容可以说是我和很多志趣相投的同事、朋友对过去十几年（甚至几十年）中的亲身经历与收集的大量面试考题的整理、分类、提纯再细化。从地域而言，跨越了从美国到中国的大大小小上百家公司；从内容上看，既涵盖了数据结构、算法、操作系统、网络等基础类知识的面试题，也兼顾了最近几年关注度最高的移动编程（如Android）、云计算与大数据等内容。与传统的教科书不同，本书的目的是通过真实面试题的Q&A分析，让读者重温在书本中可能漏掉的重点，换一个甚至多个角度去思考问题的解决之道。因为工业界的解决方案与学术界往往大相径庭，但有时却又一脉相承。 要想了解从学校过渡到工业界的跨度，不妨来看两个简单的例子。 例子1  在数据结构中，最美妙的大概就是递归算法的使用。使用递归的代码看起来非常简短（虽然逻辑解读上可能更复杂），而且应用的地方很多，比如著名的链表反转（reversing a link-list）。遥想当年大一的时候一群人在DEC-8终端机上奋笔疾书写出那些自以为惊世骇俗的递归程序时，没人思考过递归会占用更多的内存（context saving），其效率也相对更差（调用前的内存准备、占用和调用后的内存释放），在面对长链表的情况下堆栈溢出也是潜在问题。在业界的真实应用中，单纯的递归几乎是不存在的，取而代之的是循环（不占用额外的存储，堆栈溢出的危险有效降低，等等）或递归嵌套循环（并且时刻监视内存的使用及是否有内存泄露等风险）。 例子2  再来看一个更接地气的问题。有一个大型的无线网络，其中几千台无线热点部署在城市的热点地区。管理员发现其中80%的同一型号的AP会不定期出现死机的现象，一旦发生这样的现象，远程无法访问，也无法自动重启，只能人工重新在本地断电重启。由于所有的AP均为企业级，有日志定期上传到管理服务器，因此分析得出此类AP会在频繁使用的24～48小时内出现上述死机现象。这个问题极度困扰网管部门，如何解决？除了统一升级固件，还有其他办法吗？我们知道，提供服务的网络设备（如无线AP）通常会提供远程访问接口，常见的有SNMP、Telnet、TFTP，高级的有SSH（更像一台*nix服务器了）。TFTP有的会被用来上传固件；SNMP多数只提供读，支持写的比较少，这一批AP也不支持SNMP写；最后就只剩下Telnet接口了。传统意义上远程Telnet登录并执行reboot操作即可，现在的问题是如何自动登录几千台AP？经过上面的分析，这个问题已经简化为：写一个UserAgent来自动Telnet登录，把它放到一个大的循环当中访问几千台AP，而自动登录的时间选择在凌晨3点到4点，因为几乎没有客户会在这个时间段登录。再完善一点的解决方案是先通过SNMP或Telnet判断是否有活跃链接用户，等待其下线再重启，这有点像Apache Web服务器的平滑重启（graceful restart）。再进一步考量的是发起大规模Telnet登录请求的主机用何种方法来完成工作：循环、多进程、多线程、非阻塞I/O（Non-blocking I/O），以及其他考虑因素，如异常处理等。 通过上面两个简单的例子，希望大家可以感受真实环境下我们在面对问题、分析问题并寻找解决之道时是如何因地制宜的。最简单的方法不一定是最好的，但能解决客户问题的方法一定是好的（good enough solution that makes sense）。 本书并不是一本超级严肃、充满条条框框的教科书，你可以把它看作一本面试参考书，也可以闲来翻翻作为了解IT发展史的课外书。本书的内容中虽然有绝大部分是纯技术的，但是也有软技能相关的章节。总之，一个优秀的技术人员不仅要有过硬的技术背景，也要有一定的软技能（待人接物）；要有常识，要能融入团队，这样你才能走得更远、变得更强。 不知道有没有人统计过一个程序员在其技术生涯中要学习、掌握多少种技能（语言、系统、环境与流程）。我个人感觉，摩尔（Moore）定律也适用于这个问题，平均每1.5年就会有一整套新的颠覆性技术出现，如果不想被淘汰，就不得不迎头赶上。对于热爱编程的你而言，本书覆盖了6种典型的计算机语言。鉴于篇幅所限，我并没有刻意搜集更多的编程语言，因为我相信触类旁通，掌握一门语言，熟悉它、灵活运用它，再去攻克另一门语言是一件很简单的事情（有时候甚至就是半个下午的事情）。以一个科班出身（CS专业）IT老兵的角度看，对于计算机语言的接触与掌握可经历如下阶段：C → C++/Java → Perl/PHP/SQL 或Android/iOS。C是基础，数据结构、操作系统、网络编程都是以C为范例讲解的；C++/Java是OO的两大代表性语言，C++更硬核（hardcore）一些，而Java这几十年经久不衰自然有它的过人之处；Perl是脚本语言中集大成者（PHP、Python、Ruby、JavaScript这些统统可以看作Perl的“小弟”兼衍生品。严格意义上说，Perl源自Shell Scripting，像sed、awk、sh、csh、bash等不一而足，但是集大成者当属Perl，由于篇幅及受众所限，本书没有为Shell编程单独开辟章节）；SQL是一门很人性化的语言，在大数据备受关注的今天，熟练掌握SQL绝对不会让你落伍；Android/iOS分别可以看作Java与C++的变种……总而言之，从C开始熟悉基本概念、夯实基础，会让你走得更远、更好！ 最近几年，随着云计算和大数据的风起云涌，很多问题已经不再是简单（或直接）的编码问题，而更侧重于系统的体系架构设计、逻辑分析、优劣选择或方案折中；同时随着移动互联网的飞速发展，新的编程语言不断涌现，本书也选取了一些具有代表性的Q&A与大家分享，希望对大家的工作与学习有所助益。 另外，需要说明的是，本书的每一个Q&A都可以独立成文，虽然前后的数个Q&A可能会有知识点上的关联性，但是从阅读、查询、恶补或是作为面试问题的角度上来看并不存在相互依赖性。书中一些重要的Q&A配有作者录制的讲解视频，读者可扫码进行观看。每章后还附有该章内容相关的基础知识的MOOC的二维码，需要的读者可扫码进入学习。 孙宇熙2015年9月致  谢从最早的Q&A收集整理到最终集结成书，时间跨度足足有十几年。最早的版本是笔者本人的日常英文笔记（都是在历次技术面试中凭记忆记录下来的经典问题），涵盖了100多道硅谷IT公司典型的程序员面试技术问题，后来尝试着分享给身边的三五好友，颇得好评。在实战中，这本小册子不断被验证，之后又有很多同事和朋友陆续补充了一些题目。一来二往，小册子变成了厚厚的大册子（超过500道问题，涉猎的技术领域、问题类型也更加广泛）。 在本书付梓之际，需要感谢的人很多。按照华人的传统，首先要感谢父母，感谢他们对我一如既往的关怀、支持与理解；其次要感谢我的家人，没有你们的理解与宽容，我不可能有大把的周末时光把自己关在书房中埋头码字（同时也有了合理的借口可以不参与周末家庭大扫除）。 感谢在过去多年内提供了很多Q&A来充实和丰富本书的朋友和同事们，包括：我的大学同学、PaloAlto Networks技术副总裁Wilson Xu，前Yahoo!的高级工程师Stephanie Xu，Facebook早期员工Eric Ji，我的大学同学、卡内基梅隆大学高材生张成，我的前微软同事周健博士、Neo Han Chen，我的前合伙人和老朋友、硅谷硬件孵化器创始人Hilbert Ming Guo，我的EMC同事、技术总监Michelle Lei女士，我在EMC研究院的大数据与云计算的同事和专家曹逾博士、李三平博士、董哲、郭晓燕、陈曦，还有那些曾经在面试中折磨过我也被我折磨过的人们，在此一并感谢。 特别需要感谢的还有机械工业出版社的朱劼女士和我的同事朱捷先生以及开课吧团队同仁，没有他们的积极策划与耐心帮助，本书不会成为现实。 孙宇熙2015年2月28日深夜于硅谷米深堂