打赌你无法解决这个Google面试题

英文 |  https://medium.com/free-code-camp/bet-you-cant-solve-this-google-interview-question-4a6e5a4dc8ee

TechLead 的问题

在这个问题中，TechLead 要求我们观察下面的网格，并获取所有颜色相同的最大连续块的数目。

当我听到他的问题并看到图片时，我在想：“天哪，我必须做一些2D图像建模才能弄清楚这一点”，而这在面试中是几乎不可能的。

但是在他进一步解释之后，我发现事实并非如此。我们需要处理的是图像的数据，而不需要解析图像并转化为数据。

数据模型

在编写代码之前，我们需要定义数据模型。

在我们的案例中，TechLead 给了我们这些限制：

• 我们将其称为彩色正方形或“节点”的概念

• 我们的数据集中有1万个节点

• 节点分为列和行（2D）

• 列和行的数量可以不均匀

• 节点具有颜色和某种表示邻接的方式

我们还可以从数据中获取更多信息：

• 没有两个节点会重叠

• 节点永远不会与它们自己相邻

• 节点永远不会有重复的邻接关系

• 位于侧面和角落的节点将分别缺少一两个相邻关系

我们不知道的是：

• 行与列的比例

• 可能的颜色数

• 所有节点只有一种颜色的机会

• 颜色的粗略分布

职级越高，您将要问的问题越多。这也不是经验问题。虽然这样做有帮助，但是如果您不能挑出未知数，也不会使您变得更好。

我并没有指望大多数人都能发现这些未知项。直到我开始研究算法时，我也不全都知道。未知项需要时间才能弄清楚。需要与人进行大量讨论并来回查阅题目。

看他的图像，似乎分布是随机的。他只使用了3种颜色，并且从不说其他任何东西，所以我们也一样。我们还将假设所有颜色都可能相同。

由于它可能会破坏我们的算法，因此我假设我们正在使用 100x100 的网格。这样，我们不必处理1行和 10K 列的极端情况。

在典型的情况下，我会在问题提出的最初几个小时内发现所有这些问题。这就是 TechLead 真正关心的问题。你讲直接开始编码？还是会先分析题目找出问题所在？

创建数据模型

我们数据的基本模块：

• 颜色

• ID

• X

• Y

ID是干什么的？它是每个网格的唯一标志。

由于是在网格中整理数据，因此我假设我们将使用X和Y值描述数据。仅使用这些属性，我就能生成一些HTML，以确保我们生成的内容就像 TechLead 给我们的一样。

我们使用绝对定位来完成：

也适用于更大的数据集：

这里是代码：

const generateNodes = ({numberOfColumns,numberOfRows,
}) => (Array(numberOfColumns* numberOfRows).fill().map((item,index,) => ({colorId: (Math.floor(Math.random() * 3)),id: index,x: index % numberOfColumns,y: Math.floor(index / numberOfColumns),}))
)

我们取出列和行，从项目数量中创建一维数组，然后根据该数据生成节点。

我使用的是 colorId，而不是 color。首先，因为随机化比较容易。其次，我们通常必须自己检查颜色值。

尽管他从未明确声明，但他只使用了3种颜色值。我也将数据集限制为3种颜色。只需知道它可能是数百种颜色，并且最终的算法就无需更改。

举一个简单的例子，这里是2x2节点列表：

[{ colorId: 2, id: 0, x: 0, y: 0 },{ colorId: 1, id: 1, x: 1, y: 0 },{ colorId: 0, id: 2, x: 0, y: 1 },{ colorId: 1, id: 3, x: 1, y: 1 },
]

数据处理

无论我们要使用哪种方法，我们都想知道每个节点的邻接关系。X和Y值不会减少。

因此，给定X和Y，我们需要弄清楚如何找到相邻的X和Y值。这很简单。我们只需在X和Y上找到正负1的节点即可。

我为此逻辑编写了一个辅助函数：

const getNodeAtLocation = ({nodes,x: requiredX,y: requiredY,
}) => ((nodes.find(({x,y,}) => (x === requiredX&& y === requiredY))|| {}).id
)

我们生成节点的方式实际上是一种数学方法，用来找出相邻节点的ID。相反，我假设节点将以随机顺序进入我们的系统。

我通过第二遍运行所有节点以添加邻接关系：

const addAdjacencies = (nodes,
) => (nodes.map(({colorId,id,x,y,}) => ({color: colors[colorId],eastId: (getNodeAtLocation({nodes,x: x + 1,y,})),id,northId: (getNodeAtLocation({nodes,x,y: y - 1,})),southId: (getNodeAtLocation({nodes,x,y: y + 1,})),westId: (getNodeAtLocation({nodes,x: x - 1,y,})),})).map(({color,id,eastId,northId,southId,westId,}) => ({adjacentIds: ([eastId,northId,southId,westId,].filter((adjacentId,) => (adjacentId !== undefined))),color,id,}))
)

