No logré responder cómo encontrar el camino más corto para salir de un laberinto en una entrevista técnica. ¿Cómo debo mejorar mis habilidades de algoritmo?

Answer 1

Practica en una palabra.

¿Fuiste fuerte en los algoritmos y estructuras de datos en la escuela? ¿Es esta la primera vez que eres consciente de ser débil en esos problemas particulares? ¿Conoces algún otro algoritmo en el que puedas estar débil? ¿Qué hiciste para prep?

Sé que esas son muchas preguntas en una respuesta, pero necesita saber estas cosas para evaluar realmente los tipos de problemas en los que necesita trabajar.

Algunos consejos generales serían recoger las copias de CLRS y Cracking the Coding Interview e ir a la ciudad. Tal vez tome un curso en línea como Algoritmos, Parte I – Universidad de Princeton | Coursera y es parte 2 (son gratis). Ve a Hacker Rank y prueba algunos desafíos de codificación. Únase y asista a su grupo de desarrolladores locales y vea si puede obtener algunos consejos y trucos sobre cómo resolver problemas y haga que otros desarrolladores practiquen la codificación de la pizarra con usted. Si se trata de una empresa de prestigio con una entrevista más difícil (Apple, Google, Facebook, Microsoft), sugeriría (si tiene los fondos) utilizar los servicios proporcionados por una empresa como CareerCup. Son las mismas personas detrás de la entrevista de Cracking the Coding, pero también ofrecen reseñas de currículums, videos de videos simulados grabados previamente y entrevistas en vivo en línea o en persona de ex empleados de los líderes técnicos antes mencionados.

El verdadero avance vendrá de conocer tus propias debilidades. ¿Dónde estás débil técnicamente? ¿Se está comunicando con la suficiente eficacia? ¿Cómo es tu currículum y tu presentación general durante la entrevista? Si tuviera que recomendar algo de lo anterior, primero sería el grupo de desarrolladores locales. Otros profesionales podrían decirle dónde faltan sus soluciones. ¡Espero que eso ayude!

PD

No estoy patrocinado por ninguna de las empresas mencionadas anteriormente.

Answer 2

Su descripción de la pregunta es muy vaga, pero supongo que su entrevistador probablemente quiso que usted definiera una estructura de datos para representar un laberinto y un algoritmo para resolverlo.

Muchas formas de definir un laberinto son posibles, pero la primera que me viene a la mente es una simple matriz 2D con 1 y 0 para indicar la presencia o ausencia de paredes. También necesitas una forma de representar las coordenadas iniciales.

Una vez que haya definido su laberinto, el primer algoritmo que puede hacer de forma iterativa es el algoritmo ideal para resolver el laberinto con la ruta más corta. Puede mantener una estructura de datos externa con una copia del laberinto para rastrear los cuadrados que ya ha visitado. También necesita una forma de conocer la ruta más corta a cualquier cuadrado, por lo que necesitará una estructura de datos independiente que también puede almacenar como una matriz 2D donde cada entrada de la matriz contiene las coordenadas del cuadrado anterior en la ruta más corta. Una vez que tienes todo lo que el algoritmo es bastante sencillo.

En pseudocódigo:

Lista óptimoSolveMaze (bool [] [] maze, Coordinate start, Coordinate finish) {

Valida tu aporte

Inicializar 2d array de cuadrados visitados

Inicializar 2d matriz de coordenadas anteriores

Establezca las coordenadas anteriores de la casilla de inicio en nulo para indicar que es el primero.

Inicialice la cola de coordenadas BFS y agregue inicio a la cola

Coord next = queue.pop ()

mientras (siguiente! = terminar) {

para cada plaza adyacente no visitada {

establece su anterior al siguiente

marcarlo visitado

agregarlo a la cola

}

}

if (next! = final) retorno imposible

construir la lista de soluciones de nuevo desde las coordenadas de acabado hasta el inicio

}

Answer 3

Esa es una pregunta típica de la entrevista, para responderla correctamente en el tiempo, debe dominar un par de temas: recursión, teoría de grafos (especialmente la búsqueda en profundidad en su caso) y código especialmente limpio. Leer y practicar es la única manera.

He encontrado 2 libros particularmente interesantes.

1. El manual de diseño de algoritmos: Steven S Skiena: 9781848000698: Amazon.com: Libros
2. Programming Pearls (2ª edición): Jon Bentley: 0785342657883: Amazon.com: Libros

Estos 2 libros contienen referencias muy interesantes también.

Por lo general, los libros publicados antes de 1990 contienen gran cantidad de estructuras de datos y algoritmos porque los ingenieros pioneros lucharon con la falta de capacidad de computación y memoria.

Los temas básicos de informática son difíciles de entender, pero una vez que los entiendes bien, no los olvidarás fácilmente, todos se basan en algoritmos simples pero efectivos.

Definitivamente recibirás un montón de comentarios que dicen que esta es una pregunta de entrevista terrible porque en el trabajo no estarás resolviendo laberintos. Quieren saber si entiendes completamente los conceptos básicos de CS. Como compañero ingeniero de software, me gustaría que conociera los conceptos básicos antes de comenzar a darme conferencias sobre temas de escalabilidad y confiabilidad.

Answer 4

Piensa cómo resolverías el problema si estuvieras en un laberinto real. Empiezas en un punto y luego lanzas migas de pan alrededor para hacer un seguimiento de tu camino. Resulta que sabes que puedes salir, pero te gustaría ahorrar pan. Por lo tanto, usted intentaría dejar caer migas de pan y contar (por ejemplo, si el pan se cuantificó en migas de pan) el número restante. En un punto, si necesita tomar una decisión en el laberinto (el caso general), puede rastrear cada camino, y para los caminos que no tienen salidas, deje las rutas de navegación, y para los caminos que sí tienen salidas, deje las rutas de pan de manera óptima (con avidez ?). Ahora puede repetir lo mismo en cada cruce y llegar a la salida con el menor camino.

Otra forma de ver esto es que cada empalme (contando las entradas y salidas como uniones por el bien de la discusión) podría tomarse como un nodo y las rutas entre dos nodos podrían tomarse como bordes del gráfico. Usted termina con un gráfico (posiblemente cíclico) y puede usar cualquiera de los algoritmos de gráfico estándar para obtener la ruta mínima desde el nodo de entrada (unión) al nodo de salida (unión).

Desde mi experiencia limitada, creo que se trata más de tratar de ver cómo su cerebro resolvería un rompecabezas en el que necesita encontrar el camino más corto y luego implementarlo utilizando cosas que la computadora pueda entender (probablemente diferentes tipos de cosas para la velocidad y la velocidad). problemas de eficiencia).

Answer 5

No estoy seguro de para qué solicitó, pero ¿resolver este problema tiene algo que ver con lo que se supone que debemos hacer en su trabajo? La mayoría de los trabajos de Ingeniería de Software no requieren conocimiento del algoritmo de Dijkstra, el algoritmo de búsqueda A * o cualquier otro algoritmo de recorrido de ruta. Pero todavía se pregunta, porque los entrevistadores realmente no tienen idea de lo que realmente deberían probar. Y esto suena como una pregunta típica que luego surgiría.

Answer 6

¿El producto principal de la compañía tenía que ver con guiar a la gente de los laberintos?

¿No?

Oh bien. Tenías un entrevistador de mierda. Mala suerte.

Pero sigue buscando trabajos que utilicen lo que realmente haces para ayudarlos a obtener ganancias.

En realidad, hay más de esos trabajos de los que sugieren algunas de las extrañas entrevistas de los concursos de publicaciones de informática.