Breaking

Post Top Ad

Your Ad Spot

viernes, 5 de julio de 2019

Preguntas de la entrevista de la estructura de datos del gráfico

Introducción

Las preguntas de la entrevista relacionadas con los gráficos son muy comunes, y muchos algoritmos que se espera que conozca se encuentren en esta categoría.
Es importante conocer todos estos algoritmos: la motivación detrás de ellos, sus implementaciones y aplicaciones.
Si está interesado en leer más acerca de las preguntas de la entrevista de programación en general, hemos compilado una larga lista de estas preguntas, incluidas sus explicaciones, implementaciones, representaciones visuales y aplicaciones.

Preguntas de la entrevista de la estructura de datos del gráfico

Dicho simplemente: un gráfico es una estructura de datos no lineales formada por nodos / vértices y bordes.
Los nodos son entidades en nuestro gráfico, y los bordes son las líneas que los conectan:
what_are_graphs
Representación de una gráfica
Hay muchos tipos de gráficos, gráficos no dirigidos, gráficos dirigidos, gráficos con etiquetas de vértice, gráficos cíclicos, gráficos con bordes, gráficos ponderados, etc.
No obstante, se utilizan con mayor frecuencia para representar redes, ya sea una red de la ciudad, calles de la ciudad, un terreno para el paso de la IA o conexiones de redes sociales.

Amplia primera búsqueda

Ejemplo de pregunta de entrevista

Encuentra el camino más corto en un laberinto. Los bloques de ruta se representan como 1y los bloques de pared se representan como 0Puedes moverte en cuatro direcciones (arriba, abajo, izquierda, derecha).
                 0, 0, 0, 0, 0, 0, 0, 1, 1
                 0, 1, 1, 1, 1, 0, 0, 1, 0
                 0, 1, 0, 0, 1, 1, 1, 1, 0
                 1, 1, 1, 0, 1, 0, 0, 0, 0
                 1, 0, 1, 1, 1, 1, 1, 1, 1
                 1, 1, 0, 0, 0, 0, 0, 0, 0
                 0, 1, 0, 0, 1, 1, 1, 1, 0
                 0, 1, 0, 0, 1, 0, 0, 1, 0
                 0, 1, 1, 1, 1, 0, 0, 1, 1

Explicación

La primera búsqueda de amplitud (BFS, por sus siglas en inglés) es un algoritmo gráfico-transversal, que a menudo se usa para encontrar la ruta más corta desde el nodo de inicio hasta el nodo de objetivo.
BFS visita "capa por capa". Esto significa que en un gráfico como el que se muestra a continuación, primero visita a todos los hijos del nodo inicial. Estos niños son tratados como la "segunda capa".
bfs_search_gif
Después de visitar a todos los hijos del nodo inicial, el algoritmo luego visita a todos los hijos de los niños ya visitados, prácticamente moviéndose a la tercera capa.
Es importante tener en cuenta que BFS llegará al final del gráfico y luego calculará la ruta más corta posible. Garantiza encontrar el camino más corto posible, aunque paga el precio de no ser tan compatible con la memoria como otros algoritmos.
Para lograr esto, BFS utiliza una Queuey esta es una característica importante del algoritmo. La condición terminal del algoritmo es que Queueestá vacío, por lo que seguirá hasta que visite todos los nodos.
Echemos un vistazo al pseudo-código detrás de la implementación:
Queue queue  
node set visited true  
queue.enqueue(node)

while queue not empty  
    current = queue.dequeue()
    for v in current children
        if v is not visited
            v set visited true
            queue.enqueue(v)
Comenzamos agregando el nodo de inicio a la cola. Como la cola no está vacía, configuramos el nodo actual para que sea el nodo raíz y lo eliminamos de la cola.
Luego verificamos a todos los hijos del nodo actual y los visitamos si no los hemos visitado antes. Después de eso, agregamos los hijos a la cola.
Cada uno de estos hijos se convertirá en el siguiente currentnodo. Y dado que la estructura de datos de la cola sigue la estructura FIFO (primero en entrar , primero en salir), visitamos al resto de los niños de la segunda capa, antes de continuar visitando a los niños de las capas que siguen.

