Experiencia de entrevista en Amazon | Juego 189 (para SDE-1)

Recientemente, me entrevistaron para el puesto de Amazon SDE-1. Hubo dos rondas telefónicas seguidas de 4 rondas F2F.

Ronda telefónica 1:
—————————
Parecía un poco desprevenido para la entrevista. Comenzó con una introducción y transferencia de conocimientos sobre el trabajo actual y luego creó un árbol binario y me pidió que escribiera el orden de nivel, el preorden, el postorden y los recorridos en orden para ese árbol.
Luego, siguieron las preguntas de codificación.

1) Aplanar una lista enlazada de varios niveles.
1er enfoque -> Usando una cola: T = O(n), S = O(n). Codificado.
2do enfoque -> Igual que en GeeksForGeeks < Aplanar una lista vinculada >: No me pidió que codificara. Pero este requiere cambiar la estructura de los datos.

2) Aplanar una lista enlazada de varios niveles, pero los Nodes en profundidad deben imprimirse primero. Entonces, básicamente, la primera pregunta se parece a BFS y esta se parece a DFS. Hice esto usando recursividad muy fácilmente.

3) Proceso vs Hilos. ¿Qué sucede cuando escribes una URL? Diseño de alto nivel. Protocolo de apretón de manos. Protocolo HTTPS, etc.

 
 
Ronda telefónica 2:
—————————
Debo decir que este tipo que me entrevistó era realmente inteligente. Esta ronda duró un poco más de 1 hora y hubo 3 preguntas.

1) BST a lista de enlaces únicos en su lugar. Una ligera modificación de este problema Coded it.

2) Encontrar Casillas en el tablero de ajedrez atacable por una torre
Hay un tablero de ajedrez NxN. Cada casilla del tablero de ajedrez puede estar vacía o tener una torre. Una torre, como sabemos, puede atacar tanto horizontal como verticalmente. Dada una array 2D donde 0 representa una casilla vacía y 1 representa una torre, tenemos que llenar todas las celdas de la array con 1 que representan casillas que pueden ser atacadas por cualquier torre presente en el tablero de ajedrez. Uno puede encontrar una versión mucho más simple de este problema aquí:
Problema de array booleana

3) Una serie de edificios está frente al sol. Las alturas del edificio se dan en una array. Tienes que decir en qué edificios verán la puesta de sol. Esto es bastante fácil. El primer edificio definitivamente verá la puesta de sol y para el resto de los edificios, simplemente mantenga una variable max_height_seen_so_far y verifique con la altura del edificio actual. Sin embargo, luego tergiversó la pregunta y preguntó cuál sería mi enfoque si tuviera que escanear los edificios de atrás hacia adelante en lugar de de adelante hacia abajo. Utilicé una pila y apliqué la lógica similar a la utilizada en el problema del siguiente elemento mayor.

 
F2F R1:
————–
Comenzó con la introducción. Muchas preguntas sobre la empresa actual, el trabajo actual, el proyecto actual y luego una pregunta de diseño.

¿Cómo diseñaría la función de invitación a reuniones de Microsoft Outlook? Teniendo en cuenta cada invitación a una reunión como un objeto y ese servidor web es el espacio de almacenamiento para las invitaciones, diseñe una estructura de datos para recibir y enviar invitaciones a los usuarios de manera eficiente. Los objetos de mensaje deben recibirse de forma ordenada en función de la hora de la reunión. Sugerí usar un árbol de búsqueda binario y justifiqué el uso de este DS. Di una solución O (NlogN). Luego me pidieron que lo codificara. Lo codifiqué en C#.

Seguido con muchas preguntas de recursos humanos.

 
F2F R2:
————–
1) Invertir una subarray en una array. Muy fácil.

2) Rotar un subarreglo en un arreglo donde se proporcionan los índices de inicio y final del subarreglo y se proporciona ‘k’, que es el número de rotaciones que se realizarán. El entrevistador se comportó realmente tonto en esta pregunta. Todo lo que quería era una solución. Me hizo ejecutar el código en seco una y otra vez y no estaba realmente preocupado por el concepto o el enfoque. No creo que pudiera identificarse con mi solución, que era O(n) en el tiempo y O(1) en el espacio.

3) Encuentra si una lista enlazada tiene un bucle. Vieja pregunta. Toma un puntero rápido y otro lento. Pero conseguir esta solución no era realmente su motivo. Preguntó por qué el puntero lento debe moverse un Node a la vez y por qué el puntero rápido debe moverse a la velocidad de dos Nodes a la vez. Siguiendo la guía de la discusión, se me pidió que encontrara las velocidades óptimas de los punteros lentos y rápidos para una lista enlazada dada. Nuevamente, guiado por la discusión, preguntó si se da que la lista enlazada tiene un bucle y se da el tamaño del bucle, ¿puedo encontrar las velocidades óptimas de los punteros lento y rápido?

 
F2F R3:
————–
1) La misma pregunta que Q3 se hizo en la ronda telefónica con la única diferencia de que las alturas de los edificios se proporcionaron en una lista enlazada. Lo codificó en C. Luego, el entrevistador tergiversó la pregunta colocando el sol después del último edificio (anteriormente el sol se colocaba antes del primer edificio). Usó una pila. Sin embargo, esto se puede hacer simplemente invirtiendo la array de alturas y usando la misma función escrita para la primera parte del problema.

2) Diseñar una estructura de datos para representar la jerarquía de empleados en una organización. Además, el diseño debe ser tal que pueda recuperar el no. de reportes de un gerente (no solo los reportes directos sino todos los empleados debajo de él) muy rápido (se esperaba O (1)). Además, la inserción de un nuevo empleado y la eliminación de un empleado también deben ser rápidas.

Sugerí usar un árbol n-ario de tablas hash. Además, usó una tabla hash adicional donde la clave era employeeId y el valor era la dirección de la tabla hash (o el Node) en el árbol n-ario. Mi solución dio no. de reportes en O(1) y la alta y baja de empleados fue en tiempo O(n), donde n es el número total de empleados. Sin embargo, no hubo suficiente tiempo para codificar.

 
F2F R4:
————–
Esta ronda tuvo muchas preguntas de recursos humanos. Información cultural. Proyecto actual. También hizo preguntas de codificación, pero en realidad no le preocupaba que la solución fuera óptima.

1) Se intercambian dos Nodes en un BST. Encuéntrelos _ Le dije a mi enfoque. No me pidió que lo codificara.

2) Imprime todas las permutaciones de una string en orden lexicográfico. Codificado. Me tomó muchos ensayos para hacerle entender que el código es correcto 😀

Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo electrónico a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.