编程之美--微软技术面试心得

    书籍
    计算机书籍
本书收集了约60道算法和程序设计题目，这些题目大部分在近年的笔试，面试中出现过，或者是被微软员工热烈讨论过。作者试图从书中各种有趣的问题出发，引导读者发现问题，分析问题，解决问题，寻找更优的解法。本书的内容分为下面几个部分：

游戏之乐：从游戏和其他有趣问题出发，化繁为简，分析总结。

数字之魅：编程的过程实际上就是和数字及字符打交道的过程。这一部分收集了一些好玩的对数字进行处理的题目。

结构之法：汇集了常见的对字符串、链表、队列，以及树等进行操作的题目。

数学之趣：列举了一些不需要写具体程序的数学问题，锻炼读者的抽象思维能力。

书中绝大部分题目都提供了详细的解说。 每道题目后面还有一至两道扩展问题，供读者进一步钻研。

书中还讲述了面试的各种小故事，告诉读者微软需要什么样的技术人才，重视什么样的能力，如何甄别人才。回答读者关于IT业面试，招聘，职业发展的疑问。这本书的很多题目会出现在IT 行业的各种笔试，面试中。但本书更深层的意义在于引导读者思考，和读者共享思考之乐，编程之美。

邹欣，现任微软亚洲研究院技术创新组研发主管。他从1996年起在微软Outlook 产品团队从事开发工作, 2003 年到2005 年，在微软Visual Studio Team System产品团队负责软件质量管理工具的开发。加入微软前，邹欣从事过商用Unix系统、GPS/GIS软件开发以及软件测试工作。2007年出版了《移山之道——VSTS软件开发指南》一书。他1991年获北京大学计算机软件专业学士学位。1996 年获美国Wayne State University(韦恩州立大学)计算机软件专业硕士学位。

第1章 游戏之乐——游戏中碰到的题目
　1.1 让CPU占用率曲线听你指挥
　1.2 中国象棋将帅问题
　1.3 一摞烙饼的排序
　1.4 买书问题
　1.5 快速找出故障机器
　1.6 饮料供货
　1.7 光影切割问题
　1.8 小飞的电梯调度算法
　1.9 高效率地安排见面会
　1.10 双线程高效下载
　1.11 NIM（1）一排石头的游戏
　1.12 NIM（2）“拈”游戏分析
　1.13 NIM（3）两堆石头的游戏
　1.14 连连看游戏设计
　1.15 构造数独
　1.16 点游戏
　1.17 俄罗斯方块游戏
　1.18 挖雷游戏
第2章 数字之魅——数字中的技巧

