1994年微软实习生面试中的四个经典编程问题（2023年回顾）

背景

这篇文章源自 Hacker News 社区讨论，作者回顾了他在 1994 年（或可能为 1993 年）申请微软（Microsoft）暑期实习职位时的面试经历。当时互联网尚未普及，作者对“微软式面试”毫无概念，更不知道面试官会要求现场编写代码。

作为一名年轻且缺乏经验的求职者，作者首次面临这种即席编程挑战。尽管这种面试形式在当今看来并不推荐，但对于当时的青少年而言，这却是一次充满乐趣的经历。由于记忆深刻，作者至今仍清晰记得面试中的四个经典编程问题。

本文是“Computer, Enhance!”系列中关于“性能感知编程”（Performance-Aware Programming）的特别周更内容。作者计划在一周内每天分享一个问题的答案，并探讨在当时以及当今桌面计算环境演进背景下，这些问题的“正确”解法。

核心内容

作者详细描述了面试中遇到的四个编程问题，这些问题按照难度递增的顺序排列，旨在考察候选人对底层数据结构、指针操作以及特定硬件架构下算法效率的理解。

问题一：矩形复制（Rectangle Copy）

这是面试中的第一个问题，也是相对最简单的一个。面试官要求用 C 语言编写代码，将一个缓冲区（Buffer A）中的矩形区域复制到另一个缓冲区（Buffer B）。

函数签名大致如下：

void CopyRect(char *BufferA, int PitchA, char *BufferB, int PitchB,
              int FromMinX, int FromMinY, int FromMaxX, int FromMaxY,
              int ToMinX, int ToMinY)

技术细节：

• 参数含义：BufferA 和 BufferB 是源和目标缓冲区；PitchA 和 PitchB 是步幅（即每行数据的字节数，通常包含填充字节）；其余参数定义了源矩形和目标位置的坐标。
• 数据格式：当时像素通常为 8 位，因此元素被视为 8 位数据。
• 考察点：主要考察候选人对 C/C++ 指针操作、内存布局以及矩形拷贝逻辑的基本理解。面试官并未特别要求优化性能，重点在于确认候选人是否具备处理此类底层数据操作的能力。

问题二：字符串复制（String Copy）

第二位面试官提出了一个看似更简单、实则有些“反常”的问题：复制一个以 null 结尾的 ASCII 字符串。

函数签名如下：

void CopyString(char *From, char *To)

技术细节：

• 数据格式：ASCII-Z 字符串，即每个元素占一个字节，以空字符（null-terminated）结尾。
• 反常之处：作者指出，这个问题在四个面试问题中显得有些“不合逻辑”。虽然能写矩形复制的人通常也能写字符串复制，但面试官在作者成功写出代码后，还要求他对代码进行修改。
• 作者反思：回顾起来，作者怀疑这位面试官可能并不完全精通技术细节，或者其考察意图晦涩难懂。这是四个面试中唯一让作者事后感到困惑的一个环节。

问题三：洪水填充检测（Flood Fill Detection）

这是作者认为最有趣、也最具挑战性的问题，源自微软某产品（可能是某种 BASIC 语言图形库）中的洪水填充（Flood Fill）算法实现。面试官声称该解决方案“在性能上击败了 Borland”。

问题背景： 洪水填充类似于 Photoshop 中的油漆桶工具：给定图像和坐标，找到所有同色连通像素并改变其颜色。在早期的爱好者图形库和 BASIC 语言中，这是一个非常常见的操作。

具体任务： 面试官并未要求实现完整的洪水填充，而是要求实现一个检测函数：判断一个字节中的像素是否包含特定颜色。

int ContainsColor(char unsigned Pixel, char unsigned Color)

技术难点：

• CGA 模式限制：问题设定在四色 CGA（Color Graphics Adapter）模式下。在这种模式下，每个像素仅占 2 位，因此一个字节（8 位）包含四个像素，而非一个。
• 无 SIMD 指令：当时的家用计算机没有 SIMD（单指令多数据）指令集，因此不能直接使用简单的比较运算符。
• 核心挑战：如何最高效地检测一个字节中是否有任何一个 2 位的像素匹配给定的颜色？作者允许对 Color 参数进行预处理（预计算），以优化运行时效率。
• 作者评价：这是作者最喜欢的一个问题，尽管当时未能当场解决。它被视为一种“无 SIMD 指令的 SIMD 风格编程”的经典案例，展示了在硬件限制下通过位运算优化性能的极致技巧。

问题四：绘制圆形轮廓（Outlining A Circle）

最后一个问题被作者形容为“有些荒谬”。面试官要求编写代码，调用已有的 Plot 函数来绘制一个圆的轮廓。

void Plot(int X, int Y); /* 已存在 */
void OutlineCircle(int Cx, int Cy, int R)

技术细节：

• 考察性质：这几乎完全是一个经验性问题。候选人要么知道适用于 1990 年代桌面硬件的经典算法（如中点圆算法或 Bresenham 算法），要么不知道。
• 现场表现：由于该算法的发现过程本身非常精妙，作者在现场无法凭空推导出来，最终在面试官的引导下才在白板上写出了代码。
• 作者评价：如果目的是考察候选人的阅读量或知识储备，这是一个好问题；否则，它几乎毫无用处。

关键要点

• 面试风格的演变：1994 年的微软面试强调现场即时编程，这种形式在当时被视为新奇且有趣，但在现代软件工程实践中已不再被广泛推荐。
• 性能意识的萌芽：尽管问题一和二看似基础，但问题三明确指向了性能优化。作者指出，至少有两个问题（问题三和问题四隐含的算法效率）专门针对性能考量。
• 硬件限制驱动的创新：问题三展示了在缺乏现代硬件特性（如 SIMD 指令）的情况下，如何通过位操作和预计算来实现高效的并行数据处理。这是早期图形编程中的典型优化手段。
• 算法知识的重要性：问题四表明，在某些领域，熟悉经典算法和图形学基础比现场推导更重要，因为许多基础算法是经过长期优化和验证的。
• 面试者的专业性参差不齐：作者提到，问题二的面试官在后续修改要求上显得模糊不清，这暗示了即使是大型科技公司，面试者的专业水平也可能存在差异。

意义与影响

这篇文章不仅是一次怀旧回顾，更是对早期计算机图形学和系统编程教育的一次深度解读。

1. 底层编程价值的重申：在高级语言和框架盛行的今天，回顾这些基于指针、内存布局和位运算的问题，提醒开发者理解底层机制的重要性。特别是在图形处理、游戏引擎和高性能计算领域，这种“性能感知”的思维依然不可或缺。
2. SIMD 编程的前身：问题三中的解决方案可以看作是现代 SIMD 编程思想的雏形。它展示了如何在软件层面模拟硬件并行性，这对于理解现代 CPU 指令集优化（如 SSE, AVX）具有启发意义。
3. 面试文化的反思：作者对四种不同风格问题的分析，为现代技术面试提供了参考。它表明，好的面试问题应当既能考察基础知识，又能揭示候选人在资源受限环境下的问题解决能力和创造力，而不仅仅是背诵算法。
4. 历史技术的传承：通过回顾 1990 年代的 CGA 模式和 BASIC 图形库，文章连接了计算机发展的历史脉络，展示了技术是如何从简单的位操作演进为复杂的抽象层的。

总之，这篇回顾文章通过四个具体的编程问题，生动地展现了 90 年代中期微软对工程师在逻辑思维能力、底层操作技能以及性能优化意识方面的严格要求，同时也为现代开发者提供了关于基础计算机科学原理的宝贵视角。