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

梦想改变世界，据说编程的人都怀揣着一个改变世界的梦想：编程神奇而充满力量。无数的年轻人投身其中，用梦想和思考改变世界。《编程之美：微软技术面试心得》是来自微软技术人员的杰作，他们和你有同样的梦想。 

这本书收集了约60道算法和程序设计题目。作者试图从书中各种有趣的问题出发，引导读者发现问题，分析问题，解决问题，寻找更优的解法。本书的内容分为下面几个部分：（1）游戏之乐：从游戏和其他有趣问题出发，化繁为简，分析总结。（2）数字之魅：编程的过程实际上就是和数字及字符打交道的过程。这一部分收集了一些好玩的对数字进行处理的题目。（3）结构之法：汇集了常见的对字符串、链表、队列，以及树等进行操作的题目。（4）数学之趣：列举了一些不需要写具体程序的数学问题，锻炼读者的抽象思维能力。书中绝大部分题目都提供了详细的解说。 每道题目后面还有一至两道扩展问题，供读者进一步钻研。书中还回答了读者关于IT业面试，招聘，职业发展的疑问。这本书的很多题目会出现在IT 行业的各种笔试、面试中，但这本书更深层的意义在于引导读者思考，和读者共享思考之乐，编程之美。

邹欣，现任微软Windows中国工程团队首席研发总监。1996 ?C 2003年，邹欣在微软Outlook团队从事开发工作；2003 ?C 2005年，他在微软内部质量工具团队和Visual Studio团队负责软件项目管理工具的开发；2005 ?C 2012年，他担任微软亚洲研究院技术创新组研发主管，负责研究成果的产品化和创新项目；2012 ?C 2014年，他担任微软亚洲互联网工程院首席研发总监，负责必应搜索客户端、必应输入法、必应词典等产品。2014 ?C 现在，他担任微软Windows工程院首席研发总监，负责Edge，Cortana, UWP App 在中国的发展。邹欣于1991年获北京大学计算机软件专业学士学位。1996年获美国美国韦恩州立大学（Wayne State University）计算机软件专业硕士学位。他在2007年出版了《移山之道》，于2008年出版了《编程之美》 （合作），于2014年出版了《构建之法——现代软件工程》。

第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 24点游戏
1.17 俄罗斯方块游戏
1.18 挖雷游戏

第2章 数字之魅–数字中的技巧
2.1 求二进制数中1的个数
2.2 不要被阶乘吓倒
2.3 寻找发帖“水王”
2.4 1的数目
2.5 寻找的K个数
2.6 精确表达浮点数
2.7 公约数问题
2.8 找符合条件的整数
2.9 斐波那契（Fibonacci）数列
2.10 寻找数组中的值和小值
2.11 寻找近点对
2.12 快速寻找满足条件的两个数
2.13 子数组的乘积
2.14 求数组的子数组之和的值
2.15 子数组之和的值（二维）
2.16 求数组中长递增子序列
2.17 数组循环移位
2.18 数组分割
2.19 区间重合判断
2.20 程序理解和时间分析
2.21 只考加法的面试题

第3章 结构之法–字符串及链表的探索
3.1 字符串移位包含的问题
3.2 电话号码对应英语单词
3.3 计算字符串的相似度
3.4 从无头单链表中删除节点
3.5 短摘要的生成
3.6 编程判断两个链表是否相交
3.7 队列中取值操作问题
3.8 求二叉树中节点的距离
3.9 重建二叉树
3.10 分层遍历二叉树
3.11 程序改错

第4章 数学之趣–数学游戏的乐趣
4.1 金刚坐飞机问题
4.2 瓷砖覆盖地板
4.3 买票找零
4.4 点是否在三角形内
4.5 磁带文件存放优化
4.6 桶中取黑白球
4.7 蚂蚁爬杆
4.8 三角形测试用例
4.9 数独知多少
4.10 数字哑谜和回文
4.11 挖雷游戏的概率

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