一道Google面试题：如何分解棘手问题（下）
一道Google面试题：如何分解棘手问题（下）
在上一篇文章中，我们讲了创建数据模型，数据处理以及预处理优化，今天我们继续接下来的内容。
错误的方法-递归
TechLead说我们不能递归地做这个算法，因为我们会碰到堆栈溢出。
虽然他在一定程度上是正确的，但有几种方法可以缓解这个问题。要么迭代要么使用尾部递归。我们将看到迭代的例子，但是JavaScript不再将尾递归作为一种本地语言特性。
虽然我们仍然可以在JavaScript中模拟尾部递归，但我们将保持这种简单性，并创建一个典型的递归函数。
在编写代码之前，我们需要弄清楚我们的算法。对于递归，使用深度优先搜索是有意义的。不要担心知道计算机科学术语。当我向一位同事展示我想出的不同解决方案时，他这么说。
算法
我们将从一个节点开始，直到到达一个端点为止。然后我们将返回并使用下一个分支路径，直到我们扫描了整个连续块。
这只是其中一部分。我们还必须跟踪我们所处的位置以及最大的连续块的长度。
我所做的是把函数分成两部分。其中一个将保存最大的列表和以前扫描过的id，同时至少循环每个节点一次。另一个将从未扫描的根节点开始，执行深度优先遍历。
这些函数是这样的：
1const getContiguousIds = ({
2 contiguousIds = [],
3 node,
4 nodes,
5}) => (
6 node
7 .adjacentIds
8 .reduce(
9 (
10 contiguousIds,
11 adjacentId,
12 ) => (
13 contiguousIds
14 .includes(adjacentId)
15 ? contiguousIds
16 : (
17 getContiguousIds({
18 contiguousIds,
19 node: (
20 nodes
21 .find(({
22 id,
23 }) => (
24 id
25 === adjacentId
26 ))
27 ),
28 nodes,
29 })
30 )
31 ),
32 (
33 contiguousIds
34 .concat(
35 node
36 .id
37 )
38 ),
39 )
40) 1const getLargestContiguousNodes = (
2 nodes,
3) => (
4 nodes
5 .reduce(
6 (
7 prevState,
8 node,
9 ) => {
10 if (
11 prevState
12 .scannedIds
13 .includes(node.id)
14 ) {
15 return prevState
16 }
17
18 const contiguousIds = (
19 getContiguousIds({
20 node,
21 nodes,
22 })
23 )
24
25 const {
26 largestContiguousIds,
27 scannedIds,
28 } = prevState
29
30 return {
31 largestContiguousIds: (
32 contiguousIds.length
33 > largestContiguousIds.length
34 ? contiguousIds
35 : largestContiguousIds
36 ),
37 scannedIds: (
38 scannedIds
39 .concat(contiguousIds)
40 ),
41 }
42 },
43 {
44 largestContiguousIds: [],
45 scannedIds: [],
46 },
47 )
48 .largestContiguousIds
49)疯了吧？我甚至争论显示代码，因为它变得如此粗糙。
要想减负，让我们一步一步走。
递归函数
getousids是我们的递归函数。对每个节点调用一次。每次它返回时，您都会得到一个更新的连续节点列表。
这个函数中只有一个条件：我们的节点已经在列表中了吗?如果没有，请再次调用getousids。当它返回时，我们将有一个更新的连续节点列表，当它返回时，我们将有一个更新的连续节点列表，该列表将返回到reducer并用作下一个adjacentid的状态。
您可能想知道我们在哪里向continousID添加值。当我们将当前节点连接到连续的ID上时，就会发生这种情况。每次我们进一步重复，我们都要确保在循环其相邻节点之前将当前节点添加到连续ID列表中。
始终添加当前节点可确保不会无限重复。
循环
函数的下半部分也遍历每个节点一次。
我们在递归函数周围有reducer。这个检查我们的代码是否被扫描过。如果是，继续循环，直到找到一个没有循环的节点，或者直到我们退出循环为止。
如果我们的节点没有被扫描，调用getousids并等待它被扫描完。这是同步的，但可能需要一些时间。
当它返回一个邻近列表时，检查那些与最大邻近列表相对的列表。如果较大，则存储该值。
与此同时，我们将把这些相邻的元素添加到scannedIds列表中，以标记我们所处的位置。
当你看到所有的布局时，都很简单。
执行
即使是10K项，它也不会遇到3种随机颜色的堆栈溢出问题。如果我把所有东西都改成单一颜色，我就会遇到堆栈溢出。这是因为我们的递归函数经历了10K次递归。
顺序迭代
由于内存比函数调用堆栈大，我的下一个想法是在一个循环中完成整个操作。
我们将跟踪节点列表。我们将不断地添加它们并将它们连接在一起，直到我们退出循环。
这个方法要求我们将所有可能的节点列表保存在内存中，直到完成循环为止。在递归示例中，我们只保留内存中最大的列表。
1const getLargestContiguousNodes = (
2 nodes,
3) => (
4 nodes
5 .reduce(
6 (
7 contiguousIdsList,
8 {
9 adjacentIds,
10 id,
11 },
12 ) => {
13 const linkedContiguousIds = (
14 contiguousIdsList
15 .reduce(
16 (
17 linkedContiguousIds,
18 contiguousIds,
19 ) => (
20 contiguousIds
21 .has(id)
22 ? (
23 linkedContiguousIds
24 .add(contiguousIds)
25 )
26 : linkedContiguousIds
27 ),
28 new Set(),
29 )
30 )
31
32 return (
33 linkedContiguousIds
34 .size > 0
35 ? (
36 contiguousIdsList
37 .filter((
38 contiguousIds,
39 ) => (
40 !(
41 linkedContiguousIds
42 .has(contiguousIds)
43 )
44 ))
45 .concat(
46 Array
47 .from(linkedContiguousIds)
48 .reduce(
49 (
50 linkedContiguousIds,
51 contiguousIds,
52 ) => (
53 new Set([
54 ...linkedContiguousIds,
55 ...contiguousIds,
56 ])
57 ),
58 new Set(adjacentIds),
59 )
60 )
61 )
62 : (
63 contiguousIdsList
64 .concat(
65 new Set([
66 ...adjacentIds,
67 id,
68 ])
69 )
70 )
71 )
72 },
73 [new Set()],
74 )
75 .reduce((
76 largestContiguousIds = [],
77 contiguousIds,
78 ) => (
79 contiguousIds.size
80 > largestContiguousIds.size
81 ? contiguousIds
82 : largestContiguousIds
83 ))
84)又一段令人疯狂的操作。让我们从上面把这个分解。我们将每个节点循环一次。但是现在我们必须检查我们的ID是否在节点列表中：ousidslist。
如果它不在任何相邻的ID列表中，我们将添加它及其相邻的ID。这样，在循环的时候，其他东西会链接到它。
如果我们的节点在其中一个列表中，那么它可能在其中相当多的列表中。我们希望将所有这些链接在一起，并从连续列表中删除未链接的列表。
就是这样。
在我们列出节点列表之后，我们检查哪个是最大的，然后我们就完成了。
执行
与递归版本不同，当所有的10K项都是相同的颜色时，此版本完成。
除此之外，它相当慢；比我原先预期的慢得多。我忘了解释在我的性能评估中循环列表的原因，这显然对性能有影响。
随机迭代
我想在递归方法之后采用方法论，并迭代地应用它。
我花了一个晚上的大部分时间试图记住如何动态地更改循环中的索引，然后记得while（true）。自从我写了传统的循环以来，我已经完全忘记它了。
既然我有了武器，我就准备进攻。由于我花了很多时间试图加速可观察到的版本（稍后将详细介绍），我决定采用惰性方法，对数据进行修改。
该算法的目标是精确命中每个节点一次，并且只存储最大的连续块：
1const getLargestContiguousNodes = (
2 nodes,
3) => {
4 let contiguousIds = []
5 let largestContiguousIds = []
6 let queuedIds = []
7 let remainingNodesIndex = 0
8
9 let remainingNodes = (
10 nodes
11 .slice()
12 )
13
14 while (remainingNodesIndex < remainingNodes.length) {
15 const [node] = (
16 remainingNodes
17 .splice(
18 remainingNodesIndex,
19 1,
20 )
21 )
22
23 const {
24 adjacentIds,
25 id,
26 } = node
27
28 contiguousIds
29 .push(id)
30
31 if (
32 adjacentIds
33 .length > 0
34 ) {
35 queuedIds
36 .push(...adjacentIds)
37 }
38
39 if (
40 queuedIds
41 .length > 0
42 ) {
43 do {
44 const queuedId = (
45 queuedIds
46 .shift()
47 )
48
49 remainingNodesIndex = (
50 remainingNodes
51 .findIndex(({
52 id,
53 }) => (
54 id === queuedId
55 ))
56 )
57 }
58 while (
59 queuedIds.length > 0
60 && remainingNodesIndex === -1
61 )
62 }
63
64 if (
65 queuedIds.length === 0
66 && remainingNodesIndex === -1
67 ) {
68 if (
69 contiguousIds.length
70 > largestContiguousIds.length
71 ) {
72 largestContiguousIds = contiguousIds
73 }
74
75 contiguousIds = []
76 remainingNodesIndex = 0
77
78 if (
79 remainingNodes
80 .length === 0
81 ) {
82 break
83 }
84 }
85 }
86
87 return largestContiguousIds
88}
89
90module.exports = getLargestContiguousNodesIterative2尽管我像大多数人一样写这篇文章，但它是迄今为止可读性最低的。我甚至不能告诉你，甚至我自己都不确定从头到尾它会发生什么。
我们没有添加到以前扫描的ID列表中，而是从remainingnodes数组中拼接出值。
太懒惰！我从来都不建议你这样做，但是创建这些示例时我已经到了山穷水尽的地步，我想尝试一些不同的方法。
分解
我把它分成3个部分，用if块隔开。
让我们从中间部分开始。我们正在检查队列。如果有的话，我们会对排队的项目进行另一个循环，看看它们是否在我们的剩余节点中。
在第三部分中，这取决于第二部分的结果。如果我们没有任何队列，而still ingnodesindex是-1，那么我们就完成了这个节点列表，我们需要从一个新的根节点开始。新的根节点总是索引为0，因为我们要剪接剩下的节点。
回到循环的顶端，我本可以使用while（true），但我想要一个防止出现问题的方法，这在调试时很有用，因为无限循环是一件很麻烦的事情。
在那之后，我们将拼接节点。我们将它添加到连续ID列表中，并将相邻ID添加到队列中。
执行
这最终几乎和递归版本一样快。当所有节点都是相同颜色时，它是所有算法中速度最快的。
数据特有的优化
对相似颜色分组
因为我们知道只有蓝色和蓝色匹配，所以我们可以将相似颜色的节点组合在一起，形成顺序迭代版本。
将它拆分为3个较小的数组，可以减少内存占用以及在列表中需要执行的循环量。不过，这并不能解决所有颜色都相同的情况，因此这不会修复递归版本。
这也意味着我们可以多线程操作，将执行时间缩短近三分之一。
如果我们按顺序执行这些命令，我们只需要运行前三个命令中最大的一个。如果最大值大于其他两个，则不需要检查它们。
最大可能尺寸
我们可以检查每个迭代，而不是在特定的时间间隔检查是否有最大的列表。
如果最大集合大于或等于可用节点的一半（5K或更高），那么很明显我们已经有了最大节点。
使用随机迭代版本，我们可以找到迄今为止最大的列表大小，并查看还有多少节点。如果有小于最大的，我们已经得到最大的。
使用递归
虽然递归有其局限性，但我们仍然可以使用它。我们要做的就是检查剩余节点的数量。如果它在堆栈限制下，我们可以切换到更快的递归版本。虽然风险很大，但随着循环的深入，它肯定会提高执行时间。
使用“for”循环
因为我们知道最大项目数，所以将reduce函数切换到传统的for循环会有一点好处。
不管什么原因，数组。与for循环相比，原型方法的速度慢得令人难以置信。
使用尾部递归
同样，在这篇特别的文章中，我没有讨论可观察到的版本，我认为递归需要一篇自己的文章。
这是一个有很多要解释的大主题，但是尽管它允许递归版本运行，但最终可能不会像您预期的那样比while循环更快。
RxJS：可维护性vs性能
有一些方法可以重写这些函数，这样您可以更轻松地理解和维护它们。我提出的主要解决方案是在Redux Observable样式中使用RxJS，但不使用Redux。
这实际上是我对这篇文章的挑战。我想用常规的方式编写代码，然后使用RxJS流式传输数据，以了解我可以将其推进到什么程度。
我在RxJS中创建了3个版本，并利用一些自由来加快执行时间。与我的传感器文章不同的是，这三篇文章的结尾都比较慢，即使我增加了行和列。
那一周我花了一个晚上的时间来寻找可能的解决方案，并梳理每一寸代码。我甚至会躺在地上，闭上眼睛，思考思考。每次，我都会想出更好的想法，但一直遇到JavaScript速度限制。
我本来可以做的优化有一个完整的列表，但是以代码可读性为代价。我不想要那样（反正还是用过）。
我终于得到了一个可观察的解决方案，现在是一半时间内运行最快的。这是总体上最好的改进。
只有当每个节点都是相同的颜色时，我才能用observables击败内存密集型的顺序迭代。那是唯一的一次。从技术上讲，这也胜过递归方法，因为在那个场景中堆栈溢出。
在研究了如何使用RxJS流数据之后，我意识到这对于本文来说太难了。希望以后的文章详细讨论这些代码示例。
最后的统计数据
通常，最大的连续块平均在30-80个节点之间。
这些是我的数据：
无论我运行了多少次测试，每个方法的相对位置都是相同的。
当所有节点颜色相同时，采用Redux-Observable并行方法就会受到影响。我试了很多方法使它更快，但都没有奏效。
游戏开发
在我的职业生涯中，我曾两次遇到这种代码。它在Lua的规模要小得多，并且是在我开发独立游戏《Pulsen》时发生的。
有一次，我正在绘制一张世界地图。它有一个预定义的节点列表，我实时处理这个列表。这使得你可以通过点击(左)、(右)、(上)和(下)键在世界地图上移动，即使角度略有偏差。
我还为具有X和Y值的未知项列表编写了一个节点生成器。听起来是不是很熟悉?我还必须把屏幕上的网格居中。但是在HTML中比在游戏引擎中更容易做到这一点。尽管如此，集中一群绝对定位的div也不容易。
在这两种解决方案中，实时执行时间并不是很重要，因为我在加载游戏时做了很多预处理。
我想强调的是，TechLead的问题可能是你在职业生涯中遇到的；也许是这样，但是在典型的JavaScript应用程序中，速度从来都不是一个因素，这非常罕见。
根据TechLeads的其他视频，他在谷歌使用Java。我猜他面试的职位都很在意执行速度。他们可能有一堆处理大量数据的工作任务，所以可能需要这样的解决方案。
但是，那可能是一份关于HTML和CSS的工作，他只是在戏弄被采访者，谁知道呢！
结论
正如您在最后的统计数据中所看到的，外观最差的代码几乎是最快的，并且完成了我们所有的需求。祝你好运！
根据我自己的经验，我花了更长的时间开发非RxJS版本。我认为这是因为更快的版本需要整体思考。Redux-Observable允许您以小块的方式思考。
这是一个非常有趣又令人沮丧的问题。起初，这似乎很难，但在把它拆成碎片后，碎片都拼到了一起：)