我1994年微软实习面试中的四道编程题（2023）

# 1994年微软实习面试中的四道编程题 来源：https://www.computerenhance.com/p/the-four-programming-questions-from *本周没有性能感知编程（https://www.computerenhance.com/p/table-of-contents）课程，因为本周是Computer, Enhance 的“1994年暑期实习周”！本周将发布五篇文章，讲述我在1994年（可能更早）参加微软暑期实习面试时被问到的编程问题。正常课程下周恢复。* 很久很久*以前*——我记得是1994年，但也可能是1993年——我必须参加微软的暑期实习生面试。我先后与四位面试官交流，每个人都问了我一个经典的微软面试“编程问题”。 当然，当时互联网还不发达，我*完全没想到*会发生这种事。我根本不知道什么是经典的微软编程问题，也不知道面试中会问我这些。 而且，由于当时年轻缺乏经验，我从未被人要求当场解决编程问题。这对我来说是全新的体验。虽然今天我不推荐用这种问题来面试，但我可以告诉你，对于一个十几岁的少年来说，这*极其有趣*。 事实上，有趣到直到今天我*还记得所有四个问题*。 本周，我想和大家分享这四个问题，聊聊当时“正确”的答案，也许还可以进一步探讨，考虑到桌面计算的演进，今天“正确”的答案又是什么。这周每天我会发布一个问题的解答，直到全部完成。 现在，让我们先看看这些问题本身…… 我认为面试过程背后的理念是，随着面试的进行，编程问题会*越来越难*。所以第一个问题是最简单的：编写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++的人来说是这样。对于那些不习惯使用指针的人来说可能有点可怕，但总的来说，矩形复制的概念相当直接。他们也没有要求我做任何关于性能的具体处理，所以这个问题纯粹是为了测试我*是否*理解这类东西。 奇怪的是，第二个面试官问我一个非常相似的问题，但似乎*比*第一个问题*更容易*。这是唯一可能被认为“不合顺序”的问题，因为第三和第四个问题的难度大大增加。 第二个问题是关于*字符串*复制的。一般来说，如果你能写矩形复制，你就能写字符串复制，但我猜他们问这个有他们的理由。 具体来说，字符串是ASCII-Z，即每个字符一个字节，以空字符结尾——大概是这样的： `` void CopyString(char *From, char *To) { /* 在此填写代码 */ } `` 这个问题很奇怪，原因有很多，尤其是当我在（成功）写出代码后，他们要求我进行的修改。现在回想起来，这四个面试中，只有这一次我怀疑面试官是否真的精通他的领域……很难说，但是，正如我将在回答这个问题时更详细地描述的那样，这次面试中有一些事情，凭借我现在拥有的所有经验，我回头反思时会感到有些困惑。 第三个问题无疑是四道题中最有趣的，而且比前两题难得多。它实际上并不*真的*难，但考虑到我当时对这类问题的经验相对不足，我*没能在当场*解决它。不过它仍然是一个非常棒的小问题！ 这个问题源自面试官为微软产品编写的一个泛洪填充算法的实现。我忘了是*哪个*产品，但我想是某种BASIC版本。它是某个*语言产品*的图形库的一部分，因为我记得面试官特别提到这个解决方案“让我们超越了Borland的性能”。 对于那些不知道“泛洪填充”是什么的人来说，它就像Photoshop中的油漆桶工具：给定一张图像和图像中的一个特定X,Y坐标，你希望找到所有相连的该颜色像素，并将它们的颜色*改变*为其他颜色。虽然今天人们不太思考这个功能（例如，你很少看到网上有“如何用OpenGL实现泛洪填充”的文章等），但在那个时代，它是业余图形库中一个*非常常用*的操作。我记得早期我遇到的许多BASIC版本都有泛洪填充功能。 对于这个问题，他们并没有要求我实现真正的泛洪填充。相反，他们要求我实现一段代码来*检测*某个特定字节是否*匹配*某个特定颜色。 通常这不算什么问题，因为如果每个字节代表一个像素，那只是一个等号运算符。但这个问题中的关键在于，这是针对*四色CGA模式*（https://en.wikipedia.org/wiki/Color_Graphics_Adapter），其中每个像素*只占用两位*。 这意味着每个字节包含*四个*像素打包在一起，而不是*一个*。因此你不能仅仅使用简单的比较（至少在当时不行，因为家用电脑上没有SIMD指令）。所以问题变成了：测试一个字节中的*任意*四个像素是否含有给定颜色的最有效方法是什么？ 换句话说： `` int ContainsColor(char unsigned Pixel, char unsigned Color) { /* 在此填写计算真（非零）或假（零）的代码 */ } `` 此外，我可以用任何我想要的方式存储Color——所以如果我需要一些预计算，我可以直接把它硬编码进去。 这是四道题中我最喜欢的一道，尽管我当时没做出来。现在回想起来，它变得*更加*是我的最爱，因为它是一个不使用任何SIMD指令进行SIMD风格编程的经典例子。这是我第一次见到类似的东西，当然，不是最后一次。 第四个也是最后一个问题有点荒谬。虽然让某人编写绘制圆形轮廓的代码本身没有错，但这几乎完全是一个*经验*问题。要么你已经知道在1990年代桌面硬件上用于这类事情的算法，要么你不知道。你没有可能在现场想出来，因为这个算法本身的原始发现*相当惊人*。 所以，如果你想了解候选人阅读量如何，第四个问题是一个好问题。如果不是，它基本上没用。不用说，我在面试中*没有*答出这一题，因为我从未见过这个算法（或类似的东西）。我*最终*还是在白板上写出了代码，但面试官几乎全程手把手指导。 无论如何，问题形式如下： `` void Plot(int X, int Y); /* 假定此函数已存在 */ void OutlineCircle(int Cx, int Cy, int R) { /* 在此填写代码，为轮廓上的每个像素调用一次Plot */ } `` 你可能想知道为什么一切都是整数而不是浮点数。嗯，那是1994年，浮点数*仍然*不够快，在桌面电脑上不能用于大多数事情。大多数情况下，图形仍然偏好整数。当然，情况正在向浮点数发展，但“大多数图形使用浮点数”的时代尚未到来。 这就是我实习面试中被问到的四个问题。我将在接下来的四篇文章中给出我的答案——包括当时和现在的。但在阅读之前，你自己也试试看！当时它们带给我很多乐趣，我想你可能也会喜欢。如果你是有经验的程序员，你已经知道如何完成所有题目；但如果你像我一样，你仍然会享受从头推导最后两题的乐趣！ 当然，如果你还不是Computer Enhance的订阅者，希望订阅免费或付费文章并直接发送到你的邮箱，你可以在这里选择一个订阅级别：