　　这是一本让人着迷的书！
　　从我得到样书的那一刻起，在每天的闲暇时间阅读和思索这本书中的题目就成了我的一个新习惯。虽然网络上早就流传着不少微软面试题，坊间也不乏一些程序员面试类的图书，但是像这样集中展示高水平编程面试题目，并且以启发性方式对这些题目予以权威解答的图书，这还是第一本。对于那些正在准备面试的同学来说，这本书毫无疑问是宝贵的学习资料。而在我看来，即使是对于已经工作的程序员来说，这本书也是非常值得用心阅读的。
　　实话实说，对于算法和数学类谜题的意义和价值，在程序员社群里长期以来就存在很大的争议。CSDN上每隔一段时间就会有人讨论“算法真的重要吗”或者“数学真的重要吗”这样的问题。很多人对此都持质疑甚至是否定态度，他们认为，对于企业来说，是软件产品而不是具体的程序创造了价值，而创造成功的软件产品是一个庞大而复杂的系统工程，优质的算法和程序在其中的作用是有限的，相反，对平台和系统的理解、对领域知识和规则的掌握、软件质量的控制、产品设计、架构的选择和设计、平台和工具选型，以至于团队管理和有效沟通，对于软件工程师来说是更为重要的技能和素质。相比之下，算法和数学只要基础扎实就可以了，在实践当中反而不如上面那些要素显得重要，更没有必要在类似智力测试般的面试谜题和奇技淫巧上花费太多心思了。
　　这样的看法，当然有很有价值的方面。当代的软件工程师，确实需要建立更全面的知识技能体系和系统思维，但是以此来否定和贬低算法和数学基本功的重要性，否定面试谜题的意义和价值，则又属于只见树木不见森林。事实上，这些谜题考察和锻炼的，并不是算法和数学的“奇技淫巧”，而是扎实、严密和具有创造性的思考能力，面对问题有条不紊的分析能力，和不断深入、刨根问底的精神。毫无疑问，这些素质，都是软件工程师身上最宝贵的东西。
　　本书就是对这一问题的有力证明。请翻开这本书，随便挑选几个问题，认真思考，尝试解答，再看看作者的思路，在其启发下更进一步思考，尝试给出更多更好的解决方案，甚至更进一步，提出书中都没有提出的问题，把问题想透，把程序实现出来，验证自己的想法。毫无疑问这样的阅读方法是相当吃功夫的，但通过这样的方式，不但能够最大程度地获得本书的价值，也能够实实在在提高读者的基本功、思考力和创造力。毫无疑问，这些能力的意义要远比任何具体知识和技能的获得都更重要。对系统与平台的理解也好，对领域知识的掌握也好，产品的设计、架构的选择也好，所有这些算法之外的技能，不都需要强悍的思考能力的支撑才能获得吗？事实上，在这个知识开放共享的时代，头脑和思维才是唯一核心的竞争力，从这个意义上讲，这本书是直接面向核心竞争力发展的，其意义何其大也！
　　这本书另一个必须要提的意义，就是它的“美”。真正的程序员都领略过程序之美，那些简洁有力的代码，精巧严密的构思，高效直接的解决方案，美得令人窒息。可惜，在日益工业化和利益驱动的IT中，这种美已经是越来越少见的东西。但我想每一个真正热爱编程的人，都渴望欣赏这种美，渴望在思考过程中一次次“Aha！”式的愉悦。这本书就能够最有效地满足我们欣赏编程之美的渴望，题目的美，思考过程的美，解答的美，延伸思考的美，这种美的感觉，对于真正的程序员来说，本身就是一种精神享受。
　　虽然这本书表面上是指导面试的，但是依我来看，已经工作的职业程序员更有必要好好读读这本书。毕竟世界很大，不是每个人都要去微软或者谷歌，而这本书的意义绝不仅仅在面试，更重要的是在编程之美，思考之美。
　　潘爱民倾力推荐《编程之美——微软技术面试心得》
　　我很早知道邹欣计划要写这样一本书，也能够预计到这本书定会广受欢迎，因为它符合当前大量求职人员的需求，毕竟于他们而言，谁不想知道微软亚洲研究院在招人时候问些什么问题呢。另一方面，把考察软件技术人员专业知识和相应技能的各种手段加以归纳和整理，这本身也是对业界的贡献，所以，我相信，一旦这本书如计划般完成，其对业界的影响将是深远的。
　　在我的面试经历中，通过一些具体的程序问题来考察人，往往是最有效的，即使是一些人所皆知的问题，也往往能够挖掘出被面试者的亮点或弱点，原因在于，每个问题都有不同层次的解答之辞，面试者总是可以刨根究底地问下去。我们在看一段程序的时候，思路固然重要，细节也是不可忽视的，比如整数是否越界、指针是否为空，等等。这些细节可以用于考察基本功，毫无疑问，基本功不扎实的人通常很难得到面试者的青睐。
　　当拿到这本书的样稿时，我迫不及待地放下手头工作，阅读起来。有些题目的内容会引起强烈的共鸣，尤其是那些自己非常熟悉并且又深知解答的题目；也有一些题目让我异常惊诧，原来除了我所知道的解答思路之外，还有更好的解答以及更深层次的原因。还有一些题目是从来没想到过的。阅读过程是一次愉快的享受，也是脑细胞持续活跃的过程。
　　充满好奇心的人们总是能从生活的点点滴滴中想到或找到各种优化的余地，比如说，楼宇中的电梯常常显得很“傻”(微软研究院所在的希格玛大厦的电梯是一个典型的例子)，更智能或更有效的调度策略完全有可能；近距离内的交通灯联动可以有效地提高行车效率。程序员在玩电脑游戏的时候常常会想着怎么自动完成一些过程，比如说，本书中提到的俄罗斯方块游戏中如何有效地旋转和移动可快速地消除积木块、24点游戏如何自动求解、推箱子游戏如何自动求解，扫地雷游戏如何自动完成，等等。实际上，这些自然的疑问正是训练程序能力的好来源，本书采录了不少此类题目。因此，阅读本书可以满足很多人的好奇心，这也正是我自己的体会。
　　尽管作者在前言中声称“虽经过几轮审核，不少解法仍可能有漏洞或错误”，但事实上，在绝大多数题目的讲解中，作者已经由浅入深地把问题分析透了，而且，作者也为读者指出了进一步思考这些题目的方向。不同背景的人在看到这些题目的时候，可能会有不同的解法，甚至完全不同的思路。举例而言，邹欣曾经问过我如何控制CPU占用率曲线的问题，我当时的直觉是，直接截取Taskmgr调用的相关API函数，从而达到随意控制CPU占用率曲线的目的。显然这不是规范的做法，本书的分析揭示了这个问题背后的本质道理以及考问要点。另一种情况，即使有的问题你深知其理，但看过本书仍然很有收获。例如，在斐波那契数列问题中，我知道直接递归法的缺陷，也知道如何简化成迭代法来改进效率，还会推导通项公式，但是，书中的细致讲解仍然让我对这个问题有了更进一步的认识。这是本书的深度所在，如果读者更加在意所选题目背后的深层次道理，相信书中的讲解不会让你失望。
　　除了趣味性以外，本书中的题目讲解之中也融入了大量专业知识。这使得本书可以作为计算机数据结构课程或算法课程的辅助参考书。比如，有些问题的解答涉及到贪心算法或动态规划方法，算法的复杂度分析更是无处不在。数据结构教科书中介绍的链表(list)、队列、hash表和二叉树等常用数据结构也多有提及。因此，对于正在学习数据结构或算法课程的学生来说，本书中的问题正是对课程中所学知识的一次检阅，通过本书他们可以看到这些知识是如何用于解决实际问题的。从我自己的教学经验来看，这样的题解分析有助于提高学生的学习兴趣。另一方面，阅读本书也需要有必要的计算机算法和程序设计知识作为基础，否则阅读的效果会大打折扣。
　　我大致了解本书的成书过程，从策划阶段到题目收集，再到成稿和改稿，我能体会到邹欣和他的写作团队倾注了大量的精力来写作这本书。他们尽了最大的努力来编写这本书，无论是原创的题目，还是传统的题目，他们都努力把题目分析透彻并提供扩展思考的余地。邹欣在发送样稿给我的信中说道：“Our goal is to ship a top quality book. I can't say "world class", but definitely "best in China" level.”以我阅读这本书的体会来讲，他们做到了这一点。我相信，这本书的出版会符合我当初的预期，它会影响到很多人。
　　潘爱民
　　2008年2月
　　

　　1《编程之美——微软技术面试心得》第一部分
　　我在卡内基梅隆大学毕业找工作的时候，经常和其他同学一起交流面试的经验。当时令求职者“闻面色变”的公司有微软，研究所有DEC的SRC，每次有同学去微软或SRC面试，回来的时候都会被其他同学追问有没有什么有趣的面试题。
　　扉页（1）
　　扉页（2）
　　推荐序（1）
　　推荐序（2）
　　序（1）
　　序（2）
　　序（3）
　　序（4）
　　致谢（1）
　　致谢（2）
　　目录（1）
　　目录（2）
　　目录（3）
　　目录（4）
　　面试杂谈（1）
　　面试杂谈（2）
　　面试杂谈（3）
　　面试杂谈（4）