Experiencia de entrevista en Amazon (en el campus para SDE-1)

Amazon visitó JIIT Noida para el proceso en el campus en 2019.

Ronda 1  (Ronda de codificación en línea: 90 minutos en HackerEarth):

Esta ronda constaba de 2 preguntas de codificación y 20 MCQ. El nivel de dificultad de las preguntas de codificación fue fácil y los MCQ evaluaron el conocimiento de los fundamentos de CS (SO, DBMS, CN, OOPS, etc.).

Las preguntas de codificación fueron:

1. Dado un número entero N. Tienes un número infinito de monedas de 3, 5 y 10 denominaciones. Imprime el número de formas en que puedes formar una suma de N usando las denominaciones de las monedas. Soln: Problema estándar de cambio de moneda DP .
2. Dados los beneficios de una empresa para N días y Q consultas. Cada consulta contiene dos números enteros L y R. Para cada consulta, imprima el número de días en los que la ganancia es mayor o igual a L y menor o igual a R. Soln: Ordene las ganancias y, para cada consulta, use binario busque para encontrar el límite superior para R y el límite inferior para L. Complejidad de tiempo: O (nlogn + Qlogn)

Algunos de los MCQ que puedo recordar:

1. Complejidad de tiempo para T(n) = 4T(n/2) + n^2 (opciones: O(n^2), O(nlogn) etc.)
2.  Dado: expresión de prefijo. ¿Cuál de las siguientes es la expresión posfija correspondiente?
3. Calcule la cantidad de fallas de página que ocurrirán, dado: el sistema operativo usa FIFO para el reemplazo de página, no de páginas por marco dado. Y el sistema usa x páginas en un orden específico, y luego algunas y páginas en orden inverso.
4. Propósito de Ping en redes.
5. Algunas preguntas sobre comandos SQL (agregar columna a una tabla, etc.)
6. En programación orientada a objetos, ¿cuál de los siguientes se usa para lograr el polimorfismo en tiempo de ejecución? Opciones: función de amigo, sobrecarga de operadores, sobrecarga de funciones, etc.)
7. Si una máquina clasifica x entradas en y segundos, ¿cuántas entradas clasificará en z segundos? Dado: la ordenación de burbuja se usa para ordenar.
8. Recorrido posterior al orden del árbol dado, cuál de los siguientes está en orden.
9. Preguntas sobre interbloqueos, semáforos, etc.
10. No de Nodes en un árbol binario completo con N hojas.
11. Aunque las preguntas fueron fáciles, el corte fue muy alto. De ~ 400 estudiantes, 30 pudieron completar esta ronda.

Ronda 2  (Entrevista presencial – 1 hora):

El entrevistador fue muy amable y empezó con “cuéntame sobre tus proyectos”. Parecía una formalidad, le di una respuesta muy breve y luego comenzó con las preguntas.

P1: imprime todos los tripletes en una array que suman un número k dado . El problema aquí fue que TODOS esos tripletes deben imprimirse. Por ejemplo, si la array dada es {1, 1, 1, 1, 2, 0} y k = 3, la salida debería ser: {(1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 2, 0), (1, 2, 0), (1, 2, 0), (1, 2, 0), (1, 2, 0)}

Empecé a pensar y estaba explicando mi proceso de pensamiento al entrevistador mientras pensaba. Primero, hablé sobre ordenar la array dada, luego, para cada elemento A[i] de la array, encontré todos los pares que suman kA[i]. Para encontrar los pares, fijé un puntero en A[i+1] y otro en A[n-1] (si n es el tamaño de la array). Tuve que modificar la solución para que se imprimieran todos los pares posibles, y el propio entrevistador dio 2-3 pistas para ello.

Complejidad del tiempo: O(nlogn + n^2) = O(n^2)

Espacio adicional: O(1)

Luego me pidió que codificara la solución, lo cual hice, y después de realizar un ensayo, envié la solución. El entrevistador me dijo que volviera a verificar mi código. Lo analicé, faltaba un caso, lo agregué y luego se convenció.

P2: Dada una array en la que para todo i, A[i+1] = ya sea A[i] + 1, o A[i] – 1. En tal array, encuentre un número k.

Respuesta: Se puede hacer en O(n) usando búsqueda lineal. Pero se puede optimizar realizando saltos. Por ejemplo, si k = 10 y el primer elemento es 5, podemos saltar 4 elementos porque el ^4º elemento puede estar en un máximo de 9. Y así sucesivamente…

Entonces el entrevistador modificó la pregunta. Ahora, A[i+1] = en el rango {A[i] –t, A[i]+t}.

Respuesta: se modificará el tamaño del salto.

Luego me pidió que codificara la solución, lo cual hice.

Me tomó aproximadamente 30 minutos por pregunta y llegué a las soluciones gradualmente con la ayuda de las sugerencias del entrevistador. Puede parecer contrario a la intuición, pero que el entrevistador dé pistas es una señal positiva (siempre y cuando puedas captar esas pistas y llegar a la solución a la que él quiere que llegues).

Ronda 3  (Entrevista cara a cara – 45 minutos):

