程序员面试金典(第6版)

第 1 章 面试流程 1 1.1  为什么  1 1.1.1  错过了优秀人才是可以的  2 1.1.2  解决问题的技能很宝贵  2 1.1.3  基础数据结构和算法知识很有用  2 1.1.4  白板让你专注于重要的事情  2 1.1.5  但这并不适用于每个人、每家公司、每种场合  3 1.2  面试问题的来源  3 1.3  一切都是相对的  3 1.4  常见问题  4 1.4.1  面试结束后没有立即收到回复，我是被拒了吗  4 1.4.2  被拒之后我还能重新申请吗  4 第  2 章 面试揭秘  5 2.1  微软面试  6 2.1.1  推荐项  6 2.1.2  独特之处  6 2.2  亚马逊面试  6 2.2.1  推荐项  7 2.2.2  独特之处  7 2.3  谷歌面试  7 2.3.1  推荐项  8 2.3.2  独特之处  8 2.4  苹果面试  8 2.4.1  推荐项  9 2.4.2  独特之处  9 2.5  Facebook面试  9 2.5.1  推荐项  9 2.5.2  独特之处  10 2.6  Palantir面试  10 2.6.1  推荐项  10 2.6.2  独特之处  10 第  3 章 特殊情况  11 3.1  有工作经验的求职者  11 3.2  测试人员和软件开发测试工程师  11 3.3  产品经理（项目经理）  12 3.4  开发主管与部门经理  13 3.5  创业公司  13 3.5.1  职位申请  14 3.5.2  签证与工作许可  14 3.5.3  简历筛选因素  14 3.5.4  面试流程  14 3.6  收购与“人才收购”  14 3.6.1  哪些创业公司需要进行并购面试，为什么  14 3.6.2  这些面试有多重要  15 3.6.3  哪些员工需要面试  15 3.6.4  如果面试表现不好会怎么样  15 3.6.5  很优秀和最差的员工或许会令你吃惊  16 3.6.6  被收购方的员工与一般求职者的标准一样吗  16 3.6.7  被收购员工对于收购、人才收购会如何反应  16 3.6.8  收购后的团队会经历什么  16 3.6.9  怎样为你的团队准备收购面试  16 3.7  面试官  17 3.7.1  不要问与本书接近相同的题目  17 3.7.2  问中等难题或者高难度题  17 3.7.3  使用多重障碍的题目  17 3.7.4  使用高难度题目，而不是艰深的基础知识  18 3.7.5  避免“吓人”的问题  18 3.7.6  提供正面鼓励  19 3.7.7  深究行为面试题  19 3.7.8  辅导求职者  19 3.7.9  如果求职者想保持安静，请满足  20 3.7.10  了解你的模式：完整性测试、质量测试、专业知识和代理知识  20 第  4 章 面试之前  22 4.1  积累相关经验  22 4.2  写好简历  23 4.2.1  简历篇幅长度适中  23 4.2.2  工作经历  23 4.2.3  项目经历  23 4.2.4  软件和编程语言  24 4.2.5  给母语为非英语的人及国际人士的建议  24 4.2.6  提防（潜在的）污名  24 4.3  准备流程图  25 第  5 章 行为面试题  28 5.1  面试准备清单  28 5.1.1  你有哪些缺点  28 5.1.2  你应该问面试官哪些问题  28 5.2  掌握项目所用的技术  29 5.3  如何应对  29 5.3.1  力求具体，切忌自大  29 5.3.2  省略细枝末节  30 5.3.3  多谈自己  30 5.3.4  回答条理清晰  30 5.3.5  行动是关键  31 5.3.6  故事的意义  31 5.4  自我介绍  32 5.4.1  结构  32 5.4.2  兴趣爱好  32 5.4.3  展示成功的点点滴滴  33 第  6 章 大Ο  34 6.1  打个比方  34 6.2  时间复杂度  34 6.2.1  大Ο、大θ和大Ω  35 6.2.2  很优、最坏和期望情况  35 6.3  空间复杂度  36 6.4  删除常量  36 6.5  丢弃不重要的项  37 6.6  多项式算法：加与乘  38 6.7  分摊时间  38 6.8  Log N运行时间  39 6.9  递归的运行时间  39 6.10  示例和习题  40 第  7 章 技术面试题  53 7.1  准备事项  53 7.2  推荐的基础知识  53 7.2.1  核心数据结构、算法及概念  53 7.2.2  2的幂表  54 7.3  解题步骤  54 7.4  优化和解题技巧 1：寻找BUD  58 7.4.1  瓶颈  59 7.4.2  无用功  59 7.4.3  重复性工作  60 7.5  优化和解题技巧 2：亲力亲为  61 7.6  优化和解题技巧 3：化繁为简  62 7.7  优化和解题技巧 4：由浅入深  62 7.8  优化和解题技巧 5：数据结构头脑风暴法  63 7.9  可想象的极限运行时间  63 7.10  处理错误答案  66 7.11  做过的面试题  66 7.12  面试的“完美”语言  67 7.12.1  流行度  67 7.12.2  语言可读性  67 7.12.3  潜在问题  67 7.12.4  冗长  67 7.12.5  易用性  68 7.13  好代码的标准  68 7.13.1  多多使用数据结构  68 7.13.2  适当代码复用  69 7.13.3  模块化  70 7.13.4  灵活性和通用性  70 7.13.5  错误检查  71 7.14  不要轻言放弃  71 第  8 章 录用通知及其他注意事项  72 8.1  如何处理录用与被拒的情况  72 8.1.1  回复期限与延长期限  72 8.1.2  如何拒绝录用通知  72 8.1.3  如何处理被拒  72 8.2  如何评估录用待遇  73 8.2.1  薪酬待遇的考量  73 8.2.2  职业发展  73 8.2.3  公司稳定性  73 8.2.4  幸福指数  74 8.3  录用谈判  74 8.4  入职须知  75 8.4.1  制定时间表  75 8.4.2  打造坚实的人际网络  75 8.4.3  向经理寻求帮助  75 8.4.4  保持面试状态  75 第  9 章 面试题目  76 9.1  数组与字符串  76 9.1.1  散列表  76 9.1.2  ArrayList与可变长度数组  77 9.1.3  StringBuilder  77 9.2  链表  79 9.2.1  创建链表  79 9.2.2  删除单向链表中的节点  80 9.2.3  “快行指针”技巧  80 9.2.4  递归问题  81 9.3  栈与队列  82 9.3.1  实现一个栈  82 9.3.2  实现一个队列  83 9.4  树与图  85 9.4.1  树的类型  85 9.4.2  二叉树的遍历  87 9.4.3  二叉堆（小顶堆与大顶堆）  88 9.4.4  单词查找树（前序树）  89 9.4.5  图  90 9.4.6  图的搜索  91 9.5  位操作  94 9.5.1  手工位操作  95 9.5.2  位操作原理与技巧  95 9.5.3  二进制补码与负数  95 9.5.4  算术右移与逻辑右移  96 9.5.5  常见位操作：获取与设置数位  97 9.6  数学与逻辑题  99 9.6.1  素数  99 9.6.2  概率  101 9.6.3  大声说出你的思路  102 9.6.4  总结规律和模式  102 9.6.5  略作变通  103 9.6.6  触类旁通  104 9.7  面向对象设计  105 9.7.1  如何解答  105 9.7.2  设计模式  106 9.8  递归与动态规划  108 9.8.1  解题思路  109 9.8.2  递归与迭代  109 9.8.3  动态规划及记忆法  109 9.9  系统设计与可扩展性  114 9.9.1  处理问题  114 9.9.2  循环渐进的设计  114 9.9.3  逐步构建的方法：循序渐进  116 9.9.4  关键概念  116 9.9.5  系统设计要考虑的因素  118 9.9.6  人无完人，系统亦然  119 9.9.7  实例演示  119 9.10  排序与查找  121 9.10.1  常见的排序算法  121 9.10.2  查找算法  124 9.11  测试  126 9.11.1  面试官想考查什么  126 9.11.2  测试现实生活中的事物  127 9.11.3  测试一套软件  127 9.11.4  测试一个函数  129 9.11.5  调试与故障排除  129 9.12  C和C++  131 9.12.1  类和集成  131 9.12.2  构造函数和析构函数  131 9.12.3  虚函数  132 9.12.4  虚析构函数  133 9.12.5  默认值  134 9.12.6  操作符重载  134 9.12.7  指针和引用  134 9.12.8  模板  135 9.13  Java  136 9.13.1  如何处理  137 9.13.2  重载与重写  137 9.13.3  集合框架  138 9.14  数据库  139 9.14.1  SQL语法及各类变体  139 9.14.2  规范化数据库和非规范化数据库  139 9.14.3  SQL语句  140 9.14.4  小型数据库设计  141 9.14.5  大型数据库设计  142 9.15  线程与锁  143 9.15.1  Java线程  143 9.15.2  同步和锁  145 9.15.3  死锁及死锁的预防  148 9.16  中等难题  149 9.17  高难度题  152 第  10 章 题目解法  156 10.1  数组与字符串  156 10.2  链表  170 10.3  栈与队列  186 10.4  树与图  197 10.5  位操作  229 10.6  数学与逻辑题  240 10.7  面向对象设计  254 10.8  递归与动态规划  286 10.9  系统设计与可扩展性  313 10.10  排序与查找  332 10.11  测试  350 10.12  C和C++  354 10.13  Java  363 10.14  数据库  370 10.15  线程与锁  375 10.16  中等难题  388 10.17  高难度题  450 第  11 章 进阶话题  539 11.1  实用数学  539 11.1.1  整数1至N的和  540 11.1.2  2的幂的和  540 11.1.3  对数的底  542 11.1.4  排列  541 11.1.5  组合  541 11.1.6  归纳证明  541 11.2  拓扑排序  542 11.3  Dijkstra算法  543 11.4  散列表冲突解决方案  545 11.4.1  使用链表连接数据  545 11.4.2  使用二叉搜索树连接数据  546 11.4.3  使用线性探测进行开放寻址  546 11.4.4  平方探测和双重散列  546 11.5  Rabin-Karp子串查找  546 11.6  AVL树  547 11.6.1  性质  547 11.6.2  插入操作  547 11.7  红黑树  548 11.7.1  性质  549 11.7.2  为什么这样的树是平衡的  549 11.7.3  插入操作  549 11.8  MapReduce  551 11.9  补充学习内容  553 附录  A 代码库  554 附录  B 提示  560