电子工业出版社-网上书店

自计算机与软件出现以来，在近半个世纪里，软件开发所能衍生出的无限创意，深深吸引着全世界的青年。在二进制的世界里，这帮年轻的程序员充分发挥自己的热情和想像力，仅仅通过对“1”和“0”的互换操作，他们辟地开天，恣意汪洋地创造出一个又一个的奇迹。今天，前几代“青年”积累构建的虚拟世界正在深刻地改变我们的现实生活。软件开发过程的复杂程度已经足以媲美传统的工业生产。前人堆积如山的开发经验和规则，令象牙塔里的学子们望而生畏。今天软件学院的学生们站在巨人的肩膀上，用最流行的语言和工具武装到了牙齿，但似乎缺少了前辈们的热情，也忘记了编程的乐趣所在——发现问题，分析问题，解决问题，寻找更优的解法，总结规律，抽象出算法的过程，以及由此产生的成就感。本书收集了大约60道微软技术面试题，作者试图通过书中妙趣横生的问题和详细的解说，面试者的各种小故事，告诉读者微软需要什么样的技术人才，重视什么样的能力，如何甄别人才。但它更深层的意义在于引导读者思考，帮助读者重拾通过编程探索未知世界的乐趣。

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

第2章  数字之魅——数字中的技巧	117
2.1  求二进制数中1的个数	119
2.2  不要被阶乘吓倒	125
2.3  寻找发帖“水王”	129
2.4  1的数目	132
2.5  寻找最大的K个数	139
2.6  精确表达浮点数	147
2.7  最大公约数问题	150
2.8  找符合条件的整数	155
2.9  斐波那契（Fibonacci）数列	160
2.10 寻找数组中的最大值和最小值	166
2.11 寻找最近点对	171
2.12 快速寻找满足条件的两个数	178
2.13 子数组的最大乘积	182
2.14 求数组的子数组之和的最大值	185
2.15 子数组之和的最大值（二维）	192
2.16 求数组中最长递增子序列	198
2.17 数组循环移位	204
2.18 数组分割	207
2.19 区间重合判断	211
2.20 程序理解和时间分析	215
2.21 只考加法的面试题	217
第3章  结构之法——字符串及链表的探索	219
3.1  字符串移位包含的问题	221
3.2  电话号码对应英语单词	224
3.3  计算字符串的相似度	230
3.4  从无头单链表中删除节点	234
3.5  最短摘要的生成	237
3.6  编程判断两个链表是否相交	241
3.7  队列中取最大值操作问题	244
3.8  求二叉树中节点的最大距离	250
3.9  重建二叉树	256
3.10 分层遍历二叉树	262
3.11 程序改错	268
第4章  数学之趣——数学游戏的乐趣	273
4.1  金刚坐飞机问题	275
4.2  瓷砖覆盖地板	279
4.3  买票找零	282
4.4  点是否在三角形内	286
4.5  磁带文件存放优化	291
4.6  桶中取黑白球	294
4.7  蚂蚁爬杆	299
4.8  三角形测试用例	303
4.9  数独知多少	307
4.10 数字哑谜和回文	315
4.11 挖雷游戏的概率	322

推荐序
我在卡内基梅隆大学毕业找工作的时候，经常和其他同学一起交流面试的经验。当时“闻面色变”的公司有微软，研究所有DEC的SRC。每次有同学去微软或SRC 面试回来都被其他人追问有没有什么有趣的面试题。我也是那时第一次听说下水道井盖为什么是圆的。
我自己申请微软美国研究院时被面试了两天，见了15个人，感觉压力很大。 至今还记得被一位面试官不断追问我论文中一个算法的收敛性的热烈讨论。在微软工作的十几年中，我自己也面试了非常多的新员工。特别在微软亚洲研究院的九年，经常感觉很多刚刚毕业的优秀学生基础很好，但面试的准备不足。我非常欣慰地看到邹欣工程师和微软亚洲研究院其他同事们努力编写了这本好书，和大家一起分享微软的面试心得和编程技巧。相信更多的同学会因此成为“笔霸”，“面霸”，甚至“offer霸”。 
程序很美妙，虽然很难写。程序要想写的好，需要学好一定的基础知识，包括编程语言，数据结构和算法。程序写的好的人通常都有慎密的逻辑思维能力和良好的数理基础。还需要熟悉编程环境和编程工具。古人说“见文如见人”。我觉得程序同样也能反映出一个人的功力和风格。好的程序读来非常赏心悦目。我以前常问的一道面试题是“写一段自己觉得写过的最好的程序”。
编程很艰苦，但是很有趣。本书的作者们从游戏中遇到的编程问题谈起，介绍了数字和字符串中的很多技巧，探索了数据结构的窍门，还发掘了数学游戏的乐趣。我希望读者在阅读本书是能找到编程的快乐，欣赏到编程之美。本书适合计算机学院、软件学院、信息学院高年级本科生、研究生作为软件开发的参考教材。也是程序员继续进修的优秀阅读材料。更是每位申请微软公司和其他公司软件工程师面试的必读秘笈。
人类的生活因为优秀的程序员和美妙的程序而变得更加美好。
沈向洋
微软公司杰出工程师
微软公司全球资深副总裁
2008年春节于香港