Aplicaciones BFS

"¿Dónde podemos usar BFS?"
¡Este algoritmo se usa en muchos sistemas a tu alrededor! Se usa muy a menudo para la búsqueda de rutas, junto con la búsqueda en profundidad en primer lugar. Se está utilizando en su sistema de navegación GPS para encontrar ubicaciones vecinas e incluso en sitios web de redes sociales y motores de búsqueda.
BFS se utilizó mucho en inteligencia artificial y aprendizaje automático, especialmente en robótica. Y probablemente lo más notable, en su carrera de programación, se está utilizando para la recolección de basura.

Primera búsqueda de profundidad

Ejemplo de pregunta de entrevista

Compruebe si el gráfico dado está fuertemente conectado o no:

Explicación

Depth First Search (DFS) es otro algoritmo de recorrido de gráficos, similar a la búsqueda en primer plano.
DFS busca lo más lejos posible a lo largo de una rama y luego retrocede para buscar lo más lejos posible en la siguiente rama. Esto significa que en el gráfico de procedimiento, comienza con el primer vecino y continúa en la línea hasta donde sea posible.
dfs_search
Una vez que llega al nodo final en esa rama (1), retrocede al primer nodo donde se enfrentó con la posibilidad de cambiar de rumbo (5) y visita esa rama completa, en nuestro caso solo (2).
Luego retrocede nuevamente al nodo (5) y, como ya ha visitado los nodos (1) y (2), retrocede a (3) y vuelve a enrutarse a la siguiente rama (8).
El algoritmo continúa recorriendo de esta manera hasta que todos los nodos hayan sido visitados y la pila esté vacía.
DFS no garantiza encontrar la ruta más corta posible y puede conformarse con un óptimo local, a diferencia de BFS. Gracias a esto, es más compatible con la memoria, aunque no mucho.
Para lograr esto, DFS utiliza una Stack, que es la principal diferencia entre estos dos algoritmos. Stacksigue una estructura LIFO (último en entrar, primero en salir), que es la razón por la que llega lo más lejos posible, antes de tomar en consideración las otras capas.
Puede implementar DFS con la ayuda de la recursión o iteración. El enfoque recursivo es más corto y más simple, aunque ambos enfoques son más o menos iguales en cuanto a rendimiento.
Echemos un vistazo al pseudocódigo recursivo detrás de la implementación:
dfs(node)  
node set visited true

for n in node neighbors  
    if n is not visited
    dfs(n)
Comenzamos llamando al algoritmo en el nodo dado y establecemos que se ha visitado.
Luego verificamos a todos los vecinos del nodo, y para cada uno, ejecutamos el mismo algoritmo si no se visita. Esto significa que antes de pasar al siguiente vecino, visita a todos los hijos del primer vecino. Luego regresa a la cima y visita al segundo vecino, que avanza en la búsqueda de todos sus hijos, y así sucesivamente.
Es posible que haya notado la falta de Stackeste ejemplo y me gustaría abordarlo correctamente. Ambos enfoques utilizan una Stackestructura en segundo plano, aunque en el enfoque recursivo, no lo definimos explícitamente de esa manera.
Echemos un vistazo al pseudocódigo iterativo detrás de la implementación:
dfs(node)  
    Stack stack
    node set visited true
    stack.push(node)

    while stack is not empty
        current = stack.pop()
        for n in node neighbors
            if n is not visited
                n set visited true
                stack.push(n)
Aquí, agregamos el nodo de inicio al StackComo la pila no está vacía, configuramos el currentnodo para que sea el nodo inicial y lo sacamos de la pila.
Consideramos a todos los vecinos, uno por uno. El primer vecino se agrega a la pila, lo que lo convierte en el nuevo currentnodo en la siguiente iteración. De esta manera, todos los hijos de este nodo se verifican antes del nodo que se encuentra al lado de este, desde la lista de vecinos originales.

Aplicaciones DFS

"¿Dónde podemos usar DFS?"
Similar a BFS, el DFS se usa a menudo en inteligencia artificial y aprendizaje automático. Estos dos algoritmos son muy comunes y se comparan a menudo.
DFS se usa generalmente para la búsqueda de rutas entre nodos, ¡y especialmente para encontrar rutas para laberintos! DFS también se utiliza para la clasificación topológica y para encontrar componentes fuertemente conectados.