Pregunta: Implemente el algoritmo de la aplicación dividida (algoritmo, no diseño del sistema). Transacciones dadas en el formato: A->B 45, lo que significa que A debe Rs.45 a B. Reduzca las transacciones al mínimo.

Empecé dibujando un gráfico de las transacciones y pensé que si detectamos todos los ciclos en el gráfico, podemos reducir una transacción por ciclo. El entrevistador me pidió que lo codificara, lo cual comencé a hacer. Luego me detuvo en el medio y me dijo que pensara en una solución diferente. Me dio una pista para pensar en cuánto monto neto debe/se le debe a cada persona. Usando esa pista, pude llegar a una solución codiciosa: formar dos conjuntos de personas, los que deben una cantidad neta y los que se les debe. Luego, de los que deben, seleccione uno y dé a uno de los que se deben. Pero no estaba seguro del orden en que debían elegirse los elementos de los dos conjuntos. Él insinuó que elijo los que tienen los valores más grandes. Traté de demostrarlo matemáticamente y luego procedí con la solución.

Complejidad de tiempo: O (nlogn)

Espacio extra: O(n)

Luego me pidió que codificara la solución. En la solución, había usado heapify y percolate-up como funciones para heap, también me hizo codificarlas.

Ronda 4 (Entrevista presencial – 1 hora):

Pregunta: Dado un BST, encuentre el k-ésimo elemento más grande. No se proporciona el tamaño del BST.
Respuesta: Usando el recorrido en orden inverso. Contador mantenido para realizar un seguimiento del número de elementos visitados.

Luego, el resto de la entrevista se basó solo en proyectos y mi pasantía. También me hicieron algunas preguntas subjetivas como «¿cuál fue el proyecto más desafiante en el que trabajaste y por qué?», ​​»¿qué tecnología te gusta más?», etc.

El entrevistador hizo preguntas detalladas sobre mis proyectos, pero como solo había mencionado proyectos simples que había hecho yo mismo, respondí todas las preguntas con confianza.

Ronda 5 (Entrevista presencial – 1 hora):

Había dos entrevistadores en esta ronda. En esta ronda hicieron muchas preguntas teóricas de Fundamentos de CS. No soy bueno con las materias teóricas y solo pude responder las preguntas parcialmente.

Algunas de las preguntas fueron: Discutir los semáforos y cómo funcionan, qué es la sección crítica, qué es la condición de carrera, cuál es la diferencia entre un subproceso y un proceso, qué es la programación, discutir algunos algoritmos de programación, explicar el funcionamiento de round robin Planificación. ¿Qué son las propiedades atómicas de las transacciones, discutir la normalización, 1NF, 2NF, etc.? ¿Qué es un servidor DNS? ¿Pueden dos servidores DNS comunicarse entre sí? ¿Qué sucede cuando escribimos una URL web, etc.?

En una pregunta, me dieron un segmento de código en JAVA y me preguntaron si la sección crítica se violará o no.

No sé cuánto conocimiento de Fundamentos espera Amazon, pero lo logré respondiendo solo algunas de estas preguntas. Pude responder con confianza algunas preguntas. Para algunas preguntas, di respuestas parciales, tanto como pude recordar. Para algunas preguntas, como el trabajo por turnos, las propiedades de los átomos, etc., no pude responder en absoluto.

La ronda no había ido bien hasta este momento, pero como los entrevistadores fueron muy amables, les pedí que me hicieran algunas preguntas sobre DS/Algo. Luego me pidieron que verificara si dos BST son iguales (es decir, tienen exactamente los mismos elementos, las estructuras pueden diferir).

Soln: almacene recorridos en orden de ambos árboles en arrays y verifique si las dos arrays son iguales.

Complejidad temporal: O(m+n), Complejidad espacial: O(m+n)

El entrevistador me dijo que optimizara el espacio y me dio una pista para pensar en alguna otra forma de realizar el recorrido en orden. Luego realicé los recorridos en orden usando la pila en lugar de la recursividad. Mantuve dos pilas y seguí eliminando los mismos elementos de ambas pilas, cuando aparecían en ambas. Y esta pila tendrá como máximo elementos O (logn) (o elementos O (altura)), por lo que se reduce la complejidad del espacio. Luego me pidieron que codificara la solución, lo cual hice.

Sugerencias:

• Comience con una solución de fuerza bruta y luego siga optimizándola todo el tiempo que pueda. Eventualmente, debe llegar a la solución optimizada, y está perfectamente bien si comienza con una solución muy simple y la optimiza gradualmente.
• Trate de probar cada parte de su lógica matemáticamente, no haga conjeturas alocadas. Si formula alguna hipótesis, no proceda con ella sin probarla.
• Aclare las preguntas del entrevistador, pregúntele el resultado de algunos casos de prueba aleatorios para asegurarse de haber entendido la pregunta correctamente.
• Practica escribir código en papel. Es muy diferente a escribirlo en tu computadora, ya que no puedes editar mucho en papel.
• Indique siempre la complejidad de tiempo y espacio de su solución.
• Realice simulacros antes de enviar su código al entrevistador.