序
一位应聘者 (interviewee) 在我面前写下了这样的几行程序： 
while (true) { 
  if (busy)  i++; 
  else
} 
然后就陷入了沉思，良久，她问道：那else 怎么办？怎么能让电脑不做事情？ 
我说：对呀，怎么才能让电脑闲下来？你平时上课，玩电脑的时候有没有想过？这样吧，你可以上网查查资料。 
她很快地在搜索引擎中输入“50%  CPU 占用率”等关键字，但是搜索并没有返回什么有用的结果。 
在她忙着搜索的时候，我又看了一遍她的简历，从简历上可以看到她的成绩不错，她学习了很多程序设计语言，也研究过“设计模式”、“架构”、“ SOA”等，她对Windows、Linux 也很熟悉。我的面试问题是：“如何写一个短小的程序，让Windows的任务管理器显示CPU 占用率保持为50%？”这位应聘者尝试了一些方法，但是始终没有写出一个完整的程序。　面试的时间到了，她看起来比较遗憾，我也一样，因为我还有一系列的后续问题没有机会问她： 
• 如何能通过命令行参数，让CPU 的使用率在保持任意位置， 如90%？ 
• 如何能让CPU 的使用率表现为一条正弦曲线？ 
• 如果你的电脑是双核（dual-core），那你的程序会有什么样的结果？为什么？ 
作为面试者，我最希望看到应聘者能给出独具匠心的回答，这样我也能从中学到一些“妙招”。遗憾的是看到“妙招”的时候并不多。 自从2005年回到微软亚洲研究院担任开发经理一职以来，我面试过不少应聘者，也为微软校园招聘出过考题，做过员工和实习生的培训。我也了解到不少同学认为软件开发的工作没意思，是“IT 民工”、“软件蓝领”。我和其他同事也听到一些抱怨，说一些高校计算机科学的教育只停留在原理，而忽视了对原理和技术的理解和运用。 
写程序真的没有意思？为什么许多微软的员工乐此不疲？我和一些喜欢编程的员工和实习生编了这本书，这本书想通过分析微软面试中经常出现的题目，来展示编程的乐趣。编程的乐趣在于探索，而不是在于背答案。面试的过程就是展现分析能力、探索能力的过程，在面试中展现的巧妙的思路，简明的算法，严谨的数学分析就是我们这本书要谈的“编程之美”。 
还有不少同学问：“你们是不是有面试题库？”  言下之意是每个应聘者都是从“库”中随机抽出一道题目，如果答对了，就中了，如果答错了，就bye-bye 了。书中的一些关于面试的问答，能回答这样一些疑惑。 
本书的题目，一部分来源于各位作者平时自己的实践，例如有一次一位应聘者滔滔不绝地讲述自己如何在某大型项目中进行CPU压力测试，听上去水分不少，我一边听一边琢磨“怎么才能考察是否真正懂了CPU，任务调度。。。。。。”，后来就有了上面提到的“CPU使用率”的面试题。有些题目在网上流传较广，但是能得到正解的不多， 我们在书中加上了详细的分析，提出了一些扩展问题。有些题目在一些教科书和专业书籍中有更深入的分析和解答，读者可以参考。 
书中的大多数题目都能在四十五分钟左右内解决，这也是微软一次技术面试的时间。 本书不是一个“答案汇编”，很多题目并没有给出完整的答案，有些题目还有更多的问题要读者去解答。这是这本书和其他书籍不一样的地方。 面试不是闭卷考试，如果大家都背好了“井盖为什么是圆的”的答案来面试，但是却不会变通，那结果肯定是令人失望的。　 
为了方便读者评估自己的水平，我们还按照每道题目的难度制定了相应的“星级”：
•	一颗星：不用查阅资料，在20分钟内完成
•	两颗星：可以在40分钟内完成
•	三颗星：需要查阅一些资料，在60分钟左右完成
由于每个人的专业背景，经历，兴趣不一样，这种“星级”仅仅是一种参考。
我们的水平非常有限，书中的题目并不能代表程序设计各个方面的最新进展，虽然经过几轮审核，不少解法都可能有漏洞或错误，希望广大读者能给我们指正。我们计划在微软亚洲研究院的门户网站( www.msra.cn) 上开辟专栏和读者交流 – 初学者和高手都非常欢迎！
本书的内容分为下面几个部分： 
•	玩电脑：电脑上的游戏是给人玩的，CPU 也可以让人‘玩’。这一部分的题目从游戏和作者平时遇到得的有趣问题出发，展现一些并不为人重视的问题，并且加以分析和总结。希望其中化繁为简的有趣思路能够对读者解决其它复杂问题有所帮助。 
•	字符串和常用数据结构问题：对字符以及常用数据结构的处理几乎是每个程序中必然会涉及到的问题，这一部分汇集了常用的对字符串以及链表、队列以及树等操作的题目。 
•	数字问题：编程的过程实际上就是和数字以及字符的打交道的过程。如何提高掌控这些数字和字符的能力对提高编程能力至关重要。这一部分收集了一些好玩的对数字进行处理的题目。 
•	数学问题：书中还列了一些不需要写具体程序的数学问题，但是其中显示的原理和解决问题的思路对于提高思维能力还是很重要的，我们把它们单独列出。 
•	关于笔试，面试，职业选择的一些问答：微软的各种技术职位，招聘流程是很多学生所关心的，因此我们把一些相关的介绍和讨论也收录了进来。 
我们希望《编程之美》的读者是： 
1. 计算机系、软件学院或相关专业的大学生、研究生，可以把这本书当作一个习题集。 
2. 面临求职面试的IT从业人员，不妨把这本书当作“面试真题”，演练一下。 
3. 编程爱好者，可以平时随便翻翻，重温数学和编程技能，开拓思路，享受思考的乐趣。 
《编程之美》由下面几位作者协同完成，如果把这本书比作一个软件项目，它有下面的各个阶段，每个阶段有不同的目标和角色： 
1． 构想阶段：邹欣 
2． 计划阶段：邹欣，刘铁锋，莫瑜。 
3． 实现阶段/里程碑（一）：上述全部人员，加上李东，张晓，陈远，高霖 （负责封面设计）。 
4． 实现阶段/里程碑（二）： 上述全部人员，加上梁举，胡睿。 
5． 稳定阶段：上述全部人员，加上博文视点的编辑们。 
6． 发布阶段：邹欣，刘铁锋，和博文视点的编辑们。 
这本书从2007年2月开始构思，到2007年11月底交出完整的第一稿，花费的时间比每一位作者预想的要长得多，一方面是大家都有日常的工作和学习任务要完成；更重要的是，美的创造和提炼，是一个漫长和痛苦的过程。要把“编程之美”表达出来，不是一件容易的事，需要创造力、想象力和持久的艰苦劳作。就像沈向洋博士经常讲的一句话——Nothing replaces hard work。 
这本书的各位作者，都是利用自己的业余时间参与这个项目，他们的创造力、热情、执着和专业精神让这本书从一个模糊的构想变成了现实。 通过这次合作，我从他们那里学到了很多，借此机会，对所有参与这个项目的同仁们说一声： 谢谢！ 
在本书编写过程中，作者们得到了许多微软亚洲研究院的同事和实习生的帮助，具体请参见“致谢”。 
我们希望书中展现的题目和分析，能像海滩上美丽的石子和漂亮的贝壳那样，反映出造化之美，编程之美。 
邹欣 
2007．11．26

本书配套资源下载

对不起，暂无音视频资源！

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