我避免在此预处理程序代码中进行任何不必要的优化。它不会影响我们的最终性能数据，只会帮助简化算法。

我继续将 colorId 更改为另一种颜色。对于我们的算法而言，这完全没有必要，但我想使其更易于可视化。

我们为每组相邻的X和Y值调用 getNodeAtLocation并找到我们的northId，eastId，southId和westId。不再传递X和Y值，因为它们不再需要。

在获得基本ID后，我们将其转换为一个仅包含值的ID数组。这样，如果我们有边角，就不必担心检查这些ID是否为空。它还允许我们循环一个数组，而不是手动注释算法中的每个基本ID。

这是另一个2x2的示例，该示例使用通过 addAdjacencies 运行的一组新节点：

[{ adjacentIds: [ 1, 2 ], color: 'red',  id: 0 },{ adjacentIds: [ 3, 0 ], color: 'grey', id: 1 },{ adjacentIds: [ 3, 0 ], color: 'blue', id: 2 },{ adjacentIds: [ 1, 2 ], color: 'blue', id: 3 },
]

处理优化

我想大大简化本文的算法，因此添加了另一个优化过程。这将删除与当前节点颜色不匹配的相邻ID。
重写addAdjacencies函数之后，现在是这样的：

const addAdjacencies = (nodes,
) => (nodes.map(({colorId,id,x,y,}) => ({adjacentIds: (nodes.filter(({x: adjacentX,y: adjacentY,}) => (adjacentX === x + 1&& adjacentY === y|| (adjacentX === x - 1&& adjacentY === y)|| (adjacentX === x&& adjacentY === y + 1)|| (adjacentX === x&& adjacentY === y - 1))).filter(({colorId: adjacentColorId,}) => (adjacentColorId=== colorId)).map(({id,}) => (id))),color: colors[colorId],id,})).filter(({adjacentIds,}) => (adjacentIds.length > 0))
)

我减少了 addAdjacencies 的代码量，同时添加了更多功能。

通过删除颜色不匹配的节点，我们的算法可以100％确保 adjacentIds 中的ID都是连续的节点。

最后，我删除了没有相同颜色邻接关系的所有节点。这进一步简化了我们的算法，并且将总节点缩减为仅关心的节点。

错误的方式—递归

TechLead 表示我们无法递归执行此算法，因为我们遇到了堆栈溢出的情况。

尽管他部分正确，但有几种方法可以缓解此问题。迭代或使用尾递归。我们将以迭代示例为例，但是JavaScript不再具有尾部递归作为本机语言功能。

虽然我们仍然可以在JavaScript中模拟尾部递归，但我们将保持这种简单性，而是创建一个典型的递归函数。

在编写代码之前，我们需要弄清楚我们的算法。对于递归，使用深度优先搜索是有意义的。不必担心知道计算机科学术语。当我向他展示我想出的不同解决方案时，一位同事说过。

算法

我们将从节点开始，并尽我们所能直到到达终点。然后，我们将返回并采用下一个分支路径，直到我们扫描了整个连续块。

这就是其中的一部分。我们还必须跟踪我们去过的地方以及最大的连续街区的长度。

我所做的就是将我们的功能分为两部分。一个将拥有最大的列表和先前扫描的ID，同时至少每个节点循环一次。另一个将从未扫描的根节点开始，然后进行深度优先遍历。

函数长这样：

const getContiguousIds = ({contiguousIds = [],node,nodes,
}) => (node.adjacentIds.reduce((contiguousIds,adjacentId,) => (contiguousIds.includes(adjacentId)? contiguousIds: (getContiguousIds({contiguousIds,node: (nodes.find(({id,}) => (id=== adjacentId))),nodes,}))),(contiguousIds.concat(node.id)),)
)const getLargestContiguousNodes = (nodes,
) => (nodes.reduce((prevState,node,) => {if (prevState.scannedIds.includes(node.id)) {return prevState}const contiguousIds = (getContiguousIds({node,nodes,}))const {largestContiguousIds,scannedIds,} = prevStatereturn {largestContiguousIds: (contiguousIds.length> largestContiguousIds.length? contiguousIds: largestContiguousIds),scannedIds: (scannedIds.concat(contiguousIds)),}},{largestContiguousIds: [],scannedIds: [],},).largestContiguousIds
)

疯了吧？这个代码简直太长了。

接下来我们一步步来缩减代码

递归函数

getContiguousIds 是我们的递归函数，每个节点调用一次。每次都会返回更新的连续节点列表。

此功能只有一个条件：列表中是否已存在我们的节点？如果不是，请再次调用

getContiguousIds。返回时，我们将获得一个更新的连续节点列表，该列表将返回到化简器，并用作下一个相邻ID的状态。

您可能想知道我们在哪里向contiguousIds添加值。当我们将当前节点连接到contiguousIds上时，就会发生这种情况。每次进一步递归时，我们都确保在循环其相邻ID之前将当前节点添加到contiguousId列表中。

始终添加当前节点可确保我们不会无限递归。

