¿Cómo diseñaría las estructuras de datos para una red social muy grande como Facebook o Linkedln? Describa cómo diseñaría un algoritmo para mostrar el camino más corto entre dos personas (p. ej., Yo-> Bob-> Susan-> Jason-> Usted).
Preguntado en: entrevista de Google
Una buena forma de abordar este problema es eliminar algunas de las restricciones y resolver primero esa situación.
Caso 1: Simplifique el problema (sin considerar a millones de personas)
Podemos construir un gráfico tratando a cada persona como un Node y dejando que un borde entre dos Nodes indique que los dos usuarios son amigos. Si queremos encontrar el camino entre dos personas, comenzamos con una persona y hacemos una búsqueda simple en amplitud . Alternativamente, podemos hacer una búsqueda bidireccional en amplitud. Esto significa hacer dos búsquedas primero en amplitud, una desde el origen y otra desde el destino. Cuando las búsquedas chocan, sabemos que hemos encontrado un camino.
¿Por qué no funciona bien una búsqueda en profundidad? Primero, la búsqueda en profundidadsólo encontraría un camino. No necesariamente encontraría el camino más corto. En segundo lugar, incluso si solo necesitáramos cualquier ruta, sería muy ineficiente. Dos usuarios pueden tener solo un grado de separación, pero podría buscar millones de Nodes en sus «subárboles» antes de encontrar esta conexión relativamente inmediata.
En la implementación, usaremos dos clases para ayudarnos. BFSData contiene los datos necesarios para una búsqueda en amplitud, como la tabla hash isVisited y la cola toVisit. PathNode representa la ruta a medida que estamos buscando, almacenando cada Persona y el Node anterior que visitamos en esta ruta.
Lógica principal en Java dada a continuación
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())
{
/* Search out from source. */
Person collision = searchlevel(people, sourceData, destData);
if (collision != null)
return mergePaths(sourceData, destData, collision.getID());
/* Search out from destination. */
collision = searchlevel(people, destData, sourceData);
if (collision != null)
return mergePaths(sourceData, destData, collision.getID());
}
return null;
}
/* Search one level and return collision, if any.*/
Person searchLevel(HashMap<Integer, Person> people,
BFSData primary, BFSData secondary)
{
/* We only want to search one level at a time. Count
how many nodes are currently
in the primary's level and only do that many nodes.
We continue to add nodes to the end. */
int count = primary.toVisit.size();
for (int i= 0; i < count; i++)
{
/* Pull out first node. */
PathNode pathNode = primary.toVisit.poll();
int personid = pathNode.getPerson().getID();
/* Check if it's already been visited. */
if (secondary.visited.containsKey(personid))
return pathNode.getPerson();
/* Add friends to queue. */
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;
}
/* Merge paths where searches met at the connection. */
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(); // remove connection
pathOne.addAll(pathTwo); // add second path
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();
}
}
¿Qué tan rápido es la solución basada en BFS anterior?
Supongamos que cada persona tiene k amigos, y el Origen S y el Destino D tienen un amigo C en común.
1. Búsqueda tradicional en amplitud de S a D: Pasamos por aproximadamente k+k*k Nodes: cada uno de los k amigos de S, y luego cada uno de sus k amigos.
2. Búsqueda bidireccional primero en amplitud: Pasamos por 2k Nodes: cada uno de los k amigos de S y cada uno de los k amigos de D. Por supuesto, 2k es mucho menor que k+k*k.
3. Generalizando esto a un camino de longitud q, tenemos esto:
3.1 BFS: O(k q )
3.2 BFS bidireccional: 0( k q/2 + k q/2 ), que es simplemente 0( k q/2 )
Si imaginamos un camino como A->B->C->D->E donde cada persona tiene 100 amigos, esta es una gran diferencia. BFS requerirá examinar 100 millones (100 4 ) de Nodes. Un BFS bidireccional requerirá observar solo 20 000 Nodes (2 x 100 2 ).
Caso 2: manejar millones de usuarios
Para todos estos usuarios, no podemos mantener todos nuestros datos en una sola máquina. Eso significa que nuestra estructura de datos de persona simple de arriba no funciona del todo: es posible que nuestros amigos no vivan en la misma máquina que nosotros. En su lugar, podemos reemplazar nuestra lista de amigos con una lista de sus ID y recorrer de la siguiente manera:
1: Para cada ID de amigo: int machine index = getMachineIDForUser(person_ID);
2: Ir a la máquina #machine_index
3: En esa máquina, haz: Persona amiga = getPersonWithID( person_ID);
El siguiente código describe este proceso. Hemos definido una clase Servidor, que contiene una lista de todas las máquinas, y una clase Máquina, que representa una sola máquina. Ambas clases tienen tablas hash para buscar datos de manera eficiente.
Lógica principal en Java dada a continuación->
Java
// A server that holds list of all machines
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);
}
}
// A person on social network has id, friends and other info
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);
}
}
A continuación se presentan algunas optimizaciones y preguntas de seguimiento.
Optimización: Reducir los saltos de máquina
Saltar de una máquina a otra es costoso. En lugar de saltar aleatoriamente de una máquina a otra con cada amigo, intente agrupar estos saltos, por ejemplo, si cinco de mis amigos viven en una máquina, debería buscarlos a todos a la vez.
Optimización: División inteligente de personas y máquinas
Es mucho más probable que las personas sean amigas de personas que viven en el mismo país que ellos. En lugar de dividir aleatoriamente a las personas entre las máquinas, intente dividirlas por país, ciudad, estado, etc. Esto reducirá el número de saltos.
Pregunta: La búsqueda primero en amplitud generalmente requiere «marcar» un Node como visitado. ¿Cómo se hace eso en este caso?
Por lo general, en BFS, marcamos un Node como visitado estableciendo un indicador de visitado en su clase de Node. Aquí, no queremos hacer eso. Podría haber múltiples búsquedas al mismo tiempo, por lo que es una mala idea editar nuestros datos.
En cambio, podríamos imitar el marcado de Nodes con una tabla hash para buscar una identificación de Node y determinar si ha sido visitado.
Otras preguntas de seguimiento:
1. En el mundo real, los servidores fallan. Cómo te afecta esto?
2. ¿Cómo podría aprovechar el almacenamiento en caché?
3. ¿Buscas hasta el final del gráfico (infinito)? ¿Cómo decides cuándo rendirte?
4. En la vida real, algunas personas tienen más amigos de amigos que otras y, por lo tanto, es más probable que hagan un camino entre usted y otra persona. ¿Cómo podría usar estos datos para elegir dónde comenzar a atravesar?
Referencia para este artículo
Referencia para este artículo
Este artículo es una contribución del Sr. Somesh Awasthi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA