程序员面试手册：概念、编程问题及面试题
精选微软、谷歌和Facebook等世界知名IT公司面试和竞赛中涉及的编程题目
全面涵盖编程基础、架构设计、数据结构及算法等重要主题
针对各类竞赛和面试中的每个难点和考点提供了大量习题和详细解答
全面涵盖编程基础、架构设计、数据结构及算法等重要主题
针对各类竞赛和面试中的每个难点和考点提供了大量习题和详细解答
基本信息
- 原书名：Coding Interview Questions
内容简介
目录
Contents 目 录
译者序
前 言
致 谢
第1章 编程基础1
1.1 变量1
1.2 数据类型1
1.3 数据结构2
1.4 抽象数据类型3
1.5 内存与变量3
1.6 指针4
1.6.1 指针的声明4
1.6.2 指针的使用5
1.6.3 指针的操纵6
1.6.4 数组与指针7
1.6.5 动态内存分配7
1.6.6 函数指针7
1.7 参数传递的方式8
1.7.1 实际参数与形式参数8
1.7.2 参数传递的语义8
译者序
前 言
致 谢
第1章 编程基础1
1.1 变量1
1.2 数据类型1
1.3 数据结构2
1.4 抽象数据类型3
1.5 内存与变量3
1.6 指针4
1.6.1 指针的声明4
1.6.2 指针的使用5
1.6.3 指针的操纵6
1.6.4 数组与指针7
1.6.5 动态内存分配7
1.6.6 函数指针7
1.7 参数传递的方式8
1.7.1 实际参数与形式参数8
1.7.2 参数传递的语义8
译者序
面试与技术考试的成绩受很多因素影响，其中关键的一项因素就是技术水平。这些知识虽然无法完全通过书本获得，但是好的参考书可以把它们有条理地呈现出来，令人尽快发现自己的不足，从而更加明确地去补习某些方面的知识，这有利于提升面试和考试的成绩，而且对实际工作也有所帮助。
Karumanchi先生的这本书就是一本题目丰富、思路清晰而且解法多样的参考书。
书中的题目涵盖了编程基础、架构设计、网络技术、数据库技术、数据结构及算法等主要知识，而且还涉及了趣味谜题以及非技术的问题。其中数据结构与算法占据较大篇幅，因为这是面试与考试经常涉及的内容，而且能反映开发者的思考能力与技术水平。本书的每一章后面几乎都有数十个问题，多看一些这样的题目，在面对面试提问的时候，就能够更加从容地应对。
与范围和数量相比，题目的质量同样比较高。有些题目能够指出容易被忽视或误解的知识，还有一些题目则与实际的应用有关，例如模拟图书馆的借书系统，以及模拟商场的电梯系统等。这些题目往往不是单独提出来的，而是与其他题目有所联系，解决这些相似但又有微妙区别的题目能够帮助锻炼思维能力。
本书的讲解风格是较为明晰的。每一章在列出题目之前，都会先讲解题目所涉及的基础知识，使读者能够更加顺畅地切入题目本身。在解答部分，作者会用通俗易懂的语言把解题思路简洁地描述出来。这些思路不仅可以用来解决当前问题，而且还对解决其他题目有所启发。有时只要稍作变换，就可以用来应对同类问题。
把思路讲清楚之后，作者会给出解法，而且有时会从不同的思考方向给出多种解法。这可以令人看到同一道题的各种解法之间的区别，从而认清其利弊及适用场合，也可以令人在各种问题的解决办法之间体会相似之处，从而将多个知识点融会贯通。
开发者可以通读此书，也可以将其作为常备的参考手册，随时翻看，以求温故而知新。
翻译本书的过程中，我得到机械工业出版社华章公司诸位编辑与工作人员的帮助，在此深表谢意。
最后要说明的是，书中的范例代码只是为了解释思路而写的，具体运用时，可能需要酌情调整。译文对作者所用的某些分析方法、结论以及实现代码，只做了必要的技术处理，其余均保留原样。代码方面的问题，可访问原书网站www.careermonk.com，以联系作者。针对文本翻译方面的问题，可访问github.com/jeffreybaoshenlee/ciq-errata/issues留言，或发邮件至eastarstormlee@gmail.com，给我以批评和指教。
爱飞翔
2017年9月
Karumanchi先生的这本书就是一本题目丰富、思路清晰而且解法多样的参考书。
书中的题目涵盖了编程基础、架构设计、网络技术、数据库技术、数据结构及算法等主要知识，而且还涉及了趣味谜题以及非技术的问题。其中数据结构与算法占据较大篇幅，因为这是面试与考试经常涉及的内容，而且能反映开发者的思考能力与技术水平。本书的每一章后面几乎都有数十个问题，多看一些这样的题目，在面对面试提问的时候，就能够更加从容地应对。
与范围和数量相比，题目的质量同样比较高。有些题目能够指出容易被忽视或误解的知识，还有一些题目则与实际的应用有关，例如模拟图书馆的借书系统，以及模拟商场的电梯系统等。这些题目往往不是单独提出来的，而是与其他题目有所联系，解决这些相似但又有微妙区别的题目能够帮助锻炼思维能力。
本书的讲解风格是较为明晰的。每一章在列出题目之前，都会先讲解题目所涉及的基础知识，使读者能够更加顺畅地切入题目本身。在解答部分，作者会用通俗易懂的语言把解题思路简洁地描述出来。这些思路不仅可以用来解决当前问题，而且还对解决其他题目有所启发。有时只要稍作变换，就可以用来应对同类问题。
把思路讲清楚之后，作者会给出解法，而且有时会从不同的思考方向给出多种解法。这可以令人看到同一道题的各种解法之间的区别，从而认清其利弊及适用场合，也可以令人在各种问题的解决办法之间体会相似之处，从而将多个知识点融会贯通。
开发者可以通读此书，也可以将其作为常备的参考手册，随时翻看，以求温故而知新。
翻译本书的过程中，我得到机械工业出版社华章公司诸位编辑与工作人员的帮助，在此深表谢意。
最后要说明的是，书中的范例代码只是为了解释思路而写的，具体运用时，可能需要酌情调整。译文对作者所用的某些分析方法、结论以及实现代码，只做了必要的技术处理，其余均保留原样。代码方面的问题，可访问原书网站www.careermonk.com，以联系作者。针对文本翻译方面的问题，可访问github.com/jeffreybaoshenlee/ciq-errata/issues留言，或发邮件至eastarstormlee@gmail.com，给我以批评和指教。
爱飞翔
2017年9月
前言
亲爱的读者：
请先别急着翻过这一页。我知道，有很多人是不看前言的，但是这次，强烈建议大家读一读接下来的几段话，因为这里面有一些和其他前言不同的地方。
本书的前提是，读者已经掌握了一些计算机科学的基本知识。它的主要目标并不是提供与数据结构和算法有关的定理及证明，而是以一种逐步完善的方式来告诉大家：我们可以使用那些复杂度各不相同的办法来解决同一个编程问题。也就是说，针对每一个编程问题，笔者都会按照复杂度递减的顺序来讲解各种解法。总的来说，本书中囊括了各种编程解决方案，可以用来有效地应对面试、考试及校园招聘。
求职者如果能够读完本书，并很好地理解其中的内容，那么笔者保证：你肯定能够反过来给面试官提出几个难题。这正是本书想要达成的效果。
本书对于攻读工程学位及工程硕士的学生也会很有帮助。书中的每一章都会把重心放在编程问题及对这些问题所做的分析上，而不会只谈理论。笔者会在每章的开头讲解阅读此章所需的基础理论知识，然后列出一组问题。全书大约有700道算法题，而且每道题都有解答。
本书的大多数章节都会专注于问题本身，并对这些问题做出分析，而不会过多地聚焦在理论上面。各章开头会给出该章所要求的基本理论，然后提出问题。
书中的许多问题都有不止一种解法，而且这些解法的复杂度也各不相同。我们首先会讲解一种蛮力解法（brute force solution），然后逐渐改进，以求找到该问题的最佳解法（best solution）。笔者尽量使大家能够理解每个算法所耗费的时间，以及它所占据的内存量。
你至少应该将本书通读一遍，以求对其中的全部话题都有所了解。然后可以根据自己的需要，直接跳到某一章，以参考其内容。尽管本书经过多次校对，但错误在所难免，本书勘误会更新在www.CareerMonk.com网站上。你可以定期查阅此网站，以了解最新的勘误、习题及解决方案。也欢迎你发送邮件到Info@CareerMonk.com，给笔者提出宝贵的建议。
祝万事顺心、阅读愉快！
—Narasimha Karumanchi
印度理工学院孟买校区技术硕士、CareerMonk.com创始人
请先别急着翻过这一页。我知道，有很多人是不看前言的，但是这次，强烈建议大家读一读接下来的几段话，因为这里面有一些和其他前言不同的地方。
本书的前提是，读者已经掌握了一些计算机科学的基本知识。它的主要目标并不是提供与数据结构和算法有关的定理及证明，而是以一种逐步完善的方式来告诉大家：我们可以使用那些复杂度各不相同的办法来解决同一个编程问题。也就是说，针对每一个编程问题，笔者都会按照复杂度递减的顺序来讲解各种解法。总的来说，本书中囊括了各种编程解决方案，可以用来有效地应对面试、考试及校园招聘。
求职者如果能够读完本书，并很好地理解其中的内容，那么笔者保证：你肯定能够反过来给面试官提出几个难题。这正是本书想要达成的效果。
本书对于攻读工程学位及工程硕士的学生也会很有帮助。书中的每一章都会把重心放在编程问题及对这些问题所做的分析上，而不会只谈理论。笔者会在每章的开头讲解阅读此章所需的基础理论知识，然后列出一组问题。全书大约有700道算法题，而且每道题都有解答。
本书的大多数章节都会专注于问题本身，并对这些问题做出分析，而不会过多地聚焦在理论上面。各章开头会给出该章所要求的基本理论，然后提出问题。
书中的许多问题都有不止一种解法，而且这些解法的复杂度也各不相同。我们首先会讲解一种蛮力解法（brute force solution），然后逐渐改进，以求找到该问题的最佳解法（best solution）。笔者尽量使大家能够理解每个算法所耗费的时间，以及它所占据的内存量。
你至少应该将本书通读一遍，以求对其中的全部话题都有所了解。然后可以根据自己的需要，直接跳到某一章，以参考其内容。尽管本书经过多次校对，但错误在所难免，本书勘误会更新在www.CareerMonk.com网站上。你可以定期查阅此网站，以了解最新的勘误、习题及解决方案。也欢迎你发送邮件到Info@CareerMonk.com，给笔者提出宝贵的建议。
祝万事顺心、阅读愉快！
—Narasimha Karumanchi
印度理工学院孟买校区技术硕士、CareerMonk.com创始人
书摘
《程序员面试手册：概念、编程问题及面试题》：
如果IP地址不是局域网中的地址，那么处在网关位置上的路由器就会收到由计算机所发出的ARP请求（刚才说过，ARP请求会广播给局域网中的每一台设备，这也包括路由器）。路由器会查询路由表，看看其中是否有一条通往目标网络的路由，若有，则将自身的MAC地址同复给广播ARP请求的那台计算机。
这种情形只会发生在计算机不清楚网络拓扑结构的情况下，而在大多数情况下，计算机其实都是知道子网掩码与默认网关的，因此，它本身就清楚：这份数据包不应该发给局域网中的设备。于是，计算机就使用默认网关的MAC地址（这个MAC地址或许已经存放在它的ARP表里了，如果没有，那么可以采用上面所描述的办法，来发送ARP请求），把该数据包封装为数据帧。等到默认网关（也就是路由器）接到数据帧之后，它会发现其中所写的MAC地址正是自己的MAC地址，因此可以断定，这一帧确实应该由自己来接收。路由器会把这个数据链路帧的封装解开，并把其中的数据部分发给上方的网络层。
……
如果IP地址不是局域网中的地址，那么处在网关位置上的路由器就会收到由计算机所发出的ARP请求（刚才说过，ARP请求会广播给局域网中的每一台设备，这也包括路由器）。路由器会查询路由表，看看其中是否有一条通往目标网络的路由，若有，则将自身的MAC地址同复给广播ARP请求的那台计算机。
这种情形只会发生在计算机不清楚网络拓扑结构的情况下，而在大多数情况下，计算机其实都是知道子网掩码与默认网关的，因此，它本身就清楚：这份数据包不应该发给局域网中的设备。于是，计算机就使用默认网关的MAC地址（这个MAC地址或许已经存放在它的ARP表里了，如果没有，那么可以采用上面所描述的办法，来发送ARP请求），把该数据包封装为数据帧。等到默认网关（也就是路由器）接到数据帧之后，它会发现其中所写的MAC地址正是自己的MAC地址，因此可以断定，这一帧确实应该由自己来接收。路由器会把这个数据链路帧的封装解开，并把其中的数据部分发给上方的网络层。
……
