Experiencia de entrevista en Amazon | Pasante SDE

Pasantía – 6 Meses Fuera del Campus Diciembre 2019

La ronda 1:

Fue una prueba en línea en Mettl. Consistía en 28 MCQ basados ​​en estructuras de datos y algoritmos y algunas preguntas basadas en resultados. Dificultad: – Media a Alta

También tenía dos preguntas de programación: –

1. Problema de lanzamiento de dados
   https://www.geeksforgeeks.org/dice-throw-dp-30/
2. Dado un entero de 32 bits sin signo, busque a) el bit con signo más a la izquierda b) el bit con signo más a la derecha c) el número total de bits con signo. Tenemos dos que devuelven una array de caracteres que contiene a#b#c

Pude resolver ambas preguntas. Después de aproximadamente 7 días, recibí un mensaje de que había aprobado la prueba y me llamaron para una entrevista una semana después.

La ronda 2:

Fue una ronda Cara a Cara. El entrevistador fue amable. Empecé preguntando por una introducción técnica, si había hecho prácticas o no. Luego saltó directamente a DS y algoritmos.
Me hicieron dos preguntas en esta ronda y me pidieron que escribiera el código para las mismas.

1. Recorrido iterativo posterior al pedido de un árbol binario. (El entrevistador me pidió específicamente que usara solo una pila)
   https://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/
2. Imprimiendo la subsecuencia creciente de longitud máxima (longitud y subsecuencia ambas)
   Esperaba la forma optimizada pero solo podía escribir código para el enfoque O (n ^ 2). Acabo de mencionar sobre el algoritmo de clasificación de paciencia que puede resolver este problema en tiempo O (N log N).

Después de esta pregunta, me preguntó si tenía alguna pregunta para él. Después de discutir, me pidió que esperara el resultado. Vino HR y me dijo que tengo que esperar a la segunda vuelta. Después de unos 40 minutos, me llamaron para la segunda ronda.

Ronda 3:

El entrevistador no perdió tiempo y saltó directamente a DS y algoritmos. No se hicieron preguntas del currículum en esta ronda.
Me hicieron las siguientes preguntas: –

1.  Dada una array de n elementos, debe satisfacer la siguiente propiedad a < b > c < d > e < f > g 
   Observé que los elementos con índices pares deben ser menores que sus vecinos, mientras que los elementos con índices impares deben ser mayores. Le dije un enfoque ingenuo de O (N log N)
   . Podríamos poner elementos en un maxHeap y luego, uno por uno, hacer estallar y llenar los índices impares primero y luego los índices pares. No estaba satisfecho con la complejidad.
   Quería una solución de complejidad de tiempo O(n). Después de pensar durante unos 5 minutos, le pedí una pista. (Dijo tipo burbuja). También estaba pensando en intercambiar
   elementos adyacentes y obtuve la señal verde una vez que escuché esto de él. Le dije que si el elemento actual no cumple con las reglas, lo cambiamos con el siguiente elemento.
   Escribí el código y él pasó por algunos ejemplos. Quedó satisfecho y pasó a la siguiente pregunta.
2.  Me pidió que implementara un caché LRU (indirectamente)
   https://www.geeksforgeeks.org/lru-cache-implementation/
   Me pidió que implementara el mecanismo para obtener tres videos reproducidos recientemente para un usuario, de modo que si un usuario reproduce un nuevo video y que no está en la lista de reproducción reciente, el primero se elimina de esta lista y se convierte en el último. Inmediatamente le dije que esto parece un caché LRU. Me preguntó qué estructura de datos usaría para resolver este problema.
   Le dije un mapa desordenado con una lista doblemente enlazada. Preguntó qué almacenarían el mapa y la lista. Después de discutir el enfoque, me pidió que escribiera el código para la función de inserción.
   Después de que escribí el código, me preguntó si había usado específicamente la función de eliminación de escritura de listas doblemente enlazadas para una lista doblemente enlazada, dado un puntero de Node.
3. Dado un puntero a un Node de lista doblemente vinculado, elimine el Node.
   https://www.geeksforgeeks.org/delete-a-node-in-a-doubly-linked-list/
   Escribí el código y me pidió que revisara algunos casos extremos. El código era correcto, por lo que pasó rápidamente a la siguiente pregunta.
4.  Diseñe una estructura de datos personalizada que admita operaciones de inserción, búsqueda, eliminación y obtención aleatoria en tiempo O(1).
   https://www.geeksforgeeks.org/design-a-data-structure-that-supports-insert-delete-search-and-getrandom-in-constant-time/
   Me tomé un tiempo para pensar en el enfoque y di la acercarse a él. Incluso me ayudó cuando me quedé atascado. Le dije que sería bueno un mapa desordenado y una array de tamaño variable.
   Me pidió que escribiera el código para la función de eliminación. Escribí el código y me preguntó si estaba cometiendo algún error. Miré de nuevo y encontré un error. Lo corregí y luego quedó satisfecho.
5.  Dada una array de 0 y X, donde 0 representa agua y X representa tierra, encuentre el tamaño máximo de la isla continua. Le dije que haría esto usando BFS.
   Me preguntó qué almacenaré en la cola y cómo mantendré el tamaño de la isla. No tuve que escribir el código para esto. Quedó satisfecho nada más escuchar el acercamiento. Después de esto, me preguntó si tenía alguna pregunta para él. Le hice algunas preguntas sobre el trabajo en Amazon. Discutimos durante unos 10-15 minutos y luego dijo que la entrevista había terminado. Sabía que esta era la última ronda. El HR me dijo que me enviarían el resultado por correo y les di la mano a las entrevistas antes de irme. Recibí el correo de que soy seleccionado como pasante solo un día después de la entrevista.

   Consejo: siempre que esté atascado, intente hablar con el entrevistador sobre lo que está pensando y dónde está atascado. Me quedé atascado en la Pregunta 4 en la ronda 2 mientras usaba una lista o array vinculada. Me pidió que me concentrara en el enfoque de array. Cuando eso falle, no se avergüence de pedir una pista. El entrevistador le dará una pequeña pista y podrá aprovecharla.

   Veredicto: ¡¡¡SELECCIONADO!!!