Interview Question: Structure de données pour un grand réseau social

Question

Une autre question intéressante interview que je suis tombé sur -

la conception des structures de données pour un réseau social très important (Facebook, LinkedIn, etc.)?

En outre, la conception d'un algorithme pour montrer la connexion ou le chemin, entre deux personnes (par exemple moi-> foo-> bar-> rob-> ron)

Answer 1

Je considéreraient probablement un graphe non orienté de quelque variété , probablement stocké comme une matrice d'adjacence éparse. Pour ce qui est de trouver le chemin le plus court entre deux personnes, puisque le coût des arêtes est uniforme, je considérerais aller avec une recherche bidirectionnelle. Fondamentalement, sors en cercles concentriques centrés autour de chaque personne, où chaque cercle est la personne elle-même, puis ses amis, puis ses amis d'amis, etc., à chaque étape de test s'il y a une personne dans les deux cercles Suivez le chemin de la première personne que vous trouvez vers l'intérieur vers le centre de chaque personne, et vous avez trouvé le chemin le plus court.

Vous pouvez essayer d'autres algorithmes de plus court chemin, mais en général, la plupart des algorithmes de plus court chemin ne vous donnent que la distance et non le chemin réel.

Answer 2

Je m'inquiéterais du fait que ce n'est pas possible avec une structure de données - vous pouvez parler de la base de données ici. Très grand est xxx millions (100+), et je ne pense pas que cela peut être traité efficacement en mémoire.

Answer 3

Lorsque nous avons une grande quantité de données, nous ne pouvons pas conserver toutes nos données sur une seule machine. Cela signifie que pour chaque personne, nous devons stocker un identifiant de machine. Nous devons prendre en charge les aspects suivants -

1. Pour chaque ID d'ami: machine_id = lookupMachineForUserID (id);
2. Passez à machine_id
3. friend = lookupFriend (machine_id);

Il peut y avoir beaucoup d'optimisations effectuées ici. L'un d'entre eux consiste à réduire le nombre de sauts d'une machine à l'autre, car cela coûte cher. Nous pouvons le faire en regroupant des personnes appartenant à un même pays/une même ville. Il y a de grandes chances de trouver des amis dans la même ville. De même, il peut y avoir d'autres façons d'optimiser.

Je vais essayer de donner une implémentation très basique de la structure de nos données. Ofcourse en réalité, nous devons tenir compte de beaucoup de facteurs comme si sur des machines tombe en panne, les données de mise en cache, etc.

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(); 
} 

Je vais essayer de poster la solution pour tracer le chemin entre amis plus tard.

Answer 4

Motif composite? Nous n'avons peut-être pas besoin d'arracher tous ses «amis d'amis» pour ainsi dire, à la mémoire.
La conception de table DB est un autre problème

Answer 5

En ce qui concerne l'algorithme:

J'aime @sxeraverx réponse, sauf la partie de la matrice clairsemée. Une liste d'adjoints ou un simple graphique d'objets serait un meilleur choix ici. La matrice doit allouer de la mémoire pour chaque connexion possible qui est O (n^2) où n est le nombre d'utilisateurs.Un graphe de liste ou d'objet n'allouera de la mémoire que sur O (e) où e est le nombre de connexions, ce qui est rare.

J'utiliserais une recherche en profondeur d'abord avec marquage pour trouver l'ami. Marquage des nœuds que vous avez déjà parcouru est essentiel car les cycles d'amis existeront. Avec un DFS, la découverte du chemin est presque triviale car la pile que vous utilisez pour exécuter le DFS est le chemin. Donc, quand vous trouvez l'ami, vous venez de faire apparaître toute la pile et vous avez terminé. Une première recherche de souffle n'a pas cette belle propriété parce que la file d'attente utilisée pour parcourir le graphe aura des noeuds inexplorés, donc vous aurez besoin de garder une trace du chemin en utilisant une autre structure. Une première recherche approfondie pourrait être appropriée si nous nous attendons à ce que la fonction soit exécutée contre des personnes dans le même «voisinage» d'amis et que nous nous soucions vraiment de la performance.

Une autre belle propriété de la DFS est qu'elle peut être parallélisée. Lorsque vous rencontrez un nouveau nœud, vous pouvez créer de nouveaux processus/threads/threads DFS pour traiter les nœuds enfants. Les nouveaux threads doivent pouvoir partager les informations de marquage via un système de messagerie. Cela pourrait être un peu d'optimisation prématurée maintenant que j'y pense un peu plus. Voici un paper sur le sujet au cas où quelqu'un est intéressé

Answer 6

Vous pouvez utiliser une base de données graphique comme neo4j