Experiencia de entrevista en Amazon SDE (en el campus 2019)

Calificación: actualmente cursando BE Ingeniería Eléctrica y Electrónica.
Ronda 1: Después de la presentación general, el entrevistador me preguntó si era bueno con las arrays. Dije ‘Sí’ y luego me preguntó dos problemas sobre arrays/vectores y luego un problema sobre BST.
Problema 1 : dadas dos arrays (A y B), ¿puede decir si es posible intercambiar un elemento de A con un elemento de B y hacer que la suma de ambas arrays sea igual?
Responder: Ordene las arrays. Calcule la suma de ambas arrays y saque la diferencia de la suma. Si la diferencia es impar, no es posible hacer el intercambio requerido (devuelve 0), de lo contrario, si es par, (digamos que la diferencia es 8) divídalo por 2 (= 4) y luego recorra ambos arreglos (esto puede ser hecho por diferentes métodos: utilicé la búsqueda binaria con algunas modificaciones) y encontré un par que tiene una diferencia = 4. Si se encuentra, es posible (devuelve 1), de lo contrario, devuelve 0. 
Respuesta: Así es como le expliqué la solución. Después de un minuto de pensar, dije: “primero calcularemos la suma inicial de ambas arrays y luego sacaremos su diferencia. Si la diferencia fue impar, significa que no es posible hacer la misma suma intercambiando dos elementos. El entrevistador me preguntó por qué la diferencia debe ser pareja. Le dije que cualquier transacción resultante del intercambio de dos elementos siempre resultará en incrementos o deducciones iguales en el valor de la suma. Se convenció y me dijo que continuara. “Entonces, si la diferencia es par, la dividiremos por dos y luego tomaremos dos punteros para atravesar ambas arrays en paralelo. Entonces, sí, ayudará si también ordenamos las arrays para que podamos usar la búsqueda binaria. Si se encuentra un par, devolvemos 1; de lo contrario, devolvemos 0. 
Me dijo que escribiera el código para el mismo y lo hice mientras simultáneamente explicaba algunas suposiciones que estaba tomando para evitar casos de esquina por ahora y condiciones. (Como ambos vectores tienen elementos en ellos, y la suma de A inicialmente es mayor que B). 
Leyó el código y me preguntó algunas dudas que le expliqué muy bien y quedó convencido.
Problema 2 :  https://www.geeksforgeeks.org/coin-game-of-two-corners-greedy-approach/ 
Me dijo el enfoque de solución exacta y respondió con algunos ejemplos, pero no pudo encontrar una falla en eso. Preguntó qué pasa si el número de monedas inicialmente es impar. Le dije que el juego sería injusto en ese momento, pero él dijo, hagámoslo injusto, ahora, ¿cómo vas a ganar? Le dije que si la suma de los elementos impares ahora es mayor que los pares, entonces solo yo puedo ganar; de lo contrario, no es posible que gane en esta situación. Él respondió con algunos ejemplos, pero al final quedó convencido.
Problema 3: dado un BST, reemplace cada Node con la suma de todos los Nodes que son mayores que ese Node. reemplace el Node de valor máximo con 0. 
Respuesta: enfoque recursivo bastante fácil. Luché con dos soluciones defectuosas antes de presentar la tercera correcta.
duración : 1-1.5 horas.
resultado: seleccionado para la ronda 2.
Ronda 2: Entrevistador amigable y alentador. Me planteó dos problemas, uno de árbol binario y otro de vectores y matemáticas.
Problema 1: dado un árbol binario, imprima la profundidad máxima de un Node izquierdo (el Node debe ser un hijo izquierdo) (si el Node es hijo derecho del hijo izquierdo del Node raíz, entonces no contará como un Node izquierdo )
Me tomó algunos ejemplos para darme cuenta de cuál era la pregunta. Él mismo me dijo que aclarara la pregunta preguntando cualquier ejemplo, así que tomé diferentes escenarios y le pregunté cuál sería la respuesta en esos casos. Me dijo ¿cuál crees que debería ser la respuesta? Le dije las respuestas a los casos de juicio de acuerdo a mi comprensión del problema y finalmente concluí que había entendido el problema correctamente. 
Respuesta: Es un enfoque recursivo muy simple. Simplemente realice un seguimiento de maxDepth de todos los Nodes izquierdos. Para verificar si el Node es hijo izquierdo o derecho, simplemente pase un argumento entero mientras llama a la recursividad (digamos 1 para la izquierda y 2 para la derecha).
la función se verá así (C++)

int maxD;
 
