《编程之美》

　　推荐序
　　我在卡内基梅隆大学毕业找工作的时候，经常和其他同学一起交流面试的经验。当时令求职者“闻面色变”的公司有微软，研究所有DEC的SRC。每次有同学去微软或SRC面试，回来的时候都会被其他同学追问有没有什么有趣的面试题。我也是那时第一次听说“下水道井盖为什么是圆的”这一问题。
　　我自己申请加入微软美国研究院时被面试了两天，见了15个人，感觉压力很大。至今还记得当有一位面试者不断追问我论文中一个算法的收敛性时，我们进行了热烈讨论。在微软工作的十几年中，我自己也面试了非常多的新员工。特别在微软亚洲研究院的9年，经常感觉很多刚刚毕业的优秀学生基础很好，但面试的准备不足。我非常欣慰地看到邹欣工程师和微软亚洲研究院其他同事们努力编写了这本好书，和大家一起分享微软的面试心得和编程技巧。相信更多的同学会因此成为“笔霸”、“面霸”，甚至“offer霸”。
　　程序虽然很难写，却很美妙。要想把程序写好，需要学好一定的基础知识，包括编程语言、数据结构和算法。程序写得好的人通常都有缜密的逻辑思维能力和良好的数理基础，而且熟悉编程环境和编程工具。古人说“见文如见人”，我觉得程序同样也能反映出一个人的功力和风格，好的程序读来非常赏心悦目。我以前常出的一道面试题是“展示一段自己觉得写过的最好的程序”。
　　编程很艰苦，但是很有趣。本书的作者们从游戏中遇到的编程问题谈起，介绍了数字和字符串中的很多技巧，探索了数据结构的窍门，还发掘了数学游戏的乐趣。我希望读者在阅读本书时能找到编程的快乐，欣赏到编程之美。本书适合计算机学院、软件学院、信息学院高年级本科生、研究生作为软件开发的参考教材，也是程序员继续进修的优秀阅读材料，更是每位申请微软公司和其他公司软件工程师之职的面试必读秘笈。
　　人类的生活因为优秀的程序员和美妙的程序而变得更加美好。
　　沈向洋
　　微软公司杰出工程师
　　微软公司全球资深副总裁
　　2008年春节于香港
　　序
　　一位应聘者（interviewee）在我面前写下了这样的几行程序：
　　while(true){
　　if(busy)i++;
　　else
　　}
　　然后就陷入了沉思，良久，她问道：“那else怎么办？怎么能让电脑不做事情呢？”
　　我说：“对呀，怎么才能让电脑闲下来？你平时上课、玩电脑的时候有没有想过？这样吧，你可以上网查查资料。”
　　她很快地在搜索引擎中输入“50%CPU占用率”等关键字，但是搜索并没有返回什么有用的结果。
　　在她忙着搜索的时候，我又看了一遍她的简历，从简历上可以看到她的成绩不错，她学习了很多程序设计语言，也研究过“设计模式”“架构”“SOA”等，她对Windows、Linux也很熟悉。我的面试问题是：“如何写一个短小的程序，让Windows的任务管理器显示CPU的占用率为50%？”这位应聘者尝试了一些方法，但是始终没有写出一个完整的程序。面试的时间到了，她看起来比较遗憾，我也一样，因为我还有一系列的后续问题没有机会问她：
　　?如何能通过命令行参数，让CPU的使用率保持在任意位置，如90%？
　　?如何能让CPU的使用率表现为一条正弦曲线？
　　?如果你的电脑是双核（dual-coreCPU）的，那么你的程序会有什么样的结果？为什么？
　　自从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月底交出完整的第一稿，花费的时间比每一位作者预想的要长得多，一方面是大家都有日常的工作和学习任务要完成；更重要的是，美的创造和提炼，是一个漫长和痛苦的过程。要把“编程之美”表达出来，不是一件容易的事，需要创造力、想象力和持久的艰苦劳作。就像沈向洋博士经常讲的一句话——Nothingreplaceshardwork。
　　这本书的各位作者，都是利用自己的业余时间参与这个项目的，他们的创造力、热情、执着和专业精神让这本书从一个模糊的构想变成了现实。通过这次合作，我从他们那里学到了很多，借此机会，我对所有参与这个项目的同仁们说一声：谢谢！
　　在本书编写过程中，作者们得到了微软亚洲研究院的许多同事的帮助，具体请参见“致谢”。
　　我们希望书中展现的题目和分析，能像海滩上美丽的石子和漂亮的贝壳那样，反映出造化之美，编程之美。
　　邹欣
　　2007年11月于北京
　　补记
　　一晃《编程之美》已经出版10年了，在10年之后的今天，仍然有机会再次更新序言，唯有感谢和荣幸！
　　重读自己10年前写的文章（http://www.broadview.com.cn/33782），“简化、持续挑战、开拓”，这三个观点依然在持续践行……在过去的10年中，我已离开微软亚洲研究院、创办海豚浏览器、并购退出，并即将开始第二次创业旅程。每一次重大决定，都代表着我的不断挑战和开拓。
　　回想起当年“痛不欲生”地在邹老师的“摧残”之下，一次次迭代改进，似乎暗无天日、永远没有尽头……这段经历，已经成为我用来实证“坚持努力，做足过程，成果自现”的案例。
　　感谢读者的认可，感谢出版社和编辑的不懈努力，才有机会让这本书再次出发！
　　祝每一位读者都能挑战自己的极限，开拓一片天地！
　　刘铁锋
　　2018年8月
　　致谢
　　《编程之美》这本书从构思、编写到最后的出版，得到了许多同事和朋友的帮助。在此作者们要特别感谢以下人士。
　　微软亚洲研究院的多位同事热情地与我们分享了他们觉得有意思的题目，他们分别是：邓科峰、宋京民、宋江云、刘晓辉、赵爽、李劲宇、李愈胜和MattScott。
　　感谢微软亚洲研究院技术创新组的同事梁潇、殷秋丰，他们认真审阅了所有的题目和解答，找出了不少bug1。技术创新组的另外几位优秀工程师李愈胜、魏颢、赵婧还帮助我们解决了书中的几个难题。
　　感谢研究院的同事、著名技术作家潘爱民对我们的鼓励，他审阅了全部稿件，并且提出了不少意见。
　　本书的封面和插图都出自研究院的实习生高霖之手，他在10余个构图都被否定的情况下，坚持不懈，最后拿出了“九连环”的封面设计，得到作者和出版方的一致认同。
　　在本书写作的过程中，作者们各自的“老板”——杨晓松、姚麒、田江森和刘激扬都给予了不少支持，在此特表示感谢。
　　作者们的“老板的老板”，研究院前任院长，微软公司资深副总裁沈向洋博士，现任院长洪小文博士对本书一直很关心和支持。沈向洋博士在百忙之中还亲自为本书写了序。
　　1本书残留的bug都是作者们的责任。
　　微软亚洲研究院市场部的金俊女士、葛瑜女士对本书的推广提供了很大帮助。负责www.msra.cn网站的徐鹏、马小宁、黄贤俊为本书设计了专栏。
　　感谢博文视点编辑团队。感谢在本书写作前期与我们合作过的编辑方舟,在写作后期参与合作的编辑徐定翔和李滟波。特别感谢自始至终和作者们一起工作的编辑周筠、杨绣国。他们和作者们一同构思，耐心修改，没有他们的不懈努力，以及细致的编辑和推广工作，就没有《编程之美》的成功上市。