译者 | 清儿爸
出品 | AI科技大本营（ID：rgznai100）
为了更了解其他人对软件工程的看法，我开始疯狂在 YouTube 上追 TechLead 的视频。在接下来的几天里，我为他在 Google 工作时提出的一道面试题想出了各种解决方案。
通过 TechLead 模拟 Google 面试（软件工程师职位）
他问这个问题的真正目的是从应聘者得到下列信息：在编码之前，他们会问正确的问题吗出的解决方案是否符合项目指南甚至指出，是否得到正确的答案一点都不重要，重要的是应聘者的思考方式，以及应聘者是否能够理解这个问题。
TechLead 的问题
在 TechLead 的问题中，他要求应聘者在如下 格中，计算出所有颜色相同的最大连续块的数量。
当看到这个问题时，我的第一反应是，必须做一些 2D 图像建模才能解决这个问题。听起来这道题在面试中几乎不可能回答出来。
但在听完他的详细解释之后，我方知情况并非如此。在这个问题中，我们需要处理的是已经捕获的数据，而不是解析图像。
数据建模
在编写任何代码之前都需要定义数据模型。对于任何问题，首先要弄清楚我们在处理什么，并收集业务需求。
在我们案例中，TechLead 为我们定义了许多具体的需求，例如：
-
彩色方块或“节点”的概念
-
数据集中包含 1 万个节点
-
节点被组织成行和列，即二维数据
-
列数和行数可能不同
-
节点有颜色信息，并具有对“邻接”这一概念的表示方式
我们还可以从数据中获得更多信息：
-
节点不会重叠
-
节点不会和其自身邻接
-
节点不会有重复的邻接
-
位于边角的节点会比其他节点少一个或两个邻接
还有一些未知信息，例如：
-
行数与列数的比
-
可能的颜色数量
-
只有一种颜色的可能性
-
颜色的大致分布
开发人员的水平越高，其需要问的问题越多。虽然这有所帮助，但如果不能找出未知信息，问题的实际解决还是会存在阻碍。
大部分人并不会想到询问这些未知信息。在开始研究这个算法之前，我也不知道这些未知信息是什么。要找到所有的未知信息，需要与业务人员进行反复的讨论才行。
对于 TechLead 的这张照片来说，颜色的分布似乎是随机的。他只用了三种颜色，并且没有提到其他限制，因此我们暂时也做这种假设。另外我们还假设，这些颜色可能是相同的。
为了保证算法的有效性，因此我假设我们使用的是 100×100 的 格，以避免处理1行10000列这样的极端情况。
在一般情况下，我会在查看数据的最初几个小时内询问所有这些问题。这也是 TechLead 真正关心之处。应聘者需要思考，是要从编写一个随机解决方案开始，还是要首先找出问题所在。如果提前计划的话，这些问题将更容易处理。在解决这些问题之后，我们最终只需重写代码的一小部分即可。
创建数据模型
我们需要知道数据是如何输入的，以及我们希望以何种形式来处理这些数据。由于没有处理数据的系统，因此我们需要自己设计一个可视化的方法。
数据的基本结构如下：
-
Color
-
ID
-
X
-
Y
需要 ID 的原因在于，我们可能不止一次碰到同一个图片格。要想防止无限循环的话，就必须标记在这些情况下该图片格所处的位置。
此外，像这样的数据通常会分配某些 ID、哈希值或其他值。它是一个唯一的标识符，因此，我们可以通过某种方式来标识特定的节点。如果我们想知道最大的连续块，就需要知道该块中有哪些节点。
由于 TechLead 使用 格对数据进标识，我假设我们会得到 X 和 Y 的值。依靠这些属性，我就能够生成一些 HTML，并确保生成的内容与他给我们的内容相类似。
这是使用绝对定位来完成的，就像他的例子一样：
答案：3
这种方法也可以处理更大一些的数据集，如下图：
答案：18
下面是生成节点的代码：
我们使用行列信息创建一个一维数组，然后根据这些数据生成节点。
我用的是 colorId 而不是 color 。这样做有两个原因，一是随机化更为简洁，二是我们通常必须自己查找颜色值。
虽然 TechLead 没有明确说明，但该题目只用了 3 个颜色值，因此，我将数据集限制为 3 种颜色。我们只需知道它可能有数百种颜色，最终的算法就不需要改变了。
下面是一个更简单的例子，这是一个 2×2 的节点列表：
数据处理
我们希望知道每个节点的邻接关系，但仅靠 X 和 Y 的值无法做到。所以，给定 X 和 Y，我们还需要找出如何找出相邻的 X 和 Y 值。其实很简单，我们只需在 X 和 Y 上找到 +1 和 -1 的节点即可。
我为此写了一个函数：
我们用来生成节点的方式，实际上是一种计算相邻节点 ID 的数学方法。而在这一步中，我将采取一个与之相反的思路，即假设节点将以随机顺序输入。
我通过再次遍历所有节点来添加邻接关系：
声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！