循环

此功能的后半部分还将遍历每个节点一次。

我们在递归函数周围使用了reducer。此人检查我们的代码是否已被扫描。如果是这样，请继续循环，直到找到一个尚未存在的节点，或者直到退出循环为止。

如果尚未扫描我们的节点，请调用getContiguousIds并等待完成。这是同步的，但可能需要一些时间。

返回带有contiguousIds的列表后，请对照largestantContiguousIds列表进行检查。如果更大，则存储该值。

同时，我们将这些contiguousId添加到我们的scandIds列表中，以标记我们去过的地方。
当您看到所有布局时，这非常简单。

执行

即使有1万个节点+3种随机颜色，也不会遇到堆栈溢出问题。但如果只有一种颜色，那么将会将遇到堆栈溢出的情况。那是因为我们的递归函数要进行1万次递归。

顺序迭代

由于内存大于函数调用堆栈，因此我的下一个想法是在单个循环中完成整个操作。

我们将跟踪节点列表列表。我们将继续添加它们并将它们链接在一起，直到脱离循环为止。

此方法要求我们将所有可能的节点列表保留在内存中，直到完成循环为止。在递归示例中，我们仅在内存中保留了最大的列表。

const getLargestContiguousNodes = (nodes,
) => (nodes.reduce((contiguousIdsList,{adjacentIds,id,},) => {const linkedContiguousIds = (contiguousIdsList.reduce((linkedContiguousIds,contiguousIds,) => (contiguousIds.has(id)? (linkedContiguousIds.add(contiguousIds)): linkedContiguousIds),new Set(),))return (linkedContiguousIds.size > 0? (contiguousIdsList.filter((contiguousIds,) => (!(linkedContiguousIds.has(contiguousIds)))).concat(Array.from(linkedContiguousIds).reduce((linkedContiguousIds,contiguousIds,) => (new Set([...linkedContiguousIds,...contiguousIds,])),new Set(adjacentIds),))): (contiguousIdsList.concat(new Set([...adjacentIds,id,]))))},[new Set()],).reduce((largestContiguousIds = [],contiguousIds,) => (contiguousIds.size> largestContiguousIds.size? contiguousIds: largestContiguousIds))
)

另一个疯狂的。让我们从顶部开始进行分解。我们将每个节点循环一次。但是现在我们必须检查我们的id是否在节点列表的列表中：contiguousIdsList。

如果它不在任何contiguousId列表中，我们将添加它及其相邻ID。这样，在循环时，其他东西将链接到它。

如果我们的节点在其中一个列表中，则可能其中有很多。我们希望将所有这些链接在一起，并从contiguousIdsList中删除未链接的链接。

而已。

提出节点列表列表后，我们检查最大的节点列表，然后完成。

执行

与递归版本不同，当所有10K项都具有相同的颜色时，该函数确实会完成。

除此之外，它非常慢；比我最初预期的要慢得多。我忘了在效果评估中考虑循环列表列表，这显然会对性能产生影响。

随机迭代

我想将方法学放在递归方法的后面，并迭代地应用它。

我花了一整夜的时间试图记住如何动态更改循环中的索引，然后想起了while（true）。

自从我写了传统的循环已经很久了，我完全忘记了它。

现在我有了武器，我就开始进攻了。由于我花了很多时间试图加快可观察版本的速度（稍后会详细介绍），因此我决定将数据懒散地进行老式修改。

该算法的目标是精确击中每个节点一次，并且仅存储最大的连续块：

const getLargestContiguousNodes = (nodes,
) => {let contiguousIds = []let largestContiguousIds = []let queuedIds = []let remainingNodesIndex = 0let remainingNodes = (nodes.slice())while (remainingNodesIndex < remainingNodes.length) {const [node] = (remainingNodes.splice(remainingNodesIndex,1,))const {adjacentIds,id,} = nodecontiguousIds.push(id)if (adjacentIds.length > 0) {queuedIds.push(...adjacentIds)}if (queuedIds.length > 0) {do {const queuedId = (queuedIds.shift())remainingNodesIndex = (remainingNodes.findIndex(({id,}) => (id === queuedId)))}while (queuedIds.length > 0&& remainingNodesIndex === -1)}if (queuedIds.length === 0&& remainingNodesIndex === -1) {if (contiguousIds.length> largestContiguousIds.length) {largestContiguousIds = contiguousIds}contiguousIds = []remainingNodesIndex = 0if (remainingNodes.length === 0) {break}}}return largestContiguousIds
}module.exports = getLargestContiguousNodesIterative2

即使我像大多数人一样写了这篇文章，但到目前为止，它的可读性最差。我什至无法告诉您这是怎么回事，除非自己先自上而下地进行。

我们没有添加到以前扫描的ID列表中，而是从剩余的Nodes数组中拼接出了值。

懒！我永远不会建议自己这样做，但是我在创建这些样本的最后阶段想尝试一些不同的尝试。

性能对比

随机颜色

单一颜色

本文完~