Question d'entrevue: structure de Données pour un grand réseau social

Concernant l'algorithme:

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

Je voudrais utiliser une profondeur d'abord de recherche avec marquage à trouver l'ami. Marquage des Nœuds que vous avez déjà parcouru est essentiel car les cycles d'amis. Avec un DFS de la constatation de la trajectoire est presque trivial parce que la pile que vous utilisez pour exécuter le DFS est le chemin. Ainsi, lorsque vous trouvez l'ami, vous venez de pop de l'ensemble de la pile et vous avez terminé.

Un souffle de recherche ne dispose pas de cette belle propriété, parce que la file d'attente utilisée pour parcourir le graphe ont inexploré nœuds, de sorte que vous aurez besoin de garder une trace de l'emplacement à l'aide d'une autre structure. Une largeur de recherche pourrait être approprié si nous nous attendons à ce que la fonction à exécuter à l'encontre des personnes dans la même "quartier" d'amis et sont vraiment préoccupés par la performance.

Une autre belle propriété de la DFS est qu'il peut être parallélisé. Lors de la rencontre d'un nouveau nœud, on peut créer frayer de nouvelles DFS processus/threads/whatever pour traiter les nœuds enfants. Les nouvelles discussions doivent être en mesure de partager les informations de marquage par une sorte de système de messagerie. Cela peut être un peu de l'optimisation prématurée maintenant que j'y pense un peu plus. Voici un papier sur le sujet au cas où quelqu'un est intéressé

OriginalL'auteur StevenWilkins

Lorsque nous avons une grande quantité de données, il nous est impossible de garder l'ensemble de nos données sur une seule machine. Cela signifie que pour chaque personne qu'il nous faut pour stocker l'id d'un ordinateur. Nous avons besoin de prendre soin des aspects suivants -

1. Pour chaque ami ID: machine_id = lookupMachineForUserID(id);
2. Aller à la machine machine_id
3. ami = lookupFriend(machine_id);

Il peut y avoir beaucoup d'optimisations fait ici. L'un d'eux est de réduire le nombre de sauts à partir d'une machine à l'autre, parce que c'est cher. Nous pouvons le faire par le groupement de personnes appartenant au même pays/ville ensemble. Il y a de fortes chances de trouver des amis dans la même ville. De même, il ne peut y avoir d'autres moyens pour optimiser.

Je vais essayer de vous donner une base de mise en œuvre de la façon dont nos structures de données. Bien sûr, dans la réalité, nous devons tenir compte de beaucoup de facteurs tels que si sur des machines tombe en panne, la mise en cache des données, 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.

OriginalL'auteur Tushar Gupta

Composite Modèle? On peut ne pas avoir besoin de tirer de toutes ses "amis d'amis" pour ainsi dire, à la mémoire.

La table DB design est un problème différent

OriginalL'auteur riderchap