序

一位应聘者（interviewee）在我面前写下了这样的几行程序：

    while (true) {
      if (busy)  i++;
      else
    }

然后就陷入了沉思，良久，她问道：“那else怎么办？怎么能让电脑不做事情呢？”

我说：“对呀，怎么才能让电脑闲下来？你平时上课、玩电脑的时候有没有想过？这样吧，你可以上网查查资料。”

她很快地在搜索引擎中输入“50% CPU占用率”等关键字，但是搜索并没有返回什么有用的结果。

在她忙着搜索的时候，我又看了一遍她的简历，从简历上可以看到她的成绩不错，她学习了很多程序设计语言，也研究过“设计模式”“架构”“SOA”等，她对Windows、Linux也很熟悉。我的面试问题是：“如何写一个短小的程序，让Windows的任务管理器显示CPU的占用率为50%? ”这位应聘者尝试了一些方法，但是始终没有写出一个完整的程序。面试的时间到了，她看起来比较遗憾，我也一样，因为我还有一系列的后续问题没有机会问她：

· 如何能通过命令行参数，让CPU的使用率保持在任意位置，如90%？

· 如何能让CPU的使用率表现为一条正弦曲线？

· 如果你的电脑是双核（dual-core CPU）的，那么你的程序会有什么样的结果？为什么？自从2005年回到微软亚洲研究院后，我面试过不少应聘者，作为面试者，我最希望看到应聘者给出独具匠心的回答，这样我也能从中学到一些“妙招”。遗憾的是看到“妙招”的时候并不多。

我也为微软校园招聘出过考题，走访过不少软件学院，还为员工和实习生做过培训。我了解到不少同学认为软件开发的工作没意思，是“IT民工”“软件蓝领”。我和其他同事也听到一些抱怨，说一些高校计算机科学的教育只停留在原理上，忽视了对原理和技术的理解和运用。

写程序真的没有意思吗？为什么许多微软的员工和软件业界的牛人乐此不疲？我和一些喜欢编程的同事和实习生创作编写了这本书，我们希望通过分析微软面试中经常出现的题目，来展示编程的乐趣。编程的乐趣在于探索，而不是在于背答案。面试的过程就是展现分析能力、探索能力的过程，在面试中展现出来的巧妙的思路、简明的算法、严谨的数学分析就是我们这本书要谈的“编程之美”。

有时候会有同学问：“你们是不是有面试题库？”言下之意是每个应聘者都是从“库”中随机抽出一道题目，如果答对了，就中了；如果答错了，就bye-bye了。书中有一些关于面试的问答，我想它们可以回答这样一些疑惑。

本书的题目，一部分源自各位作者平时想出来的，例如，有一次一位应聘者滔滔不绝地讲述自己如何在某大型项目中进行CPU的压力测试，听上去水分不少，我一边听一边琢磨“怎样才能考察一个人是否真正懂了CPU，任务调度……”，后来就有了上面提到的“CPU使用率”的面试题。有些题目来自于平时的实践和讨论，比如一些和游戏相关的题目。有些题目是随手拈来，比如我看到朋友的博客上有一道面试题，自己做了一下，发现自己的解法并不是最优的，但是，倒是可以作为一个面试题的题目，第2章的“程序理解和时间分析”就是这么得来的。书中有些题目在网上流传较广，但是网上流传的解法并不是正解，我们在书中加上了详细的分析，并提出了一些扩展问题。还有一些题目在教科书和专业书籍中有更深入的分析和解答，读者可以参考。

书中的大多数题目都能在45分钟内解决，这也是微软一次技术面试的时间。本书不是一个“答案汇编”，很多题目并没有给出完整的答案，有些题目还有更多的问题要读者去解答，这是本书和其他书籍不一样的地方。面试不是闭卷考试，如果大家都背好了“井盖为什么是圆的”的答案来面试，但是却不会变通，那结果肯定是令人失望的。

为了方便读者评估自己的水平，我们还按照每道题目的难度制定了相应的“星级”：

· 一颗星：不用查阅资料，在20分钟内完成；

· 两颗星：可以在40分钟内完成；

· 三颗星：需要查阅一些资料，在60分钟内完成。

由于每个人的专业背景、经历、兴趣不一样，这种“星级”仅仅是一种参考。

作者们水平有限，书中的题目并不能代表程序设计各个方面的最新进展，虽然经过几轮审核，不少解法仍可能有漏洞或错误，希望广大读者能给我们指正。我们已在微软亚洲研究院的门户网站（www.msra.cn）上开辟专栏（www.msra.cn/bop）和读者交流——初学者和高手都非常欢迎！

本书的内容分为下面几个部分。

· 游戏之乐：电脑上的游戏是给人玩的，CPU也可以让人“玩”。这一部分的题目从游戏和作者平时遇到的有趣问题出发，展现一些并不为人重视的问题，并且加以分析和总结。希望其中化繁为简的思路能够对读者解决其他复杂问题有所帮助。

· 数字之魅：编程的过程实际上就是和数字及字符打交道的过程。如何提高掌控这些数字和字符的能力对提高编程能力至关重要。这一部分收集了一些好玩的对数字进行处理的题目。

· 结构之法：对字符及常用数据结构的处理几乎是每个程序必然会涉及的问题，这一部分汇集了对常用的字符串、链表、队列以及树等进行操作的题目。

· 数学之趣：书中还列了一些不需要写具体程序的数学问题，但是其中显示的原理和解决问题的思路对于提高思维能力还是很重要的，我们把它们单独列出来。

· 关于笔试、面试、职业选择的一些问答：微软的面经，各种技术职位的介绍是很多学生所关心的内容，因此我们把一些相关的介绍和讨论也收录了进来。

我们希望《编程之美》的读者是：

1．大学计算机系、软件学院或相关专业的大学生、研究生，可以把这本书当作一个习题集；

2．面临求职笔试、面试的IT从业人员，不妨把这本书当作“面试真题”，演练一下；

3．编程爱好者，平时可以随便翻翻，重温数学和编程技能，开拓思路，享受思考的乐趣。

《编程之美》由下面几位作者协同完成，如果把这本书的写作比作一个软件项目，它有下面的各个阶段，每个阶段则有不同的目标和角色。

1．构想阶段：邹欣。

2．计划阶段：邹欣、刘铁锋、莫瑜。

3．实现阶段/里程碑（一）：上述全部人员，加上李东、张晓、陈远、高霖（负责封面设计）。

4．实现阶段/里程碑（二）：上述全部人员，加上梁举、胡睿。

5．稳定阶段：上述全部人员，加上博文视点的编辑们。

6．发布阶段：邹欣、刘铁锋和博文视点的编辑们。

这本书从2007年2月开始构思，到2007年11月底交出完整的第一稿，花费的时间比每一位作者预想的要长得多，一方面是大家都有日常的工作和学习任务要完成；更重要的是，美的创造和提炼，是一个漫长和痛苦的过程。要把“编程之美”表达出来，不是一件容易的事，需要创造力、想象力和持久的艰苦劳作。就像沈向洋博士经常讲的一句话——Nothing replaces hard work。

这本书的各位作者，都是利用自己的业余时间参与这个项目的，他们的创造力、热情、执着和专业精神让这本书从一个模糊的构想变成了现实。通过这次合作，我从他们那里学到了很多，借此机会，我对所有参与这个项目的同仁们说一声：谢谢！

在本书编写过程中，作者们得到了微软亚洲研究院的许多同事的帮助，具体请参见“致谢”。

我们希望书中展现的题目和分析，能像海滩上美丽的石子和漂亮的贝壳那样，反映出造化之美，编程之美。

邹欣

2007年11月于北京