首页»学习  »   正文

一道Google面试题:如何分解棘手问题(上)

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

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

这段视频让我很兴奋

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

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

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

TechLead的问题

一道Google面试题:如何分解棘手问题(上)

一道Google面试题:如何分解棘手问题(上)

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

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

数据建模

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

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

  • 我们称之为彩色方块或“节点”的概念。
  • 我们的数据集中有10K个节点。
  • 节点被组织成列和行(2D)。
  • 列和行数可能不均匀。
  • 节点有颜色和表示邻接的方法。

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

  • 没有两个节点会重叠。
  • 节点之间永远不会相邻。
  • 一个节点永远不会有重复的邻接。
  • 位于边和角上的节点将分别丢失一个或两个邻接。

我们不知道的:

  • 行与列的比率
  • 可能的颜色数量。
  • 只有一种颜色的概率。
  • 颜色的粗略分布。

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

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

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

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

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

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

创建数据模型

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

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

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

  • Color
  • ID
  • X
  • Y

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

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

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

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

一道Google面试题:如何分解棘手问题(上)

Answer: 3

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

一道Google面试题:如何分解棘手问题(上)

Answer: 18

他是生成节点的代码:

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种颜色。只要知道它可能有数百种颜色,最终的算法就不需要改变了。

作为一个更简单的例子,这里有一个2×2节点列表:

[
  { 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。

下面是另一个2×2示例,使用一组新的节点通过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都是连续的节点。

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

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

欢迎关注ATYUN官方公众号,商务合作及内容投稿请联系邮箱:bd@atyun.com

发表评论