编程之美--微软技术面试心得(08年度畅销榜NO.1) (2010 年度畅销榜NO.2679 )

本书收集了约60道算法和程序设计题目，这些题目大部分在近年的笔试，面试中出现过，或者是被微软员工热烈讨论过。作者试图从书中各种有趣的问题出发，引导读者发现问题，分析问题，解决问题，寻找更优的解法。本书的内容分为下面几个部分：\r\n\r\n
游戏之乐：从游戏和其他有趣问题出发，化繁为简，分析总结。\r\n\r\n
数字之魅：编程的过程实际上就是和数字及字符打交道的过程。这一部分收集了一些好玩的对数字进行处理的题目。\r\n\r\n
结构之法：汇集了常见的对字符串、链表、队列，以及树等进行操作的题目。\r\n\r\n
数学之趣：列举了一些不需要写具体程序的数学问题，锻炼读者的抽象思维能力。\r\n\r\n
书中绝大部分题目都提供了详细的解说。 每道题目后面还有一至两道扩展问题，供读者进一步钻研。\r\n\r\n
书中还讲述了面试的各种小故事，告诉读者微软需要什么样的技术人才，重视什么样的能力，如何甄别人才。回答读者关于IT业面试，招聘，职业发展的疑问。这本书的很多题目会出现在IT 行业的各种笔试，面试中。但本书更深层的意义在于引导读者思考，和读者共享思考之乐，编程之美。

第1章 游戏之乐——游戏中碰到的题目 \r\n　1.1 让CPU占用率曲线听你指挥 \r\n　1.2 中国象棋将帅问题 \r\n　1.3 一摞烙饼的排序 \r\n　1.4 买书问题 \r\n　1.5 快速找出故障机器 \r\n　1.6 饮料供货 \r\n　1.7 光影切割问题 \r\n　1.8 小飞的电梯调度算法 \r\n　1.9 高效率地安排见面会 \r\n　1.10 双线程高效下载 \r\n　1.11 NIM（1）一排石头的游戏 \r\n　1.12 NIM（2）“拈”游戏分析 \r\n　1.13 NIM（3）两堆石头的游戏 \r\n　1.14 连连看游戏设计 \r\n　1.15 构造数独 \r\n　1.16 点游戏 \r\n　1.17 俄罗斯方块游戏 \r\n　1.18 挖雷游戏 \r\n第2章 数字之魅——数字中的技巧 \r\n　2.1 求二进制数中1的个数 \r\n　2.2 不要被阶乘吓倒 \r\n　2.3 寻找发帖“水王” \r\n　2.4 的数目 \r\n　2.5 寻找最大的K个数 \r\n　2.6 精确表达浮点数 \r\n　2.7 最大公约数问题 \r\n　2.8 找符合条件的整数 \r\n　2.9 斐波那契（Fibonacci）数列 \r\n　2.10 寻找数组中的最大值和最小值 \r\n　2.11 寻找最近点对 \r\n　2.12 快速寻找满足条件的两个数 \r\n　2.13 子数组的最大乘积 \r\n　2.14 求数组的子数组之和的最大值 \r\n　2.15 子数组之和的最大值（二维） \r\n　2.16 求数组中最长递增子序列 \r\n　2.17 数组循环移位 \r\n　2.18 数组分割 \r\n　2.19 区间重合判断 \r\n　2.20 程序理解和时间分析 \r\n　2.21 只考加法的面试题 \r\n第3章 结构之法——字符串及链表的探索 \r\n　3.1 字符串移位包含的问题 \r\n　3.2 电话号码对应英语单词 \r\n　3.3 计算字符串的相似度 \r\n　3.4 从无头单链表中删除节点 \r\n　3.5 最短摘要的生成 \r\n　3.6 编程判断两个链表是否相交 \r\n　3.7 队列中取最大值操作问题 \r\n　3.8 求二叉树中节点的最大距离 \r\n　3.9 重建二叉树 \r\n　3.10 分层遍历二叉树 \r\n　3.11 程序改错 \r\n第4章 数学之趣——数学游戏的乐趣 \r\n　4.1 金刚坐飞机问题 \r\n　4.2 瓷砖覆盖地板 \r\n　4.3 买票找零 \r\n　4.4 点是否在三角形内 \r\n　4.5 磁带文件存放优化 \r\n　4.6 桶中取黑白球 \r\n　4.7 蚂蚁爬杆 \r\n　4.8 三角形测试用例 \r\n　4.9 数独知多少 \r\n　4.10 数字哑谜和回文 \r\n　4.11 挖雷游戏的概率

一位应聘者 (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 也可以让人‘玩’。这一部分的题目从游戏和作者平时遇到得的有趣问题出发，展现一些并不为人重视的问题，并且加以分析和总结。希望其中化繁为简的有趣思路能够对读者解决其它复杂问题有所帮助。 • 字符串和常用数据结构问题：对字符以及常用数据结构的处理几乎是每个程序中必然会涉及到的问题，这一部分汇集了常用的对字符串以及链表、队列以及树等操作的题目。 • 数字问题：编程的过程实际上就是和数字以及字符的打交道的过程。如何提高掌控这些数字和字符的能力

《编程之美》小组

无封面