Amazon Entrevista Experiencia SDE-1 | Feb 2020 ( Exp 1.5 año )

Hola, chicos !
Les comparto mi experiencia de entrevista con Amazon para el puesto SDE-1 en febrero de 2020.

Ronda 1:
Bueno, la primera ronda fue una prueba de evaluación en línea en AMCAT. Había dos preguntas de codificación que debían completarse en 90 minutos.

1. Dada una array bidimensional de 0 y 1, donde 1 representa una persona infectada y 0 representa una persona no infectada. Después de cada segundo, una persona infectada infecta a sus 4 vecinos no infectados (L, R, U, D). Necesidad de calcular el tiempo tal que todo se infecta.
   Enfoque: aplicar BFS
   similar a:  naranjas podridas
2. Dada una array bidimensional de 0 y 1, donde 1 representa un componente de construcción y 0 representa un área vacía. Necesitamos calcular el número total de componentes de construcción conectados.
   Enfoque: Aplicar DFS
   similar a:  Número de islas

Las siguientes tres rondas fueron en el sitio en la ubicación de Gurgaon.

La ronda 2: 

Esta ronda comenzó con una breve introducción sobre mí y mi trabajo en la empresa anterior, seguida de dos preguntas de codificación:

1. Dada una string, diga «ABAABCD». Calcule el número mínimo de letras que se eliminarán de modo que las letras restantes puedan formar una string palíndromo.
   La respuesta para «ABAABCD» es: 2
   Explicación: elimine C y D, la string restante es: «ABAAB», que puede formar un palíndromo (BAAAB)
   Enfoque: simplemente cuente la cantidad de caracteres impares. Dado que puede mantener un carácter impar, la respuesta será el carácter impar -1. Usé HashMap para almacenar caracteres y su conteo.
   if(caracteres_impares==0) ​​devuelve 0;
   devuelve personajes_impares-1;
2. Dadas dos Linkedlists en orden creciente. Combinarlos en orden decreciente. Debe fusionarse en su lugar, no puede crear una nueva lista vinculada.
   Enfoque: simplemente aplique el concepto de clasificación por combinación y agregue caracteres al principio de la lista combinada en lugar de al final.
   Fusionar en orden creciente:  fusionar dos listas enlazadas ordenadas

Ronda 3:

Esta ronda también comenzó con una breve introducción sobre mí y mi trabajo en la empresa anterior, seguida de dos preguntas de codificación:

1. Dada una array ordenada de 0 y 1 en orden no decreciente. Encuentre la suma de la array en O (log n)
   Enfoque: aplique la búsqueda binaria para encontrar la posición del primer 1 y devuelva la posición n + 1.
2. Dada una array de enteros, encuentre y reemplace el siguiente elemento más pequeño de cada elemento en la array dada en O (n).
   Enfoque: use Stack.
   Pasos :
   Inserte el elemento comenzando desde atrás.
   Si la parte superior de la pila es mayor que el elemento actual, continúe eliminando hasta que se encuentre el elemento más pequeño o la pila quede vacía.
   if Stack –> Respuesta vacía para el elemento actual =-1
   else respuesta para el elemento actual= stack.peek();
   Inserte el elemento actual para apilar y repita las 3 líneas anteriores. Además, me preguntó algunos conceptos del sistema operativo y algunas preguntas relacionadas con el trabajo anterior.

Ronda 4:

Esta ronda también comenzó con una breve introducción sobre mí y mi trabajo en la empresa anterior, seguida de dos preguntas de codificación. También me preguntó sobre mi proyecto actual, me preguntó profundamente sobre el enfoque que usaba para resolver los problemas que enfrentaba.

1. Dado un número n que representa el total de escaleras. Encuentra de cuántas maneras puedes llegar al enésimo escalón con 1 o 2 escalones a la vez.
   Aproximación: DP
   Dado que para llegar a 0, número de vías = 1;
   para llegar al 1º, número de vías = 1 (0->1);
   para llegar al 2º, número de vías= 2 (0->1->2 | 0->2)
   para llegar al 3º, número de vías= 3
   Por lo tanto, podemos ver, para llegar al enésimo escalón, número de vías= vías para llegar a ( n-1)th +maneras de llegar a (n-2)th.
   Enlace:  Nth Stair Además, me pidió que expandiera este problema con k-pasos (k pasos al máximo que se pueden tomar):
   Es simple nuevamente, solo necesito agregar valores k anteriores para obtener formas de llegar a una escalera en particular.
2. Dado un árbol de búsqueda binaria (BST), encuentre la vista superior de BST dado. Enfoque: mantenga tanto la distancia horizontal como el nivel para cada Node.
   Cree un TreeMap<Integer, Pair> que almacene la distancia horizontal y un objeto de clase de par. (Nota: TreeMap ya está ordenado según la clave, es decir, la distancia horizontal)
   Aplique el recorrido en orden según lo siguiente: void topView (Node root, int hd, int level)
   {
   if (root==null)
   return;
   if(map.contains(hd))
   {
   if(map.get(hd).level<level)
   map.put(hd, new Pair(root.data, level));
   }
   else
   {
   map.add(hd, new Pair(root.data, level));
   }
   topView(root.left, hd-1, level+1);
   topView(root.right, hd+1, level+1);
   }Simplemente imprima Pair.value para cada clave en TreeMap.class Pair{
   int value;
   nivel int;
   Par(int a, int b)
   {
   valor=a;
   nivel=b;
   }
   }

Ronda 5:

Esta fue la ronda final de una hora que se llevó a cabo en Chime Video Call:

1.  Me preguntó lo más difícil que he hecho en el último año y medio y mis preguntas relacionadas con el trabajo anterior.
2. Un número está representado por una LinkedList, donde cada Node representa un dígito del número. Te dan dos de esos números, encuentra la suma de dos números. Debe devolver el encabezado de LinkedList que representa la suma de dos números dados.
   Enfoque: Primero respondí invirtiendo ambos y luego sumando cada dígito y reenviando el acarreo. Y finalmente invirtiendo la LinkedList final.
   En segundo lugar, le di otro enfoque usando Stack.
   Finalmente le di un enfoque recursivo y me pidió que resolviera usando el mismo.
   Enlace:   Suma de dos LinkedList

Finalmente recibí una llamada de recursos humanos que me seleccionaron para el puesto SDE-1.
Tenga en cuenta los siguientes puntos que he usado durante mi entrevista:

R. Siempre responda si sabe algo más, simplemente diga «No lo sé, señor/señora».
B. Para las preguntas de codificación, comience con un enfoque de fuerza bruta para optimizarlo.
C. Mientras escribe el código, asegúrese de cubrir todos los casos extremos solo usted mismo. Puede ejecutar en seco su código antes de finalmente decir que ha terminado.
D. Debe ser capaz de calcular la complejidad del tiempo y el espacio.

Practique más para todos los conceptos de estructura de datos y algoritmos en GeeksForGeeks, encontrará todos los conceptos en este lugar.

Artículo presentado por: Ripesh Yadav