最近我想了解一下别人对软件工程的看法，然后开始在YouTube上疯狂地观看TechLead。在接下来的几天里，我为他在谷歌工作时问的一个面试问题想出了各种各样的解决方案。

[playlist type="video" ids="40203"]

视频（TechLead模拟谷歌面试（软件工程师职位））

这段视频让我很兴奋

TechLead在谷歌的100多次采访中提出了一个问题。我很好奇在RxJS中想出一个解决方案。不过，本文将介绍传统的方法。

他的问题的真正目的是从被采访者那里获得信息。在编码之前他们会问正确的问题吗？解决方案是否符合项目的指导方针？他甚至指出，即使你得到正确的答案，这一点都不重要。他想知道你是怎么想的，你是否能理解这个问题。

他谈到了几个解决方案，一个是递归的(受堆栈大小的限制)，另一个是迭代的(受内存大小的限制)。我们将会对这两个问题进行更多的研究!

TechLead的问题





当我听到他的问题，看到这张照片时，我在想“哦，天哪，我必须做一些二维图像建模来解决这个问题”。在面试中听起来几乎不可能的回答。

但在他进一步解释之后，情况就不一样了。您正在处理已经捕获的数据，而不是解析图像。我现在意识到，这个图像其实是用词不当。

数据建模

在编写任何代码之前，需要定义数据模型。这一点我再怎么强调也不为过。在编写如此高级的代码之前，首先要弄清楚您正在处理什么，并收集业务需求。

在我们的案例中，TechLead为我们定义了很多这样的需求:

• 我们称之为彩色方块或“节点”的概念。


• 我们的数据集中有10K个节点。


• 节点被组织成列和行(2D)。


• 列和行数可能不均匀。


• 节点有颜色和表示邻接的方法。

我们也可以从数据中得到更多的信息:

• 没有两个节点会重叠。


• 节点之间永远不会相邻。


• 一个节点永远不会有重复的邻接。


• 位于边和角上的节点将分别丢失一个或两个邻接。

我们不知道的:

• 行与列的比率


• 可能的颜色数量。


• 只有一种颜色的概率。


• 颜色的粗略分布。

作为开发人员，您的级别越高，您就越需要问这些问题。这也不是经验的问题。虽然这有帮助，但如果你不能找出未知的东西，它不会让你变得更好。

我不指望大多数人能找出这些未知数。直到我开始在脑海中计算这个算法，我也不知道它们的全部。未知的东西需要时间去发现。要找到所有的问题，需要与商界人士进行大量的讨论和反复。

看着他的图像，似乎分布是随机的。他只使用了3种颜色，从来没有说过别的，所以我们也会这么做。我们还假设有可能所有颜色都相同。

因为它可能会破坏我们的算法，所以我假设我们使用的是100x100网格。这样，我们就不用处理奇数行和10K列的情况。

在典型的环境中，我会在数据发现的前几个小时内问所有这些问题。这才是TechLead真正关心的。你是要从编写一个随机的解决方案开始，还是要找出问题所在？

你将在你的数据模型中犯错误。我知道我在第一次写这篇文章的时候就这样做了，但是如果你提前计划的话，这些问题会更容易处理。因此，我最终不得不重写代码的一小部分。

创建数据模型

我们需要知道数据是如何输入的，以及我们希望以何种格式处理它。

由于我们没有适当的系统来处理数据，所以我们需要自己设计一个可视化系统。

我们数据的基本组成部分:

• Color


• ID


• X


• Y

我们为什么需要ID?因为我们可能不止一次地遇到相同的项目。我们想要防止无限循环，所以我们需要标记我们在这些情况下所处的位置。

此外，像这样的数据通常会被分配某种ID、散列或其他值。它是一个唯一的标识符，所以我们有办法识别那个特定的节点。如果我们想知道最大的连续块，我们需要知道该块中有哪些节点。

因为他把数据用网格表示出来，我假设我们会得到X和Y的值。仅使用这些属性，我就能够生成一些HTML，以确保我们生成的内容与他给出的内容类似。

这是用绝对定位完成的，就像他的例子:

[caption id="attachment_40179" align="aligncenter" width="400"] Answer: 3[/caption]

它甚至可以处理更大的数据集：

[caption id="attachment_40180" align="aligncenter" width="880"] Answer: 18[/caption]

他是生成节点的代码:

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。。首先，因为随机化更简单。其次，我们通常需要自己查找颜色值。

虽然他从未明确表示，但他只使用了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和- 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,

  }))

)

 

我们为每组相邻的X和Y值调用getNodeAtLocation，并找到我们的northId、eastId、southId和westId。我们不传递X和Y值，因为它们不再是必需的。我避免在这个预处理器代码中进行任何不必要的优化。它不会影响我们最终的性能统计，只会帮助简化我们的算法。

我继续把colorId变成了一种颜色。这对于我们的算法来说是完全不必要的，但是我想让它更容易可视化。

在获得基本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。

重写了addAdjacements函数后，我们现在得到:

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

  ))

)

在添加更多功能的同时，我减少了addadjacements。

通过删除颜色不匹配的节点，我们的算法可以100%确保Adjacentids属性中的任何ID都是连续的节点。

最后，我删除了所有没有相同颜色相邻的节点。这就更加简化了我们的算法，我们已经将总节点缩减为我们关心的节点。

由于我实在是啰嗦导致这篇文章实在是太长，所以本人决定明天继续更新，明天见~