Вопрос интервью: структура данных для большой социальной сети

Ответ 1

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

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

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

Ответ 2

Относительно алгоритма:

Мне нравится ответ @sxeraverx, за исключением разреженной части матрицы. Здесь лучше будет отображать список смежности или простой граф объектов. Матрица должна выделять память для каждого возможного соединения, которое является O (n ^ 2), где n - количество пользователей. Граф списка или объекта будет выделять память только на O (e), где e - количество соединений, которое является разреженным.

Я бы использовал поиск глубины с маркировкой, чтобы найти друга. Маркирующие узлы, которые вы уже прошли, очень важны, поскольку существуют циклы друзей. С DFS обнаружение пути почти тривиально, потому что стек, который вы используете для выполнения DFS, - это путь. Поэтому, когда вы найдете друга, вы просто поместите весь стек, и все готово.

Первым поиском для поиска не обладает это приятное свойство, потому что очередь, используемая для перемещения графика, будет иметь неизведанные узлы, поэтому вам нужно будет отслеживать путь, используя какую-либо другую структуру. Первый поиск по ширине может быть уместным, если мы ожидаем, что функция будет запущена против людей в одном "соседстве" друзей и действительно обеспокоена производительностью.

Другим приятным свойством DFS является то, что он может быть распараллелен. Когда вы сталкиваетесь с новым node, вы можете создавать новые процессы/потоки DFS или все, что нужно для обработки дочерних узлов. Новые потоки должны иметь возможность делиться информацией о маркировке с помощью какой-либо системы обмена сообщениями. Теперь это может быть немного преждевременной оптимизацией, что я думаю об этом еще немного. Здесь статья по этому вопросу в случае, если кто-то заинтересован.

Ответ 3

Вы можете использовать базу данных графа, такую ​​как neo4j

Ответ 4

Когда у нас есть большой объем данных, мы не можем хранить все наши данные на одной машине. Это означает, что для каждого человека нам нужно сохранить идентификатор машины. Нам нужно позаботиться о следующих аспектах -

• Для каждого идентификатора друга: machine_id = lookupMachineForUserID (id);
• Перейти к машине machine_id
• friend = lookupFriend (machine_id);

Здесь может быть сделано много оптимизаций. Один из них - уменьшить количество переходов с одной машины на другую, поскольку это дорого. Мы можем сделать это, объединив вместе людей, принадлежащих к одной и той же стране/городу. Есть большие шансы найти друзей в одном городе. Аналогичным образом могут быть другие способы оптимизации.

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

public class Server 
{
 ArrayList<Machine> machines = new ArrayList<Machine>();
}

public class Machine 
{
 public ArrayList<Person> persons = new ArrayList<Person>();
 public int machineID;
}

public class Person 
{
 private ArrayList<Integer> friends;
 private int ID;
 private int machineID;
 private String info;
 private Server server = new Server();
}

Я попытаюсь опубликовать решение для отслеживания пути между друзьями позже.

Ответ 5

Я бы позаботился о том, что с структурой данных это невозможно - вы, возможно, говорите о структуре базы данных здесь. Очень большой ххх миллионов (100+), и я не думаю, что это может быть эффективно рассмотрено в памяти.

Ответ 6

Композитный шаблон? Возможно, нам не придется тянуть всех своих "друзей друзей", так сказать, в память.
Дизайн таблицы БД - это другая проблема.