第1章介绍面试的流程。通常整个面试过程可以分为电话面试、共享桌面远程面试和现场面试3个阶段,每一轮面试又可以分为行为面试、技术面试和应聘者提问3个环节。本章详细讨论了面试中每一环节需要注意的问题。其中第1.3.2节深入讨论了技术面试中的5个要素,是全书的大纲,接下来的第2~6章逐一讨论每个要点。
第2章梳理应聘者接受技术面试时需要用到的基础知识。本章从编程语言、数据结构及算法三方面总结了程序员面试的知识点。
第3章讨论应聘者在面试时写出高质量代码的3个要点。通常面试官除了期待应聘者写出的代码能够完成基本的功能之外,还能应对特殊情况并对非法输入进行合理的处理。读完这一章,读者将学会如何从规范性、完整性和鲁棒性3个方面提高代码的质量。
第4章总结在编程面试中解决难题的常用思路。如果在面试过程中遇到复杂的难题,应聘者最好在写代码之前形成清晰的思路。读者在读完这一章之后将学会如何用画图、举例和分解复杂问题3种思路来解决问题。
第5章介绍如何优化代码的时间效率和空间效率。如果一个问题有多种解法,面试官总是期待应聘者能找到最优的解法。读完这一章,读者将学会优化时间效率及空间换时间的常用算法。
第6章总结面试中的各项能力。面试官在面试过程中会一直关注应聘者的学习能力和沟通能力。除此之外,有些面试官还喜欢考查应聘者的知识迁移能力、抽象建模能力和发散思维能力。读完这一章,读者将学会如何培养和运用这些能力。
第7章是两个面试的案例。在这两个案例中,我们将看到应聘者在面试过程中的哪些举动是不好的行为,而哪些表现又是面试官所期待的行为。衷心地希望应聘者能在面试时少犯甚至不犯错误,完美地表现出自己的综合素质,最终拿到心仪的Offer。
本书特色
正如前面提到的那样,本书的原型是我过去4年多陆陆续续发表的几十篇博客,但这本书也不仅仅是这些博客的总和,它在博客的基础上添加了如下内容。
本书试图以面试官的视角来剖析面试题。本书前6章的第一节都是“面试官谈面试”,收录了分布在不同IT企业(或者IT部门)的面试官们对代码质量、应聘者如何形成及表达解题思路等方面的理解。在本书中穿插着几十条“面试小提示”,是我作为面试官给应聘者在面试方法、技巧方面的建议。在第7章的案例中,“面试官心理”揭示了面试官在听到应聘者不同回答时的心理活动。应聘者如果能了解面试官的心理活动,无疑能在面试时更好地表现自己。
本书总结了解决面试难题的常用方法,而不仅仅只是解决一道道零散的题目。在仔细分析、解决了几十道典型的面试题之后,我发现其实是有一些通用的方法可以在面试的时候帮助我们解题的。举个例子,如果面试的时候遇到的题目很难,我们可以试图把一个大的复杂的问题分解成若干个小的简单的子问题,然后递归地去解决这些子问题。再比如,我们可以用数组实现一个简单的哈希表解决一系列与字符串相关的面试题。在详细分析了一道面试题之后,很多章节都会在“相关题目”中列举出同类型的面试题,并在“举一反三”中总结解决这一类型题目的方法和要点。
本书收集的面试题是都是各大公司的编程面试题,极具实战意义。包括谷歌、微软在内的知名IT企业在招聘的时候,都非常重视应聘者的'编程能力,编程技术面试也是整个面试流程中最为重要的一个环节。本书选取的题目都是被各大公司面试官反复采用的编程题。如果读者一开始觉得书中的有些题目比较难,那也正常,没有必要感到气馁,因为像谷歌、微软这样的大企业的面试本身就不简单。读者逐步掌握了书中总结的解题方法之后,编程能力和分析复杂问题的能力将会得到很大的提升,再去大公司面试将会轻松很多。
本书附带提供了50道编程题的完整的源代码,其中包含了每道题的测试用例。很多面试官在应聘者写完程序之后,都会要求应聘者自己想一些测试用例来测试自己的代码,一些没有实际项目开发经验的应聘者不知道如何做单元测试。相信读者朋友在读完这本书之后就会知道如何从基本功能测试、边界值测试、性能测试等方面去设计测试用例,从而提高编写高质量代码的能力。
目录
第1章面试的流程1
1.1面试官谈面试1
1.2面试的三种形式2
1.2.1电话面试2
1.2.2共享桌面远程面试3
1.2.3现场面试4
1.3面试的三个环节5
1.3.1行为面试环节5
应聘者的项目经验6
应聘者掌握的技能7
回答“为什么跳槽”8
1.3.2技术面试环节10
扎实的基础知识10
高质量的代码11
清晰的思路14
优化效率的能力15
优秀的综合能力16
1.3.3应聘者提问环节17
1.4本章小结18
第2章面试需要的基础知识20
2.1面试官谈基础知识20
2.2编程语言22
2.2.1 C++ 22
面试题1:赋值运算符函数24
经典的解法,适用于初级程序员25
考虑异常安全性的解法,高级程序员必备26
2.2.2 C# 27
面试题2:实现Singleton模式31
不好的解法一:只适用于单线程31
不好的解法二:可用于多线程但效率不高32
可行的解法:同步锁前后两次判断33
推荐的解法一:利用静态构造函数34
推荐的解法二:按需创建实例34
解法比较35
2.3数据结构36
2.3.1数组36
面试题3:二维数组中的查找38
2.3.2字符串42
面试题4:替换空格44
O(n2)的解法,不足以拿到Offer 45
O(n)的解法,搞定Offer就靠它46
2.3.3链表49
面试题5:从尾到头打印链表51
2.3.4树53
面试题6:重建二叉树55
2.3.5栈和队列58
面试题7:用两个栈实现队列59
2.4算法和数据操作62
2.4.1查找和排序63
面试题8:旋转数组的最小数字66
2.4.2递归和循环71
面试题9:斐波那契数列73
效率很低的解法,面试官不会喜欢73
面试官期待的实用解法74
O(logn)但不够实用的解法74
解法比较75
2.4.3位运算77
面试题10:二进制中1的个数78
可能引起死循环的解法79
常规解法79
能给面试官带来惊喜的解法80
2.5本章小结82
第3章高质量的代码84
3.1面试官谈代码质量84
3.2代码的规范性86
3.3代码的完整性87
从3方面确保代码的完整性87
3种错误处理的方法88
面试题11:数值的整数次方90
自以为题目简单的解法90
全面但不够高效的解法,离Offer已经很近了90
全面又高效的解法,确保能拿到Offer 92
面试题12:打印1到最大的n位数94
跳进面试官陷阱94
在字符串上模拟数字加法94
把问题转换成数字排列97
面试题13:在O(1)时间删除链表结点99
面试题14:调整数组顺序使奇数位于偶数前面102
只完成基本功能的解法,仅适用于初级程序员102
考虑可扩展性的解法,能秒杀Offer 104
3.4代码的鲁棒性106
面试题15:链表中倒数第k个结点107
面试题16:反转链表112
面试题17:合并两个排序的链表114
面试题18:树的子结构117
3.5本章小结121
第4章解决面试题的思路123
4.1面试官谈面试思路123
面试题19:二叉树的镜像125
4.2画图让抽象问题形象化125
面试题20:顺时针打印矩阵127
4.3举例让抽象问题具体化131
面试题21:包含min函数的栈132
面试题22:栈的压入、弹出序列134
面试题23:从上往下打印二叉树137
面试题24:二叉搜索树的后序遍历序列140
面试题25:二叉树中和为某一值的路径143
4.4分解让复杂问题简单化146
面试题26:复杂链表的复制147
面试题27:二叉搜索树与双向链表151
面试题28:字符串的排列154
4.5本章小结158
第5章优化时间和空间效率160
5.1面试官谈效率160
5.2时间效率162
面试题29:数组中出现次数超过一半的数字163
基于Partition函数的O(n)算法163
利用数组特点的O(n)算法165
解法比较166
面试题30:最小的k个数167
O(n)的算法,只当可以修改输入数组时可用167
O(nlogk)的算法,适合处理海量数据168
解法比较169
面试题31:连续子数组的最大和171
举例分析数组的规律171
应用动态规划法173
面试题32:从1到n整数中1出现的次数174
不考虑效率的解法,想拿Offer有点难174
明显提高效率的解法,让面试官耳目一新175
面试题33:把数组排成最小的数177
5.3时间效率与空间效率的平衡181
面试题34:丑数182
逐个判断整数是不是丑数的解法182
创建数组保存已经找到的丑数的解法183
面试题35:第一个只出现一次的字符186
面试题36:数组中的逆序对189
面试题37:两个链表的第一个公共结点193
5.4本章小结196
第6章面试中的各项能力198
6.1面试官谈能力198
6.2沟通能力和学习能力200
沟通能力200
学习能力200
善于学习、沟通的人也善于提问201
6.3知识迁移能力203
面试题38:数字在排序数组中出现的次数204
面试题39:二叉树的深度207
重复遍历结点的解法,不足以打动面试官209
只遍历结点一次的解法,正是面试官喜欢的209
面试题40:数组中只出现一次的数字211
面试题41:和为s的两个数字VS和为s的连续正数序列214
面试题42:翻转单词顺序VS左旋转字符串218
6.4抽象建模能力222
面试题43:n个骰子的点数223
基于递归求骰子点数,时间效率不够高223
基于循环求骰子点数,时间性