Una búsqueda

Dado el siguiente gráfico, donde el nodo negro es el nodo inicial, los nodos rojos son las paredes y el nodo verde es el nodo objetivo, busque la ruta más corta al nodo verde:
a_star_search_example

Explicación

Una * búsqueda es muy diferente de las dos que hemos hablado anteriormente. También es un algoritmo de recorrido gráfico, sin embargo, se utiliza para manejar escenarios de búsqueda de caminos en la vida real.
Una búsqueda * se basa en una función de costo de conocimiento y heurística para el nodo dado como una forma de decidir qué nodo debería visitar a continuación. En la mayoría de los casos, esta función de costo se denota como f(x).
La función de costo se calcula como la suma de otras dos funciones:
  • g(x) - La función que representa el costo de pasar del nodo inicial a un nodo determinado.
  • h(x) - El costo estimado desde el nodo dado al nodo objetivo.
Obviamente, no sabemos el costo exacto de movimiento de la nota dada al nodo objetivo, razón por la cual h(x)también se la denomina "heurística".
El algoritmo siempre elige el nodo con el valor más f(x)bajo . Esto es lógico, considerando cómo se calcula la función.
Los pocos pasos que tomamos desde el punto de partida combinados con lo cerca que nos acercamos a la meta hacen que el valor sea f(x)menor si vamos por el camino más corto hacia la meta. Alejarse de la meta y hacer más pasos de los necesarios para alcanzarla aumenta la f(x)función.

A * Aplicaciones de búsqueda

"¿Dónde podemos usar A * Search?
Este algoritmo se usa generalmente para la mayoría de los problemas de ruta más corta. A menudo se utiliza para escenarios de búsqueda de la vida real, así como para videojuegos. La mayoría de los jugadores de NPC y AI confían en A * para buscar de forma inteligente un camino, rápido y eficiente.

Algoritmo de Dijkstra

Dado el siguiente gráfico ponderado, encuentre la ruta más corta entre los vértices A y H.
dijkstra_interview_graph

Explicación

El algoritmo de Dijkstra es un algoritmo de recorrido gráfico notorio para encontrar la ruta más corta desde un nodo / vértice dado a otro.
Hay varias implementaciones de este algoritmo y algunas incluso utilizan diferentes estructuras de datos y tienen diferentes aplicaciones. Cubriremos el clásico: encontrar la ruta más corta entre dos nodos.
Dijkstra funciona de forma ligeramente diferente a los algoritmos anteriores. En lugar de comenzar en el nodo raíz, comienza en el nodo objetivo y retrocede hasta el nodo inicial.
El algoritmo hace esto construyendo un conjunto de notas con la distancia mínima desde la fuente, dictada por el "peso" de los bordes.
Está construido con algunas variables:
  • dist : la distancia desde el nodo objetivo (más a menudo denominado nodo de origen) a todos los demás nodos del gráfico. El distnodo de origen es 0, ya que ahí es donde empezamos. Además, la distancia a todos los demás nodos se establece en infinito. A medida que el algoritmo atraviesa el gráfico, la distancia a todos los demás nodos se recalcula de acuerdo con el nodo actual.
  • Q : Al igual que en BFS, necesitamos definir un tipo de datos de cola y rellenarlo con todos los nodos del gráfico. La condición terminal para el algoritmo es si la cola está vacía.
  • Establecer : también necesitaremos un conjunto que contenga todos los nodos visitados para no volver a visitarlos. Al final, el conjunto contendrá todos los nodos del gráfico.
Echemos un vistazo al pseudo-código detrás de su implementación:
dijkstra(Graph, source)  
    source set distance 0

    for n in Graph
        if n is not source
            n set dist infinity
            n set parent none
            queue.add(n)

    while Q is not empty
        n = node in Q with min dist(n)
        remove n from Q

        for node in n neighbors
            i = dist(n) + length(node, goal)
            if i < dist(goal)
                dist(goal) = i

Aplicaciones Dijkstra

