Pregunta De la Entrevista: Estructura de datos para una gran red social

Question

Otra cuestión interesante entrevista que me topé -

diseño de las estructuras de datos para una gran red social (Facebook, LinkedIn, etc.)?

Además, el diseño de un algoritmo para mostrar la conexión, o la ruta, entre dos personas (por ejemplo, me-> foo> bar-> rob-> ron)

Answer 1

yo probablemente considerar un grafo no dirigido de alguna variedad , probablemente almacenado como una matriz de adyacencia escasa. En cuanto a encontrar el camino más corto entre dos personas, ya que el costo de los bordes es uniforme, consideraría ir con una búsqueda bidireccional.

Básicamente, salga en círculos concéntricos centrados alrededor de cada persona, donde cada círculo es la persona misma, luego sus amigos, luego sus amigos de amigos, etc., en cada paso probando si hay alguna persona en ambos círculos. Sigue el camino de la primera persona que encuentres hacia adentro, hacia el centro de cada persona, y encontrarás el camino más corto.

Puede probar otros algoritmos de ruta más corta, pero en general, la mayoría de los algoritmos de ruta más corta solo le dan la distancia y no la ruta real.

Answer 2

Me preocuparía que no sea posible con una estructura de datos; posiblemente hable de la base de datos aquí. Muy grande es xxx millón (más de 100), y no creo que esto pueda tratarse eficientemente en la memoria.

Answer 3

Cuando tenemos una gran cantidad de datos, no podemos mantener todos nuestros datos en una sola máquina. Eso significa que para cada persona necesitamos almacenar una identificación de la máquina. Tenemos que cuidar de los siguientes aspectos -

1. por cada amigo ID: machine_id = lookupMachineForUserID (id);
2. Ir a la máquina machine_id
3. friend = lookupFriend (machine_id);

Aquí se pueden realizar muchas optimizaciones. Una de ellas es reducir el número de saltos de una máquina a otra, ya que es caro. Podemos hacerlo agrupando personas que pertenecen al mismo país/ciudad juntas. Hay altas posibilidades de encontrar amigos en la misma ciudad. Del mismo modo, puede haber otras formas de optimizar.

Trataré de dar una implementación muy básica de cómo se verán nuestras estructuras de datos. Por supuesto, en realidad, tenemos que considerar muchos factores, como qué pasaría si en una de las máquinas se cae, los datos de almacenamiento en caché, 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(); 
} 

voy a tratar de publicar la solución a trazar el camino entre amigos después.

Answer 4

¿Patrón compuesto? Es posible que no necesitemos llevar a todos sus "amigos de amigos", por así decirlo, a la memoria.
El diseño de la tabla DB es un problema diferente

Answer 5

En cuanto al algoritmo:

me gusta @sxeraverx respuesta excepto la parte matriz dispersa. Una lista de ajustes o un gráfico de objetos simples sería una mejor opción aquí. La matriz debe asignar memoria para cada posible conexión que es O (n^2) donde n es el número de usuarios.Una lista o gráfico de objetos solo asignará memoria en O (e) donde e es el número de conexiones, que es escaso.

Utilizaría una búsqueda en profundidad con marcado para encontrar al amigo. Marcar nodos que ya ha recorrido es esencial, ya que existirán ciclos de amigos. Con un DFS, el hallazgo de la ruta es casi trivial porque la pila que está utilizando para ejecutar el DFS es la ruta. Entonces, cuando encuentres al amigo, solo sacaste toda la pila y listo.

Una primera búsqueda al principio no tiene esta propiedad agradable porque la cola utilizada para atravesar el gráfico tendrá nodos inexplorados, por lo que deberá realizar un seguimiento de la ruta utilizando alguna otra estructura. Una primera búsqueda amplia podría ser apropiada si esperamos que la función se ejecute contra personas en el mismo "vecindario" de amigos y realmente nos preocupa el rendimiento.

Otra buena propiedad del DFS es que se puede paralelizar. Al encontrar un nuevo nodo, uno puede crear engendrar nuevos procesos DFS/hilos/lo que sea para procesar los nodos hijos. Los nuevos hilos deben poder compartir la información de marcado a través de algún tipo de sistema de mensajes. Esto podría ser un poco de optimización prematura ahora que lo pienso un poco más. Aquí hay una paper sobre el tema por si alguien está interesado

Answer 6

Se puede usar una base de datos gráfico como neo4j