Проектировать структуры данных для очень большой социальной сети, такой как Facebook или Linkedln

31.12.2019GBlog

Как бы вы спроектировали структуры данных для очень большой социальной сети, такой как Facebook или Linkedln? Опишите, как бы вы разработали алгоритм, чтобы показать кратчайший путь между двумя людьми (например, Me-> Bob-> Susan-> Jason-> You).

Спросил в: Google Интервью

Хороший способ решить эту проблему — сначала снять некоторые ограничения и решить их для этой ситуации.

Случай 1: упростить проблему (не учитывая миллионы людей)
Мы можем построить график, рассматривая каждого человека как узел и позволяя ребру между двумя узлами указывать, что два пользователя являются друзьями. Если мы хотим найти путь между двумя людьми, мы начинаем с одного человека и делаем простой поиск в ширину . В качестве альтернативы, мы можем выполнить двунаправленный поиск в ширину. Это означает, что нужно выполнить два поиска в ширину, один из источника и один из пункта назначения. Когда поиски сталкиваются, мы знаем, что нашли путь.

Почему поиск в глубину не работает хорошо? Во -первых, поиск в глубину будет просто найти путь. Это не обязательно найти кратчайший путь. Во-вторых, даже если бы мы просто нуждались в каком-либо пути, это было бы очень неэффективно. У двух пользователей может быть только одна степень разделения, но он может искать миллионы узлов в своих «поддеревьях», прежде чем найдет это относительно непосредственное соединение.

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

Основная логика в Java приведена ниже

Linkedlist<Person> findPathBiBFS(HashMap<Integer, Person> people,

int source, int destination)

{

BFSData sourceData = new BFSData(people.get(source));

BFSData destData = new BFSData(people.get(destination));

while (!sourceData.isFinished() && !destData.isFinished())

{

/ * Поиск из источника. * /

Person collision = searchlevel(people, sourceData, destData);

if (collision != null)

return mergePaths(sourceData, destData, collision.getID());

/ * Поиск из пункта назначения. * /

collision = searchlevel(people, destData, sourceData);

if (collision != null)

return mergePaths(sourceData, destData, collision.getID());

}

return null;

}

/ * Поиск на одном уровне и возврат столкновения, если есть. * /
Person searchLevel(HashMap<Integer, Person> people,

BFSData primary, BFSData secondary)

