Как масштабировать / распространять подобные вопросы DFS в распределенной системе

Question

Я готовлю интервью в Google и нашел продолжение

Возьмите, к примеру, приведенный ниже вопрос.Что делать, если размер входного файла действительно большой, что невозможно сделать на одной машине.

Моя идея состоит в том, чтобы разделить его на множество частей.Однако проблема в том, что я понятия не имею, как уменьшить / объединить ответы.

Любая идея или направление такого рода проблем.

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

Предположим, у вас действительно очень большая карта.Затем вы разбили бы его на прямоугольные части и дали бы каждому экземпляру кусок:

• Каждый экземпляр затем выполнял бы что-то похожее на решение, которое вы связали с LeetCode.

• Он будет знать, что это за его собственные полностью окруженные острова, и из этого он узнает самые крупные из них и сообщит о них в таблицу лидеров.

• Этобудет иметь список своих островов, примыкающих к ребру, и индексы смежности, которые представляют собой просто пару для каждого из четырех ребер, или ноль, если остров не касается этого ребра.В основном это относится к случаю, когда есть участок земли, который простирается по всему экземпляру.

• Он бы знал, какая у него карта и где запросить ее краевые острова.Он просто скажет: «У меня есть земля на этом краю, отсюда сюда. Вы?»

• Это должно быть в состоянии вернуть список соседних островов (размер, индексыдругие смежности) к другому экземпляру.

• Потребуется запросить экземпляры следующего перехода, пока не будут обнаружены все острова с несколькими картами.

• Вам понадобится особый экземпляр, который объединит все результаты в глобальную таблицу лидеров.

• Для дополнительного кредита вам необходимо определить, когда два или более экземпляров насчитали один и тот же большой остров, и удалить дубликаты.,Может быть, просто сохранить информацию о ребре в хэше.