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

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

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

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

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

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

TechLead的问题

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

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

数据建模

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

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

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

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

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

我们不知道的:

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

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

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

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

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

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

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

创建数据模型

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

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

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

  • Color
  • ID
  • X
  • Y

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

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

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

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

Answer: 3

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

Answer: 18

生成节点的代码:

 1const generateNodes = ({
 2  numberOfColumns,
 3  numberOfRows,
 4}) => (
 5  Array(
 6    numberOfColumns
 7    * numberOfRows
 8  )
 9  .fill()
10  .map((
11    item,
12    index,
13  ) => ({
14    colorId: (
15      Math
16      .floor(
17        Math.random() * 3
18      )
19    ),
20    id: index,
21    x: index % numberOfColumns,
22    y: Math.floor(index / numberOfColumns),
23  }))
24)

我们取列和行,从项目数中创建一个一维数组,然后从数据中生成节点。

这里用的不是颜色,而是colorId。。首先,因为随机化更简单。其次,我们通常需要自己查找颜色值。

虽然他从未明确表示,但他只使用了3个颜色值。我也将数据集限制为3种颜色。只要知道它可能有数百种颜色,最终的算法就不需要改变了。

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

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

数据处理

无论我们使用哪种方法,我们都想知道这些节点的邻接关系。X和Y的值不能满足要求。

给定X和Y,我们需要找出相邻的X和Y值。其实很简单。我们只需要在X和Y上找到+ 1和- 1的节点。

我为这段逻辑写了一个辅助函数:

 1const getNodeAtLocation = ({
 2  nodes,
 3  x: requiredX,
 4  y: requiredY,
 5}) => (
 6  (
 7    nodes
 8    .find(({
 9      x,
10      y,
11    }) => (
12      x === requiredX
13      && y === requiredY
14    ))
15    || {}
16  )
17  .id
18)

我们生成节点的方法,实际上有一种数学方法可以算出相邻节点的id。相反,我假设节点会随机进入系统。

我通过第二个步骤运行所有节点以添加相邻:

 1const addAdjacencies = (
 2  nodes,
 3) => (
 4  nodes
 5  .map(({
 6    colorId,
 7    id,
 8    x,
 9    y,
10  }) => ({
11    color: colors[colorId],
12    eastId: (
13      getNodeAtLocation({
14        nodes,
15        x: x + 1,
16        y,
17      })
18    ),
19    id,
20    northId: (
21      getNodeAtLocation({
22        nodes,
23        x,
24        y: y - 1,
25      })
26    ),
27    southId: (
28      getNodeAtLocation({
29        nodes,
30        x,
31        y: y + 1,
32      })
33    ),
34    westId: (
35      getNodeAtLocation({
36        nodes,
37        x: x - 1,
38        y,
39      })
40    ),
41  }))
42  .map(({
43    color,
44    id,
45    eastId,
46    northId,
47    southId,
48    westId,
49  }) => ({
50    adjacentIds: (
51      [
52        eastId,
53        northId,
54        southId,
55        westId,
56      ]
57      .filter((
58        adjacentId,
59      ) => (
60        adjacentId !== undefined
61      ))
62    ),
63    color,
64    id,
65  }))
66)

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

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

在获得基本id之后,我们将它们转换为一个邻接数组,该数组只包含那些具有值的邻接数组。这样,如果我们有角和边,我们就不用担心检查id是否为空。它还允许我们循环一个数组,而不是在算法中手工记录每个基本ID。

下面是另一个2×2示例,使用一组新的节点通过addAdjacencies运行:

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

预处理优化

我想大大简化本文的算法,所以我在另一个优化过程中添加了该算法。该操作删除与当前节点颜色不匹配的相邻id。

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

 1const addAdjacencies = (
 2  nodes,
 3) => (
 4  nodes
 5  .map(({
 6    colorId,
 7    id,
 8    x,
 9    y,
10  }) => ({
11    adjacentIds: (
12      nodes
13      .filter(({
14        x: adjacentX,
15        y: adjacentY,
16      }) => (
17        adjacentX === x + 1
18        && adjacentY === y
19        || (
20          adjacentX === x - 1
21          && adjacentY === y
22        )
23        || (
24          adjacentX === x
25          && adjacentY === y + 1
26        )
27        || (
28          adjacentX === x
29          && adjacentY === y - 1
30        )
31      ))
32      .filter(({
33        colorId: adjacentColorId,
34      }) => (
35        adjacentColorId
36        === colorId
37      ))
38      .map(({
39        id,
40      }) => (
41        id
42      ))
43    ),
44    color: colors[colorId],
45    id,
46  }))
47  .filter(({
48    adjacentIds,
49  }) => (
50    adjacentIds
51    .length > 0
52  ))
53)

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

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

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

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

End

原文发布于微信公众号 - ATYUN订阅号(atyun_com)

原文发表时间:2019-05-13

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券