{

/ * Мы хотим искать только один уровень за раз. подсчитывать

сколько узлов в настоящее время

на уровне первичного и делать это только много узлов.

Продолжаем добавлять узлы до конца. * /

int count = primary.toVisit.size();

for (int i= 0; i < count; i++)

{

/ * Вытащить первый узел. * /

PathNode pathNode = primary.toVisit.poll();

int personld = pathNode.getPerson().getID();

/ * Проверьте, был ли он уже посещен. * /

if (secondary.visited.containsKey(personid))

return pathNode.getPerson();

/ * Добавить друзей в очередь. * /

Person person = pathNode. getPerson();

Arraylist<Integer> friends = person.getFriends();

for (int friendid : friends)

{

if (!primary.visited.containsKey(friendid))

{

Person friend= people.get(friendld);

PathNode next = new PathNode(friend, pathNode);

primary.visited.put(friendld, next);

primary.toVisit.add(next);

}

return null;

}

/ * Объединить пути, где встречались поиски в соединении. * /
Linkedlist<Person> mergePaths(BFSData bfsl, BFSData bfs2,

int connection)

{

// endl -> source, end2 -> dest

PathNode endl = bfsl.visited.get(connection);

PathNode end2 = bfs2.visited.get(connection);

Linkedlist<Person> pathOne = endl.collapse(false);

Linkedlist<Person> pathTwo = end2.collapse(true);

pathTwo.removeFirst(); // удалить соединение

pathOne.addAll(pathTwo); // добавить второй путь

return pathOne;

}

class PathNode

{

private Person person = null;

private PathNode previousNode = null;

public PathNode(Person p, PathNode previous)

{

person = p;

previousNode = previous;

}

public Person getPerson()

{

return person;

}

public Linkedlist<Person> collapse(boolean startsWithRoot)

{

Linkedlist<Person> path= new Linkedlist<Person>();

PathNode node = this;

while (node != null)

{

if (startsWithRoot)

path.addlast(node.person);

else

path.addFirst(node.person);

node = node.previousNode;

}

return path;

}

class BFSData

{

public Queue<PathNode> toVisit = new Linkedlist<PathNode>();

public HashMap<Integer, PathNode> visited =

new HashMap<Integer, PathNode>();

public BFSData(Person root)

{

PathNode sourcePath = new PathNode(root, null);

toVisit.add(sourcePath);

visited.put(root.getID(), sourcePath);

}

public boolean isFinished()

{

return toVisit.isEmpty();

}

Как быстро это решение выше BFS?
Предположим, что у каждого человека есть k друзей, а у Source S и Destination D есть общий друг C.

1. Традиционный поиск в ширину от S до D: мы проходим примерно k + k * k узлов: каждый из k друзей S, а затем каждый из их k друзей.

2. Двунаправленный поиск в ширину: мы проходим 2k узлов: каждый из k друзей S и каждый из k друзей D. Конечно, 2k намного меньше, чем k + k * k.

3. Обобщая это к пути длины q, мы имеем это:
3.1 BFS: O (k ^q )
3.2 Двунаправленная BFS: 0 (k ^{q / 2} + k ^{q / 2} ), что равно 0 (k ^{q / 2} )

Если мы представим путь, подобный A-> B-> C-> D-> E, где у каждого человека есть 100 друзей, это большая разница. BFS потребует просмотра 100 миллионов (100 ⁴ ) узлов. Двунаправленная BFS потребует просмотра только 20 000 узлов (2 x 100 ² ).

Случай 2: справиться с миллионами пользователей
Для этих многих пользователей мы не можем хранить все наши данные на одной машине. Это означает, что наша простая структура данных Person сверху не совсем работает — наши друзья могут жить не на той же машине, что и мы. Вместо этого мы можем заменить наш список друзей списком их идентификаторов и перейти следующим образом:

1: для каждого идентификатора друга: int machine index = getMachineIDForUser (person_ID);

2: Перейти к машине #machine_index

3: На этой машине выполните: Person friend = getPersonWithID (person_ID);

Код ниже описывает этот процесс. Мы определили класс Server, который содержит список всех машин, и класс Machine, который представляет одну машину. Оба класса имеют хеш-таблицы для эффективного поиска данных.

Основная логика в Java приведена ниже->

// Сервер, который содержит список всех машин

class Server

{

HashMap<Integer, Machine> machines =

new HashMap<Integer, Machine>();

HashMap<Integer, Integer> personToMachineMap =

new HashMap<Integer, Integer>();

public Machine getMachineWithid(int machineID)

{

return machines.get(machineID);

}

public int getMachineIDForUser(int personID)

{

Integer machineID = personToMachineMap.get(personID);

return machineID == null ? -1 : machineID;

}

public Person getPersonWithID(int personID)

{

Integer machineID = personToMachineMap.get(personID);

if (machineID == null) return null;

Machine machine = getMachineWithid(machineID);

if (machine == null) return null;

return machine.getPersonWithID(personID);

}

// У человека в социальной сети есть идентификатор, друзья и другая информация

class Person

{

private Arraylist<Integer> friends =

new Arraylist<Integer>();

private int personID;

private String info;

public Person(int id)

{

this.personID =id;

}

public String getinfo()

{

return info;

}

public void setinfo(String info)

{

this.info = info;

}

public Arraylist<Integer> getFriends()

{

return friends;

}

public int getID()

{

return personID;

}

public void addFriend(int id)

{

friends.add(id);

}

Ниже приведены некоторые оптимизации и дополнительные вопросы.

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

Оптимизация: умное разделение людей и машин
Люди гораздо чаще дружат с людьми, которые живут в той же стране, что и они. Вместо того, чтобы случайным образом распределять людей по машинам, попробуйте разделить их по странам, городам, штатам и т. Д. Это уменьшит количество прыжков.

Вопрос: Поиск в ширину обычно требует «пометки» узла как посещенного. Как ты это делаешь в этом случае?
Обычно в BFS мы отмечаем узел как посещенный, устанавливая флаг посещения в его классе узла. Здесь мы не хотим этого делать. Возможно одновременное выполнение нескольких поисков, поэтому плохая идея — просто отредактировать наши данные.

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

Другие дополнительные вопросы:
1. В реальном мире серверы выходят из строя. Как это влияет на вас?
2. Как вы можете воспользоваться кешированием?
3. Вы ищете до конца графика (бесконечно)? Как вы решаете, когда сдаться?
4. В реальной жизни некоторые люди имеют больше друзей друзей, чем другие, и поэтому с большей вероятностью проложат путь между вами и кем-то еще. Как вы могли бы использовать эти данные, чтобы выбрать, с чего начать обход?

Ссылка на эту статью
Ссылка на эту статью

Эта статья предоставлена г-ном Сомешем Авастхи . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

Рекомендуемые посты:

Проектировать структуры данных для очень большой социальной сети, такой как Facebook или Linkedln

0.00 (0%) 0 votes