一道Google面试题：如何分解棘手问题（上）
一道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
腾讯云开发者
