编程之美：微软技术面试心得 - (EPUB全文下载)

文件大小：0.34 mb。
文件格式：epub 格式。
书籍内容：

编程之美：微软技术面试心得
第1章 游戏之乐——游戏中碰到的题目
第2章 数字之魅——数字中的技巧
第3章 结构之法——字符串及链表的探索
第4章 数学之趣——数学游戏的乐趣
索引
创作后记
第1章 游戏之乐——游戏中碰到的题目
研究院举办过几届桌上足球（football）公开赛，第一届的冠军是一位文静的女实习生。
这一章的题目原计划叫做“Problem Solving”——运用所学的知识解决问题，直译为“问题解决”，甚为不美。事实上这里面大部分题目都是和游戏相关的，因此本章改名为“游戏之乐”。这些题目从游戏和作者平时遇到的有趣问题出发，向程序员提出挑战。
个人电脑（PC）在蹒跚起步的时候，就被当时的主流观点视为玩具。PC上的确有各种各样的游戏，电脑上的游戏是给人玩的，如果你愿意，CPU也可以让人“玩”。
笔者曾经用“CPU使用率”这个问题问了十几个应聘者，一个典型的模式如下。
我：笔试考得怎么样？发挥了多少水平？
答：我不习惯在纸上写程序，平时都在电脑上写……
我：那你对Windows、操作系统这些东西熟悉吗？
答：那是相当熟悉……
我：好，那你可否在这笔记本电脑上帮我解决一个问题——让 CPU 的使用率划出一条直线，比如就在50%的地方。
这个时候可以观察应聘者的好几个方面。
1.应聘者面对这个陌生问题的时候如何开始分析。
有人知道观察任务管理器如何运行，有人在纸上写写画画，有人明显没有什么想法。
2.当提示可以在网上搜索资料时，应聘者如何寻找资料，如何学习。
比如，有一位学生很快地用快捷键在 IE中打开了几个 Tab窗口，然后每个窗口输入不同的搜索关键字。当我提示在 MSDN 上查找一些函数的时候，有些人根本不知道 MSDN 网站应该怎么用。有些人反复读了函数的说明，仍不得其解。
3.在电脑上是怎么写程序，怎么调试程序的。
有人能很娴熟地使用C/C#的各种语言特性，很快地写出程序，有人写的程序编译了好几次都不能通过，对编译错误束手无策。程序第一次运行的时候，任务管理器的CPU使用率不按预想的轨道运行，这时候有人就十分慌乱，在程序中瞎改一通，希望能“蒙”对。有人则有条理地分析，最后找到并解决问题。
我想，45分钟下来，应聘者的思考能力、学习能力、技术能力如何，应该很清楚了。行还是不行，双方都明白了。
这一章的其他题目大多和游戏有关，同学们在玩“空当接龙”“俄罗斯方块”，甚至“魔兽”的时候，有没有动过好奇心——这个程序为什么这么酷，如果是我来写，应该怎么做？有没有把好奇心转化为行动？
喜欢玩电脑、会玩电脑的人，也会运用电脑解决实际问题，这也是我们要找的人才。
1.1 让CPU占用率曲线听你指挥
写一个程序，让用户来决定Windows任务管理器（Task Manager）的CPU占用率。程序越精简越好，计算机语言不限。例如，可以实现下面三种情况[1]：
1.CPU的占用率固定在50%，为一条直线；
2.CPU的占用率为一条直线，具体占用率由命令行参数决定（参数范围1~ 100）；
3.CPU的占用率状态是一个正弦曲线。
分析与解法
有一名学生写了如下的代码：
while（true）
{
if（busy）
i++；
else
}
然后她就陷入了苦苦思索：else干什么呢？怎么才能让电脑不做事情呢？CPU使用率为0的时候，到底是什么东西在用CPU？另一名学生花了很多时间构想如何“深入内核，以控制CPU占用率”——可是事情真的有这么复杂吗？
MSRA IEG（Microsoft Research Asia,Innovation Engineering Group）的一些实习生写了各种解法，他们写的简单程序可以达到如图1-1所示的效果。
图1-1 编程控制CPU占用率呈现正弦曲线形态
看来这并不是不可能完成的任务。让我们仔细地回想一下写程序时曾经碰到的问题，如果不小心写了一个死循环，CPU占用率就会跳到最高，并且一直保持在100%。我们也可以打开任务管理器[2]，实际观测一下它是怎样变动的。凭肉眼观察，它大约是1秒钟更新一次。一般情况下，CPU使用率会很低。但是，当用户运行一个程序，执行一些复杂操作的时候，CPU的使用率会急剧升高。当用户晃动鼠标时，CPU的使用率也有小幅度的变化。
那当任务管理器报告CPU使用率为0的时候，是谁在使用CPU呢？通过任务管理器的“进程（Process）”一栏可以看到，System Idle Process占用了CPU空闲的时间——这时候大家该回忆起在“操作系统原理”这门课上学到的一些知识了吧。系统中有那么多进程，它们什么时候能“闲下来”呢？答案很简单，这些程序或在等待用户的输入，或者在等待某些事件的发生[3]，或者主动进入休眠状态[4]。
在任务管理器的一个刷新周期内，CPU 忙（执行应用程序）的时间和刷新周期总时间的比率，就是CPU的占用率，也就是说，任务管理器中显示的是每个刷新周期内CPU占用率的统计平均值。因此，我们可以写一个程序，让它在任务管理器的刷新期间内一会儿忙，一会儿闲，然后调节忙/闲的比例，就可以控制任务管理器中显示的CPU占用率。
解法一：简单的解法
要操纵CPU的使用率曲线，就需要使CPU在一段时间内（根据Task Manager的采样率）跑 busy 和 idle 两个不同的循环（loop），从而通过不同的时间比例，来调节 CPU使用率。
Busy loop可以通过执行空循环来实现，idle可以通过Sleep（）来实现。
问题的关键在于如何控制两个loop的时间，我们先试验一下Sleep一段时间，然后循环n次，估算n的值。
那么对于一个空循环for（i=0; i < n; i++）；又该如何来估算这个最合适的n值呢？我们都知道CPU执行的是机器指令，而最接近于机器指令的语言是汇编语言，所以我们可以先把这个空循环简单地写成如下汇编代码（此代码为示意性的伪代码）后再进行分析： next: mov　eax,dword ptr[i]　；将i放入寄存器 add　eax,1 ............

以上为书籍内容预览，如需阅读全文内容请下载EPUB源文件，祝您阅读愉快。