Experiencia de entrevista en Amazon para la pasantía SDE (en el campus)

Evaluación en línea de Amazon. Entonces esta ronda se llevó a cabo en la plataforma llamada AMCAT. Las preguntas eran repetitivas y la mayoría de las cosas que se preguntaban estaban disponibles en Internet.

Así que esta ronda tenía 4 Partes:

1. depuración
2. Aptitud
3. conductual
4. Codificación

La ronda de codificación fue bastante simple, algunas preguntas que encontré fueron:

1. Cree una copia de la lista enlazada que contiene punteros aleatorios.
2. Busque en una array ordenada Fila -Columna.
3. Puente en un gráfico.
4. https://leetcode.com/discuss/interview-question/373006

Todas las preguntas estaban fácilmente disponibles en Internet.  

Entrevista Técnica 1: Aproximadamente 2500 personas dieron la primera ronda en línea y solo 161 estudiantes tuvieron la oportunidad de la entrevista. Así que mi entrevista se llevó a cabo después de una semana de la declaración del resultado de la ronda en línea.

Me uní a la reunión en Amazon Chime, el entrevistador me pidió directamente que me uniera a la plataforma de codificación en vivo en la que me dio mi primera pregunta de codificación.

Me dijo que le dijera un enfoque óptimo, y solo si está satisfecho con mi enfoque, se me permitirá escribir el código. Le comenté mi enfoque, aunque me dio algunos consejos para llevarme al enfoque correcto.

Pregunta 1: Dada la array nums de n enteros y un objetivo entero, ¿hay elementos a, b, c y d en nums tales que a + b + c + d = objetivo? Encuentre todos los cuatrillizos únicos en la array que da la suma del objetivo.  

Tenga en cuenta que el conjunto de soluciones no debe contener cuatrillizos duplicados.

Input: nums = {1,0,-1,0,-2,2}, target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Estaba basado en DP en árboles, el primer enfoque que le dije fue un enfoque de fuerza bruta. Quería que hiciera esto en O (N), así que en 4-5 minutos pude encontrar una solución. Así que tuve que codificarlos en 45 a 60 minutos, incluida la discusión sobre el enfoque y la complejidad del tiempo.  

En general, fue una experiencia increíble. Enfrenté estos problemas por primera vez y casi pude hacerlo bien. Fue una sensación increíble, Súper Satisfactoria.

Pregunta 2: Dada la raíz de un árbol binario, encuentre el valor máximo V para el cual existen diferentes Nodes A y B donde V = |A.val – B.val| y A es un antepasado de B.

    8
   / \
  3   10
 /  \   \
1    6   14
    /  \   \
   4    7   13

Entrevista técnica 2: Esta fue una gran ronda, aunque no pude desempeñarme bien. El entrevistador fue muy amable y solo observaba lo que estaba pensando mientras abordaba la pregunta.

Así que en esta ronda también me pidió directamente que me uniera a la plataforma de codificación en vivo. Luego me dio una pregunta para resolver, le pregunté si quería escuchar mi acercamiento a lo que su respuesta fue NO,  

Me dijo que está emocionado de ver cómo abordaré el problema. En esta ronda, ni siquiera esperaba un código adecuado sin errores, solo estaba interesado en conocer mi proceso de pensamiento y cómo abordaba el problema.

Pregunta 1: se le da una string de números, debe devolver una array de strings particionada en la que la substring (i-1) th + (i-2) th = i-ésima substring.  

Si no es posible, devuelva una array de strings vacía.

Por ejemplo:

Input:                  Output:
"111122335"   ------>   {"1","11","12","23","35"}  
Input:                  Output:
"112233"      ------->  {"11","22","33"}
Input:                  Output:
"11314"       ------->  {"11","3","14"} or {"1","13","14"}
Input:                  Output:
"13234113"     -------->{}

Así que di una solución de retroceso para la primera pregunta. La complejidad del tiempo era alta y no pude reducirla (aunque codifiqué la solución de retroceso correctamente).

Pregunta 2:

B, C, D reports to A
E, F, G reports to B
H, I report to C
J, K, L reports to H
M, N reports to K
O, P reports to J

Input:
Emp1: O
Emp2: M
Output:
C

Esta fue la segunda pregunta nada más se le dio. Tenía que averiguar qué tengo que hacer con esto.

Me dijo que tenía que diseñar una estructura de datos para contener toda esta información y hacer un programa adecuado para mostrar cómo iba a almacenar valores en la estructura de datos.

Después de eso, resuelva la pregunta para la entrada dada.

En lugar de A, B, C, D, etc., puede haber una identificación única para cada empleado y puede haber un número ilimitado de personas informando a una sola persona. Para la segunda pregunta, construí un árbol N-Ary para la solución, básicamente, la salida fue el ancestro menos común de los valores de entrada.

Así que hice un programa para toda la estructura con Entrada y Salida completas (Incluyendo cómo colocaré los datos dados en la Estructura de Datos).  

No pude reducir al tiempo la complejidad de la solución, me pidió que resolviera esto en O (1) u O (N).