1994 年微软实习面试四道编程问题大揭秘，你能答对几道？

突发回顾 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 项的查找表也可使用四元素的查找表将颜色转换。提醒大家关注后续文章获取这四道编程问题的答案。