algorithm - 如何将此类 DFS 算法问题扩展/分布到分布式系统中

Question

我正在准备谷歌面试并找到了一些跟进

以下面的问题为例。如果输入尺寸非常大，无法在单台机器上完成怎么办。

我的想法是将它分成许多 block 。然而，困难在于我不知道如何减少/合并答案。

关于这类问题的任何想法或方向。

https://leetcode.com/problems/max-area-of-island/

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Answer 1

假设您有一张非常非常大的 map 。然后你将它分解成矩形 block 并给每个实例一个 block :

• 然后每个实例都会运行类似于您从 LeetCode 链接的内容的解决方案。

• 它会知道它自己的完全包围的岛屿是什么，然后它会知道其中最大的岛屿并将它们报告给排行榜。

• 它将有一个与边相邻的自己的岛的列表，以及邻接索引，这只是四个边中的每一个的一对，或者如果岛不接触该边则为空。基本上这涵盖了有一 block 土地横跨整个实例的情况。

• 它会知道它有哪张 map ，以及在哪里查询其边缘岛屿。它只会说“从这里到这里，我在这个边缘有土地。你呢？”

• 它需要能够将相邻岛屿的列表(大小、索引、其他邻接)返回给另一个实例。

• 它需要查询下一跳实例，直到发现所有多 map 岛。

• 您需要一个将所有结果合并到全局排行榜的特殊实例。

• 为了获得额外的分数，您需要确定两个或多个实例何时对同一个大岛进行计数并删除重复项。也许只是将边缘信息存储在哈希中。