Solicité a través de una referencia de empleado para el puesto SDET-1. Fui entrevistado en Amazon Chennai (SP Infocity). Me enfrenté a 5 rondas cara a cara.
El 11 de octubre me enfrenté a la primera ronda que estaba principalmente relacionada con la resolución de problemas y la codificación.
Ronda 1: Ronda de resolución de problemas y codificación (1 hora)
La entrevistadora simplemente comenzó con una pregunta formal de presentación. Luego me preguntó sobre mi proyecto de fin de carrera, lo expliqué claramente y lo esbocé en la pizarra.
Luego me hizo dos preguntas de codificación.
- Simule un patrón de bloqueo de Android.
- Genera todas las palabras que se pueden formar con el patrón dado . La especificación del teclado es el teclado móvil. Lo explicaré claramente.
Si la entrada dada es 2 3 6.
2 corresponde a abc. 3 corresponde a def. 6 corresponde a mno.
Supongamos que si tenemos que generar todas las combinaciones de 2,3,6, la salida debería ser un conjunto de strings
adm,adn,ad0,bdm,bdn,bd0,…..
Di una solución recursiva e iterativa para imprimir las combinaciones.
Luego, la entrevistadora modificó ligeramente la pregunta. Me pidió que validara las strings generadas con un diccionario.
Di dos enfoques para mantener el diccionario. Primero, sugerí un enfoque de tabla hash que toma una complejidad de tiempo promedio O (1) para las operaciones de inserción, eliminación y búsqueda.
Luego, dado que las strings generadas tienen prefijos comunes, sugerí un enfoque trie para el diccionario.
El entrevistador quedó satisfecho con mi solución y me pidió que codificara la solución por completo.
Después de unos días tuve 2 rondas cara a cara.
Ronda 2: Ronda de prueba y automatización (1 hora)
El entrevistador comenzó preguntándome si tenía conocimientos previos sobre pruebas y entornos de prueba, a lo que respondí que no. Luego discutimos sobre los tipos de prueba y las diferentes fases y los procedimientos de prueba asociados con ella. Luego me hizo dos preguntas simples de generación de casos de prueba.
Di alrededor de 10 casos de prueba para la pregunta, ya que era bastante sencillo. Y codifiqué algunos usando la prueba JUnit, que es realmente simple.
2. Dado un módulo de archivo abierto en un editor, ¿cuáles son los posibles escenarios en los que el módulo de archivo abierto podría dar errores?
Di una lista de casos en los que discutimos claramente sobre los entresijos de cada uno.
Esta ronda fue bastante fácil ya que preparé la parte de prueba el día anterior.
Ronda 3: Ronda de estructuras de datos y algoritmos (1 hora y 15 minutos)
Dos tipos me entrevistaron en esta ronda. Comenzamos con una presentación formal. Luego me hicieron dos preguntas.
Dado un tablero de ajedrez*n y un caballo que se coloca en cualquier esquina, genera todos los caminos posibles siguiendo los cuales el caballo puede cubrir todas las casillas.
Empecé con un enfoque usando BFS. Pero había una falla en mi enfoque que era que el caballero no escaparía de una celda si todos los puntos posibles a los que el caballero puede ir desde ese punto dado fueron explorados previamente.
Luego di una solución usando Backtracking.
Comience con una esquina. Para todos y cada uno de los puntos posibles que el caballo puede alcanzar, haga llamadas recursivas a aquellos que usan un bucle for simple. el camino recorrido que se puede mantener fácilmente en una array. Esto resuelve la falla en mi enfoque anterior, ya que podemos volver a la otra posibilidad si se llega a un camino muerto.
El entrevistador estaba contento con mi enfoque y me pidió que codificara la solución. Lo codifiqué y luego pasamos a la siguiente pregunta.
Primero di un enfoque de fuerza bruta O (n ^ 2) y luego lo optimicé para O (n) tiempo y O (n) Espacio. Luego, finalmente di una solución de O (n) tiempo O (1) espacio al encontrar el diferencia absoluta de las longitudes de las dos listas. Luego me pidieron que codificara la solución, que era bastante sencilla.
Después de esto tuve las dos rondas finales el 31 de octubre.
Ronda 4: Ronda de gerentes de contratación (1 hora)
El entrevistador me pidió que informara sobre mí. Luego nos concentramos en mi proyecto durante los primeros minutos y luego el entrevistador me preguntó sobre las entrevistas a las que había asistido anteriormente y cómo se desarrolló el proceso. Luego comenzó a preguntar sobre las pruebas y el uso de las pruebas correspondientes a algunos escenarios dados. Después de unos minutos de discusión, hizo dos preguntas sobre estructuras de datos.
Primero di un enfoque O (nlogn) para encontrar los pares e imprimirlos. El enfoque fue ordenar la array y mantener dos índices (en cada extremo) a la izquierda y a la derecha y encontrar si los pares suman la suma dada e imprimirlos hasta que los punteros izquierdo y derecho se crucen.
Luego me preguntó si puedo optimizarlo aún más. Le di un enfoque O (n) usando hash. Mantuve un hashset de enteros. Coloque el primer número en el hashset, comience desde el segundo elemento y para cada número en la array verifique si (Suma dada – Elemento actual) está presente en el hashset. Si es así, imprima el par.
2. Dado un árbol binario, imprima la vista inferior del mismo .
Después de pensar unos minutos, se me ocurrió un enfoque utilizando la distancia horizontal de los Nodes desde la raíz. Tenemos que tomar nota del último Node a una distancia horizontal particular mientras se atraviesa usando el recorrido de orden de nivel. Usé un Hashtable para almacenar el último Node visitado en cada distancia horizontal.
Este enfoque utiliza el tiempo O(n) y el espacio O(n).
Luego hizo un rompecabezas.
En una sala de 30 personas, encuentre el número único de apretones de manos dada la condición de que cada uno en la sala debería haberle dado la mano a todos.
Acabo de utilizar una lógica simple. En una habitación de 2 personas, solo hay un apretón de manos único (la primera persona tiene un apretón de manos único mientras que la segunda no tiene ninguno). Si consideramos tres personas,n = 3 (A,B,C)
A tiene dos apretones de manos únicos B, C. (n-1 apretones de manos)
B tiene 1 apretón de manos único C. (n-2 apretones de manos)
C no tiene ningún apretón de manos único.
número total de apretones de manos = n-1 + n-2 = 2n-3 = 3. (que es la suma de los dos primeros números naturales)
De manera similar, para n personas, los apretones de manos únicos serían la suma de los primeros n-1 números naturales.
Para n = 30, el número total de apretones de manos únicos es 29*30/2 = 29*15 = 435.
Eso es un envoltorio. Estaba contento con la forma en que me acerqué a la solución.
Me preguntó si tenía alguna pregunta para él. Pregunté sobre la cultura y el ambiente de trabajo en amazon.
Ronda 5: Ronda de aumento de barra (1 hora)
Dos miembros entraron a la sala y se presentaron y comenzamos con mi presentación y mi proyecto.
Me preguntaron cuántas rondas tenía antes de la actual. Al principio solo hicieron algunas preguntas sobre las pruebas. Luego hicieron dos preguntas de codificación.
Inmediatamente comencé con una solución de fuerza bruta al encontrar el recorrido en orden del árbol. Luego ordené la array y encontré el k-ésimo más grande en la array ordenada, que es el (nk)-ésimo elemento del índice de inicio de la array, donde n es el número total de Nodes en el árbol. Esto usa el tiempo O(nlogn) y el espacio O(n).
Me pidieron que lo optimizara aún más.
Di una solución de tiempo O (nlogn) y espacio O (1) convirtiendo el árbol binario en una lista doblemente enlazada y luego encontrando el kth más grande en una lista doblemente enlazada que se puede hacer en el tiempo O (nlogn).
Pero hay una solución mejor para esto que no se me ocurrió durante la entrevista. Simplemente construya un minimontón de k elementos, inserte elementos en el montón recorriendo el árbol utilizando cualquier recorrido.
Si el elemento raíz del montón es más pequeño que el Node actual del árbol, elimine el elemento raíz del montón e inserte el nuevo elemento en el montón. Por fin, después del recorrido completo del árbol, el k-ésimo elemento más grande estará en la raíz del montón. Esto usa el tiempo O(nlogk) y el espacio O(k).
Pero estaban contentos con mi enfoque ya que me dijeron que lo optimizara ya sea por espacio o por tiempo. Le di un enfoque de espacio constante para que estuvieran satisfechos.
2. Dada una gráfica dirigida, encuentra si existe un ciclo o no. Si existe, imprímelo.
Di una solución usando BFS. Puse un Node en la cola y luego agregué todos los Nodes posibles a los que se puede acceder desde el Node actual. Mientras recorremos los Nodes, simplemente marcamos el Node como visitado en el hashmap para evitar bucles indefinidos entre Nodes. Estaban satisfechos con mi enfoque.
Finalmente, preguntaron cómo se implementa HashMap y cómo funciona (especialmente cómo se calculan el código hash y el índice). Diseñé mi propia función hash y expliqué la forma en que funcionan las funciones get y put en un mapa hash. Estuvieron contentos con mi explicación y luego me preguntaron cómo modificaría su función hash en caso de colisión y discutieron brevemente sobre las técnicas de manejo de colisiones.
Me preguntaron si tenía alguna pregunta para ellos. Acabo de hacer la misma pregunta que hice en la ronda anterior.
PD: Para cada pregunta tenemos que escribir el código claramente. No se sumerja directamente en la parte de la codificación, explique claramente su enfoque. Tenga confianza y no quieren la solución optimizada para la pregunta, ven cómo el candidato aborda la pregunta.
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