void maxD(node* root, int direction, int depth)
{
    if (!root)
        return;
 
    if (direction == 1) // left child
    {
        maxD = max(maxD, depth);
    }
 
    maxD(root->left, 1, depth + 1);
    maxD(root->right, 2, depth + 1);
}

El entrevistador quedó convencido con mi enfoque y pasó rápidamente a la segunda pregunta.
Problema 2 : dada una lista de canciones y un generador de números aleatorios que genera cualquier número aleatorio de 1-INT_MAX, devuelve una lista de reproducción aleatoria (en su lugar)
Mi enfoque : lista de canciones = vector A;
tamaño int = tamaño A.();
intj=0; 

while (j < size()) {
 
    int I = randomGenerator();
 
    // To generate a random number within
    // bounds of array. the part with j will
    // be understood later
    I = I % (size - j);
    .
 
        swap(A[j], A[I]);
 
    j++;
}

El entrevistador estaba convencido por mi enfoque, pero tenía un enfoque diferente en mente y siguió cuestionando la estabilidad de esta solución y me dijo que hiciera un ensayo sobre ella una vez. Era correcto, así que no hizo más preguntas.
duración : 1 h aprox.
resultado  : seleccionado para la ronda 3.
Ronda 3: esta fue la ronda más difícil y el entrevistador fue duro y no tan amistoso. Me hizo dos preguntas que no pude responder, pero luché mucho y se fue con mis enfoques.
Problema 1 : dados dos números n y k. ¿Puede ‘n’ descomponerse usando ‘k’ potencias de 2? En caso afirmativo, devuelva un conjunto posible.
Ejemplo : n = 9, k=3 – respuesta: SÍ, 4+4+1 = 9;
No, no se puede hacer mediante la conversión binaria del número y luego combinando las potencias de dos allí (que probé al instante). No pude explicar el
problema de trabajo 2 : dados los vectores ‘n’ de diferentes tamaños y un número entero ‘k’, encuentre el conjunto máximo posible de 3 números de arrays distintas en las que la diferencia de max-min <= k. (una vez que encuentre un triplete, no se puede contar en otros conjuntos).
Era una pregunta complicada: usé clasificación, montones mínimos, tres punteros y otras cosas. Mi solución usó tres bucles anidados con clasificación individual en cada uno y creó un montón mínimo y tomó la diferencia cada vez y minimizó la diferencia de máximo-mínimo y aumentó el puntero mínimo de una array si la condición no cumplió o aumentó el puntero de todas las arrays si lo hizo Esto fue muy complejo y el entrevistador estaba confundido en cuanto a lo que estaba escribiendo. Me preguntó muchas veces cómo funcionará en cada paso. A veces expliqué mientras que otras veces yo también luché. Me preguntó sobre la complejidad de la solución, que pensé que era algo así como O(n*m^2*log(mn)) y no estaba convencido con nada de lo que acabo de decir. Me interrogaron lo suficiente como para creer que estoy fuera del proceso después de eso.
duración : 1.5-2 horas.
resultado : seleccionado para la ronda 4 !!! (tal vez no lo juzguen solo en función de su solución)
Ronda 4: esta fue principalmente la ronda del gerente de contratación.
Me pidió que me presentara, lo cual hice muy bien con mi respuesta preparada.
Luego me preguntó si tenía alguna debilidad o alguna crítica que recibí por algo el año pasado.
Después de eso, me preguntó sobre mis proyectos y mi experiencia en prácticas. Le dije honestamente lo que hacía y sabía y cuando me preguntó sobre cualquier cosa relacionada con los proyectos como la base de datos, le dije hasta qué punto hice el proyecto y lo usé y no conozco conceptos profundos de bases de datos. Me preguntó sobre mis actividades extracurriculares que había mencionado en mi currículum.
Luego preguntó qué estructuras de datos conocía. Le dije todas las estructuras de datos que conocía. Olvidé mencionar las listas vinculadas, así que al final dije «y sí, las listas vinculadas también» y luego me dijo que haría una pregunta sobre la lista vinculada. (No sé si había planeado que cualquier estructura de datos que diga al final será el tema de las preguntas, porque psicológicamente será nuestro punto débil 😛 y, de hecho, las listas enlazadas eran un poco mi debilidad). 
La pregunta era fácil y un problema de entrevista muy común: fusionar dos listas enlazadas ordenadas.
No conocía la solución de complejidad espacial O(1) antes, así que primero lo hice con arreglos, luego me preguntó si podía hacerlo en el espacio O(1). Entonces, después de un minuto de pensar, también pude darme cuenta de eso. Luego escribí el código y el entrevistador quedó satisfecho.
Duración : 20-30 minutos.
Resultado : SELECCIONADO.