Experiencia de entrevista de Traveloka para SDE3 (en el campus)

Objetivo técnico en línea Ronda 1 : La ronda tenía 50 preguntas sobre C++ y sus resultados. Se realizó en Hackerrank. El tiempo límite asignado fue de 75 minutos.

Después de la primera ronda, unos 50 estudiantes se clasificaron para la segunda ronda.

Ronda de codificación en línea 2: había 2 preguntas para resolver.

Pregunta 1: N Nodes donde se dan. Cualquier par de Nodes estaban conectados entre sí si el GCD (Node1, Node2) era mayor que un valor de umbral dado (T). El problema era encontrar si dos Nodes dados tenían alguna ruta entre ellos para consultas Q. La aplicación de BFS modificado después de crear la array de adyacencia superó la mayoría de los casos de prueba.

Pregunta 2. Problema de cambio de moneda modificado .

Había N monedas que debían convertirse en M monedas. Si estuviera en X monedas, entonces podría ir a (X + Y) sumando Y monedas donde Y es un factor primo de X. Agregar una Y constituía un solo paso . El problema era encontrar el número mínimo de pasos requeridos para la conversión. El problema podía resolverse mediante Programación Dinámica.

8 Los estudiantes fueron seleccionados después de la Ronda de Codificación para las rondas de entrevistas.

Entrevista Ronda 1:  La entrevista también fue en línea en Skype. La entrevista comenzó con las presentaciones habituales. Luego me preguntaron sobre mi idioma preferido y los proyectos que realicé en ellos. Luego se hicieron algunas preguntas de codificación.

Problema 1: encuentre la suma máxima de rutas en un árbol binario. La ruta podría comenzar y terminar en cualquier Node del árbol. Discutí con él mi enfoque y estaba muy interesado en él. Me dijo que escribiera un pseudocódigo para ello. Más tarde encontró algún error y me dijo que volviera a verificar. Después de algún tiempo le di un enfoque O(n). Estaba satisfecho con eso.

Problema 2: encontrar LCA en un árbol binario. Estaba atascado en encontrar LCA en un BST en lugar de un árbol binario. Entonces, primero le di una solución O (altura) para encontrar LCA en BST. Pero esperaba una solución O(n) para el árbol binario. Así que le di otra solución para encontrar LCA usando el recorrido de ruta en O(n).

Problema 3: hay N compromisos en un repositorio. Para un commit x en particular, se sabe que no hubo ningún error en el repositorio y después de un commit Y hay algún error en el repositorio. El problema era encontrar el compromiso que causó el error.

Escribí el algoritmo de búsqueda binaria para el problema con complejidad O(log(n)). Después del simulacro, se convenció de que la solución funcionará para el problema.

La ronda duró 1 hora. 4 estudiantes fueron seleccionados para la siguiente ronda.

Entrevista Ronda 2: Esta ronda también comenzó con la introducción. El entrevistador me preguntó por las preguntas de la ronda anterior y mi enfoque de las mismas.  

Problema 1:  me dieron una estructura de datos de cola que admite operaciones estándar como enqueue() y dequeue(). Tuve que implementar una estructura de datos de pila usando solo instancias de cola y operaciones de cola permitidas en las instancias.

Solución: https://www.geeksforgeeks.org/implement-stack-using-queue/

Problema 2: implementar caché LRU. Lo estaba implementando usando un mapa hash y una lista vinculada O (n). Esperaba O (1) para el reemplazo de página. Luego usé Queue usando una lista doblemente enlazada en mi enfoque.

Solución: https://www.geeksforgeeks.org/lru-cache-implementation/

Luego me hizo otra pregunta para resolver problemas. Se hicieron algunos conceptos de gestión de memoria, preguntas relacionadas con proyectos y conceptos de DBMS. Quería saber las razones de elegir una tecnología sobre otra en mis proyectos.

Después de eso, me preguntó si tenía alguna pregunta. Le hice algunas preguntas. Respondió a cada una de mis preguntas con una explicación.

Esta ronda duró aproximadamente 1 hora y 15 minutos. Los entrevistadores estaban más interesados ​​en conocer mi enfoque de los problemas de DS que en el código.

El proceso completo duró dos días. Fui seleccionado para SLI+FTE. 4 estudiantes se ofrecieron ambos al final.