Entrevista en el campus de Amazon Pune Pool

La campaña de colocación del campus del grupo de Amazon se llevó a cabo en marzo de 2019. Hubo un total de cinco rondas, la primera ronda fue una ronda de codificación en línea que se llevó a cabo en Hackerearth, seguida de tres entrevistas técnicas y una ronda técnica.

Ronda en línea

Hubo 2 problemas de codificación y 10 MCQ relacionados con el sistema operativo y DBMS.

Entrevista Técnica 1

Problema 1

Se le dan dos números enteros n, k y una array a de tamaño n. Halla la frecuencia de k en el arreglo a.

Solución

Mi primera solución fue codificar la frecuencia de toda la array en la array h y luego imprimir h[k]. La complejidad de tiempo y espacio son ambas O(n) en este caso. El entrevistador me pidió que mejorara la complejidad del espacio.

En mi siguiente solución, solo tomé un conteo de variables enteras y lo incrementé cada vez que ocurría k mientras atravesaba la array a. Esta complejidad espacial se reduce a O(1) y la complejidad temporal sigue siendo O(n).

Me dijo que si la array está ordenada y ahora también tengo que reducir la complejidad del tiempo. Simplemente podría usar las funciones lower_bound() y upper_bound() en C++ para encontrar la primera y última ocurrencia de k en el arreglo a. Ahora la complejidad del espacio es O(1) y la complejidad del tiempo es O(log(n)). Me dijo que escribiera el código.

En lugar de usar upper_bound() y lower_bound() directamente, pensé que sería mejor implementarlos. Entonces, escribí dos códigos de búsqueda binarios, uno para lower_bound() y otro para upper_bound(). Quedó satisfecho y pasó a la siguiente pregunta.

Problema 2

Cree un árbol de búsqueda binario a partir de un enlace ordenado.

Solución

Mi primera solución fue un árbol sesgado obvio. Quedó impresionado y le dijo que, de hecho, es una solución muy fácil y simple, pero que ahora quiere un árbol de altura equilibrada. Esta la solución . Me dijo que escribiera todo el código, lo cual hice un poco correctamente con su ayuda.

Entrevista Técnica 2

Mi segunda ronda estuvo a cargo de una joven muy bonita e inteligente. Ella me ayudó mucho, dándome sugerencias e ideas para mejorar mi solución.

Problema 1

Te dan un árbol binario y dos enteros k y d. Imprime todos los Nodes a una distancia de d de k.

Solución

Mi primera solución fue encontrar la distancia de cada Node desde el Node k usando LCA y luego imprimir solo aquellos Nodes cuya distancia es d. esta es mi idea La complejidad temporal de mi solución fue O(nlog(n)). Ella lo quería en
O(n). Ella me ayudó a construir toda la lógica y finalmente me dijo que escribiera el código.

Problema 2

Se le da una array a que consta solo de 0, 1 y 2. Tiene que ordenar la array.

Solución

Mi primera solución fue codificar la frecuencia de la array en un recorrido y luego completar 0, seguido de 1 y luego 2 en el segundo recorrido. Estaba satisfecha pero lo quería en un solo recorrido. Esta es la solución . Me dijeron que escribiera el código.

Entrevista Técnica 3

Esta fue más una discusión general sobre varios campos de la informática en lugar de una ronda de resolución de problemas.

Problema 1

Tiene dos archivos a.txt y b.txt que tienen dos números con hasta mil millones de dígitos. Tienes que calcular la suma de dos números.

Solución

Mi solución fue primero mover el puntero de archivo de ambos archivos al final y luego comenzar a agregar los dígitos y llevar y, en consecuencia, retroceder y almacenar el resultado en un nuevo archivo. Finalmente, cree otro archivo y guarde el contenido invertido del archivo de resultados anterior. Estaba satisfecho, pero luego restringió el recorrido hacia atrás. Dije que podemos usar la recursividad para devolver el acarreo. Preguntó si se puede usar alguna estructura de datos para este problema. Respondí con la lista vinculada, porque no se puede asignar una gran cantidad de memoria continua, pero la lista vinculada no usa memoria continua.

Problema 2

Se le da una cuadrícula de alfabetos. Tienes que imprimir las coordenadas de todos los puntos de partida desde donde se puede formar la palabra ‘AMAZON’. Puede moverse hacia arriba, abajo, izquierda y derecha.

Solución

Di una solución usando DFS y DP. Fue difícil de explicar, pero hice lo mejor que pude. Supongo que esperaba una solución más sencilla, pero quedó satisfecho. Me dijo que escribiera el código mi idea.

Técnica cum Bar Raiser Ronda

Me dijeron que diera una breve descripción sobre mí y mis proyectos. Me preguntó mi papel en el proyecto. Después de lo cual dio dos problemas para resolver.

Problema 1

Te dan un árbol binario y un Node k. Averigüe si el subárbol izquierdo de k es una imagen especular del subárbol derecho o no.

Solución

La idea era una modificación de esto .

Problema 2

Se le da una array de caracteres. Debe devolver una array de caracteres en la que cada alfabeto x esté presente min (frecuencia (x), posición de x en orden alfabético)).

Solución

Este fue un problema de implementación simple. Me dijeron que escribiera el código correctamente con clase.

Finalmente, se seleccionaron un total de 9 personas. De los cuales 6 eran del Instituto de Tecnología del Ejército de Pune . Tuve la suerte de ser uno de ellos.