在科技大厂的求职路上，每一场面试都像是一次闯关。特别是对于我们这些身在海外的华人开发者来说，能拿到微软这种级别公司的面试机会，既兴奋又紧张。最近，我就经历了一场微软的远程技术面试，整个过程虽然只有短短一小时，但其中的一道算法题却让我印象极为深刻，今天就想和大家分享一下这段经历和这道有趣的题目，希望能给正在求职路上的你一些启发。

Problem:

Given a 2d array of integers representing a paint canvas where each integer represents a color write a function that takes a point in the array and an integer representing a new color and updates the canvas at that point along with all connected points of the same color with the new color.

Example 1:

Input:

const canvas = [

[1, 2, 0, 1],

[3, 2, 4, 3],

[3, 1, 2, 0],

[1, 0, 0, 4],

]

const row = 1;

const column = 1;

const newColor = 5;

看到这道题，我的心稍微定了一下。这其实是一个非常经典的图像处理问题，通常被称为“泛洪填充” (Flood Fill) 算法。它的核心思想是从一个起始点开始，将所有与之相连的、颜色相同的区域都替换成新的颜色。这本质上是一个图的遍历问题，画布上的每一个像素点都可以看作是图中的一个节点。

我的脑海里立刻浮现出两种主流的解法：深度优先搜索（DFS）和广度优先搜索（BFS）。DFS通常用递归来实现，代码写起来会非常简洁直观：从给定的点开始，检查它的颜色是否是目标颜色，如果是，就改变它，然后对它的上、下、左、右四个相邻且颜色相同的点，递归地调用相同的函数。但这里有一个小小的“陷阱”，如果画布非常大，递归层级太深可能会导致调用栈溢出（stack overflow）。

考虑到这一点，我向面试官阐述了我的想法，并提出使用广度优先搜索（BFS）的迭代方案可能更为稳妥。具体思路是，我们可以使用一个队列（Queue）来辅助。首先将起始点放入队列，然后开始循环，只要队列不为空，就取出一个点。如果这个点的颜色是我们要找的原始颜色，就将它更新为新颜色，并将其所有符合条件的（未访问过、颜色相同、在边界内）邻居点加入队列。这样一层一层地向外扩展，就像水波纹一样，直到所有相连的同色区域都被“染色”。这种方法避免了递归的风险，空间复杂度也相对可控。

面试官听完我的分析后点了点头，示意我可以在编辑器里实现我的想法。在整个编码过程中，他会时不时地针对一些边界条件处理提出问题，比如“如果给定的点就在边界上怎么办？”或者“如果新旧颜色相同，你的程序会如何处理？”。完成代码后，他又追问了算法的时间和空间复杂度。对于一个M×N的画布，这两个复杂度在最坏情况下都是O(M×N)，因为我们可能需要访问每一个像素点。

整个交流过程非常顺畅，面试官更在意的似乎是我解决问题的思路、沟通的清晰度以及代码的健壮性，而非仅仅写出能运行的代码。这次经历让我深刻体会到，微软这样的公司在面试中，极其看重候选人的计算机科学基础知识和逻辑思维能力。他们出的题目可能不是最刁钻的，但一定能考察出你的基本功是否扎实。希望这次的分享能对大家有所帮助，祝各位求职顺利，早日拿到心仪的Offer！

本文的作者 石老师，在这里给大家打个硬广，csoahelp.com每日分享北美大厂面经，小红书也有更新，我们还提供种类多样的收费服务协助您进入北美科技大厂，有意向的微信扫码联系我，或者也可以通过其他方式联系我