"¿Dónde podemos usar Dijkstra?"
Este algoritmo se usa generalmente para muchos de los problemas de ruta más corta, y definitivamente es un algoritmo notable.
Google Maps usa Dijkstra para encontrar la ruta más corta en la navegación. El enrutamiento IP también depende en gran medida exactamente de Dijkstra y tiene aplicaciones en redes de computadoras.

Comparando BFS, DFS, A * y Dijkstra

Esto podría no aparecer como una pregunta de entrevista, pero ciertamente es una pregunta lógica. Hemos cubierto 4 algoritmos diferentes que se utilizan principalmente para el mismo propósito.
"¿Cuál debería usar? ¿Cuál es la mejor?"
La respuesta a esta pregunta común es: todas ellas .
Cada uno de estos algoritmos, aunque aparentemente similares, ofrece ventajas sobre el otro, según la situación en la que los esté implementando y su caso específico.
Aquí hay algunos casos en los que podría elegir cuál usaría:
  • Encontrar miembros actualmente vivos en un árbol genealógico.
En tal caso, sería mejor usar DFS ya que la mayoría de los niveles más lejanos están vivos. BFS perdería demasiado tiempo considerando niveles que no deberían ser considerados. No tendría sentido usar Dijkstra o A * para este propósito.
  • Encontrar a los miembros fallecidos en un árbol genealógico.
En tal caso, usar DFS sería menos práctico que BFS ya que la mayoría de los miembros fallecidos se ubicarían cerca de la parte superior. BFS atravesaría este gráfico capa por capa y agregaría todos los miembros relevantes a la lista.
  • Encontrar la ruta más corta desde el punto A al punto B en un gráfico / mapa.
En tal caso, aunque un poco controvertido, usar una búsqueda A * sobre Dijkstra es una práctica común. Usar BFS y DFS aquí puede ser muy poco práctico. BFS asume que el peso entre todos los nodos es el mismo, mientras que el peso / costo real podría variar. ¡Aquí es donde entra en juego Dijkstra!
Dijkstra toma en cuenta el costo de moverse en una ventaja. Si el costo de ir en línea recta es más grande que hacerlo, se dará una vuelta. Esto puede traducirse en carreteras congestionadas en un mapa para un ejemplo.
A * se enfoca en alcanzar la meta, y solo da pasos que parecen prometedores y razonables, de acuerdo con sus funciones.
Dijkstra toma en consideración todos los demás nodos, mientras que A * solo toma los razonables. Debido a esto, A * es más rápido que Dijkstra y a menudo se considera "el algoritmo de búsqueda inteligente".
Algunos también se refieren a A * como el algoritmo Dijkstra "informado". Si quita la heurística de A *, lo que significa que elige el siguiente paso solo de acuerdo con el costo hasta el momento, prácticamente obtiene Dijkstra, al revés. Esto hace que A * corra no con avidez hacia la meta, sino en todas las direcciones considerando cada nodo en la gráfica, que de nuevo es lo mismo que Dijkstra.
Si está buscando una búsqueda y resultados optimizados buscando exclusivamente el objetivo, A * es la opción para usted.
Si está buscando un algoritmo para calcular la ruta más corta entre el punto de inicio y cada nodo en el árbol, que incluye el nodo objetivo, Dijkstra es la opción para usted.

Recursos

Si está buscando una mejor manera de practicar este tipo de preguntas de programación de entrevista, así como otras, entonces le recomendamos que pruebe un servicio como el problema de codificación diaria . Te enviarán un nuevo problema para resolver todos los días, todos los cuales provienen de las mejores compañías. También puede encontrar más información aquí si desea más información.

Conclusión

En este artículo, hemos cubierto las preguntas comunes de la entrevista relacionadas con la estructura de datos del gráfico.
Nuevamente, si está interesado en leer más acerca de las preguntas de la entrevista de programación en general, hemos compilado una larga lista de estas preguntas, incluidas sus explicaciones, implementaciones, representaciones visuales y aplicaciones.

No hay comentarios.:

Publicar un comentario

Dejanos tu comentario para seguir mejorando!

Post Top Ad

Your Ad Spot

Páginas