突发：回顾 1994 年微软实习面试编程问题
本周没有 [性能感知编程] 的课程，因为这周是“1994 年暑期实习周”。本周将发布五篇文章，讲述 1994 年申请微软暑期实习面试时被问到的编程问题。正常安排的课程将在下周恢复。
面试背景
很久之前（记得是 1994 年，也可能是 1993 年），参加了微软暑期实习岗位的面试，分别和四个人进行面试，每人问了一道经典的微软面试“编程问题”。那时互联网不发达，没想到会有这样的面试环节，也不知道什么是经典的微软编程问题。而且当时年轻缺乏经验，没人让当场解决编程问题，这是全新体验。虽现在不推荐这种面试提问方式，但当时觉得很有趣，到现在还记得这四道问题。本周想分享这四道问题，谈谈当时和如今的“正确”答案，且会每天发布一道问题的答案，直到全部发布完。
问题 1：矩形复制
面试流程设计是编程问题随面试进行变难，所以第一道问题最简单：编写 C 代码，将一个矩形从一个缓冲区复制到另一个缓冲区。不太记得具体参数，大概如下：
void CopyRect(char *BufferA, int PitchA, char *BufferB, int PitchB, int FromMinX, int FromMinY, int FromMaxX, int FromMaxY, int ToMinX, int ToMinY) { /* 填写代码 */ }即给定缓冲区 A 和 B，缓冲区 A 中的“源”矩形，以及缓冲区 B 中的“目标”位置，编写代码将元素从 A 复制到 B。当时像素通常 8 位，所以元素是 8 位的。这道题对懂 C/C++ 的人较简单，对不熟悉指针操作的人可能有点难，但矩形复制概念较直观，且当时没对性能提具体要求，主要看是否理解这类操作。
问题 2：字符串复制
奇怪的是，第二位面试官问了个非常相似但似乎更简单的问题，这是唯一一道看起来“顺序不对”的题，因为第三道和第四道题难度明显增加。第二道题是字符串复制，一般能写出矩形复制代码的人也能写出字符串复制代码，但面试官有自己考量。具体来说，这些字符串是 ASCII - Z 格式，即每个元素占一个字节，以空字符结尾，大概如下：
void CopyString(char *From, char *To) { /* 填写代码 */ }这道题有很多奇怪的地方，尤其是成功写出代码后，面试官让做的修改。现在回想，在这四次面试中，只有这次怀疑面试官是不是不太懂行，在回答这道题时会详细描述，以现在的经验来看，有些地方确实让人有点摸不着头脑。
问题 3：填充检测
第三道题是四道题中最有趣的，也比前两道题难很多。其实它本身不难，但鉴于当时对这类问题缺乏经验，没能当场解决。不过，这仍是个很棒的小问题。这个问题源于面试官为微软一款产品编写的填充算法实现，忘了是哪款产品，可能是某种 BASIC 语言，是为某款编程语言的图形库设计的，面试官特别提到这个解决方案“让我们在性能上超过了 Borland”。
对于不了解“填充”的人来说，它就像 Photoshop 里的油漆桶工具：给定一张图片和图片中的一个特定 X、Y 坐标，要找到所有颜色相同且相连的像素，并将它们的颜色改为其他颜色。虽然现在人们不太关注这个功能，但在那个时代的业余图形库中，这是个非常常见的操作，早期遇到的很多 BASIC 语言都有填充功能。
对于这道题，没让实现实际的填充算法，而是让实现检测某个字节是否“匹配”特定颜色的代码。通常情况下，这不难，因为如果每个字节代表一个像素，只需要使用等于运算符即可。但这道题的难点在于，它针对的是 [四色 CGA 模式]，其中每个像素只占两位。这意味着每个字节包含四个像素，而不是一个。所以不能简单地进行比较（至少在当时，家用计算机还没有 SIMD 指令）。问题就变成了，如何最有效地检测一个字节中的四个像素是否包含给定的颜色？换句话说：
int ContainsColor(char unsigned Pixel, char unsigned Color) { /* 在此处填写计算结果，真（非零）或假（零） */ }此外，可以随意存储颜色值，所以如果需要预计算，也可以包含在内。这是最喜欢的一道题，尽管当时做不出来。现在回想起来，更喜欢它了，因为这是在没有 SIMD 指令的情况下进行类 SIMD 编程的经典案例，是第一次见到这样的问题，但肯定不是最后一次。
问题 4：绘制圆形轮廓
第四道也是最后一道题有点离谱。让别人编写绘制圆形轮廓的代码本身没问题，但这几乎完全是个“经验”问题。要么已经知道在 20 世纪 90 年代的桌面硬件上使用的算法，要么不知道，不可能当场想出这个算法，因为这个算法的最初发现本身就非常了不起。所以，如果想了解候选人的知识储备，第四道题是个不错的问题，否则，它基本上没什么用。面试时没做出来这道题，因为从未见过这个算法（或类似的算法），最后还是在白板上写出了代码，但大部分时间都需要面试官的指导。问题如下：
void Plot(int X, int Y); /* 此函数已存在 */ void OutlineCircle(int Cx, int Cy, int R) { /* 在此处填写代码，为轮廓上的每个像素调用一次 Plot 函数 */ }所有参数都是整数而不是浮点数，是因为 1994 年，桌面计算机上的浮点数运算速度还不够快，大多数情况下还是首选整数运算，虽然图形处理逐渐向浮点运算发展，但“大多数图形处理使用浮点数”的时代还未到来。
答案及后续安排
以上就是实习面试时被问到的四道问题。接下来的四篇文章中，会给出当时和现在的答案。在阅读之前，也可以自己试试看。当时觉得这些问题很有趣，相信大家也会喜欢。如果是有经验的程序员，应该已经知道如何解决这些问题；如果和作者一样，重新推导后两道题的解法也会很有意思。
读者评论
有读者分享了绘制圆形轮廓和填充检测问题的解法。Joost 分享了绘制圆形轮廓的思路：知道圆上一个点，从该点出发只能移动到三个像素之一，分别计算它们到圆心的距离，选择距离最近的那个；不需要使用平方根，比较平方距离即可；知道当前像素到圆心的距离，移动一个像素后的距离变化可预测。gonutz 分享了填充检测问题的想法：将查找的颜色重复四次放入一个字节，与要检查的字节进行异或运算，检查结果中是否有两个 0；使用 256 项的查找表，也可使用四元素的查找表将颜色转换。
提醒大家关注后续文章，获取这四道编程问题的答案。
