《编程之美:微软技术面试心得》是一本让人着迷的书!阅读起来。有些题目的内容会引起强烈的共鸣,尤其是那些自己非常熟悉并且又深知解答的题目;也有一些题目让我异常惊诧,原来除了我所知道的解答思路之外,还有更好的解答以及更深层次的原因。还有一些题目是从来没想到过的。阅读过程是一次愉快的享受,也是脑细胞持续活跃的过程。
自计算机与软件出现以来,在近半个世纪里,软件开发所能衍生出的无限创意,深深吸引着全世界的青年。在二进制的世界里,这帮年轻的程序员充分发挥自己的热情和想像力,仅仅通过对“1”和“0”的互换操作,他们辟地开天,恣意汪洋地创造出一个又一个的奇迹。今天,前几代“青年”积累构建的虚拟世界正在深刻地改变我们的现实生活。软件开发过程的复杂程度已经足以媲美传统的工业生产。前人堆积如山的开发经验和规则,令象牙塔里的学子们望而生畏。今天软件学院的学生们站在巨人的肩膀上,用*流行的语言和工具武装到了牙齿,但似乎缺少了前辈们的热情,也忘记了编程的乐趣所在——发现问题,分析问题,解决问题,寻找更优的解法,总结规律,抽象出算法的过程以及由此产生的成就感。本书收集了大约60道微软技术面试题,作者试图通过书中

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

人类的生活因为**的程序员和美妙的程序而变得更加美好。

沈向洋
微软公司杰出工程师
微软公司全球**副总裁
2008年春节于香港

第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
……

在线视听
这是一本让人着迷的书!
从我得到样书的那一刻起,在每天的闲暇时间阅读和思索这本书中的题目就成了我的一个新习惯。虽然网络上早就流传着不少微软面试题,坊间也不乏一些程序员面试类的图书,但是像这样集中展示高水平编程面试题目,并且以启发性方式对这些题目予以权威解答的图书,这还是**本。对于那些正在准备面试的同学来说,这本书毫无疑问是宝贵的学习资料。而在我看来,即使是对于已经工作的程序员来说,这本书也是非常值得用心阅读的。
实话实说,对于算法和数学类谜题的意义和价值,在程序员社群里长期以来就存在很大的争议。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月