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

web前端开发

共 10860字,需浏览 22分钟

 ·

2020-09-12 05:41

英文 |  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, } = prevState
return { 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 = 0
let remainingNodes = ( nodes .slice() )
while (remainingNodesIndex < remainingNodes.length) { const [node] = ( remainingNodes .splice( remainingNodesIndex, 1, ) )
const { adjacentIds, id, } = node
contiguousIds .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 = 0
if ( remainingNodes .length === 0 ) { break } } }
return largestContiguousIds}
module.exports = getLargestContiguousNodesIterative2

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

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

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

性能对比

随机颜色

耗时方法
229.481msRecursive
272.303msIterative Random
323.011msIterative Sequential
391.582msRedux-Observable Concurrent
686.198msRedux-Observable Random
807.839msRedux-Observable Sequential

单一颜色

耗时方法
1061.028msIterative Random
1462.143msRedux-Observable Random
1840.668msRedux-Observable Sequential
2541.227msIterative Sequential


本文完~


浏览 26
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报