Amazon Entrevista | Set 54 (Para Prácticas)

Hola todos. Aquí está mi experiencia de entrevista para una pasantía en Amazon.
Posición: Pasante de 2 meses
Número de rondas: 1 en línea + 2 PI (2 F2F)

Ronda 1: (90 minutos)
20 MCQ y 2 preguntas de codificación
Hubo 20 MCQ basados ​​en salida C, probabilidad, matemáticas básicas, OOPS, análisis de algoritmos y sistemas operativos.

Pregunta 1: Dada una lista enlazada, escriba una función para invertir cada k Nodes (donde k es una entrada a la función).
Ejemplo:
Entradas: 1->2->3->4->5->6->7->8->NULL y k = 3
Salida: 3->2->1->6->5-> 4->8->7->NULO.
Entradas: 1->2->3->4->5->6->7->8->NULL y k = 5
Salida: 5->4->3->2->1->8- >7->6->NULO.

Pregunta 2: dada una string que contiene palabras separadas por un número arbitrario de espacios. Escribe una función que devuelva una string que consista en la primera letra de cada palabra. (Nota: puede haber cualquier cantidad de espacios al comienzo de la string dada, al final de la string dada o entre palabras de la string.) Ejemplo:
Entrada
: ” este es un caso de prueba ”
Salida: tiatc
(Función Se proporcionaron prototipos y principal para ambas preguntas. Aunque muchas soluciones pasaron los casos de prueba iniciales, fueron rechazadas más tarde porque no satisfacían los casos límite).

Ronda 2: (cara a cara) (1 hora 20 min)
Pregunta 1: Dados dos números representados por dos listas enlazadas, escribe una función que devuelva lista suma. La lista de suma es una representación de lista enlazada de la suma de dos números de entrada.
Ejemplo

Input:
 First List: 5->6->3  // represents number 563
 Second List: 8->4->2 //  represents number 842
Output
 Resultant list: 1->4->0->5  // represents number 1405

Invertí las listas enlazadas y simplemente agregué los Nodes correspondientes junto con el carry. Luego me pidió que resolviera la pregunta sin invertir la lista. Luego resolví la pregunta de forma iterativa sin invertir las listas.
Luego, el entrevistador me pidió que escribiera un código recursivo para el mismo problema.
Después de eso, me pidió que modificara el código para que el acarreo en cada lugar se pasara por valor en lugar de usar punteros (que había usado en mi código).

Pregunta 2: código iterativo y recursivo para invertir una lista enlazada (cuidado con los casos de esquina: cuando la lista no tiene Nodes o contiene un solo Node)

Pregunta 3: escriba una función para verificar si un árbol binario es un subárbol de otro árbol binario (verifique todos los casos de esquina).
Lo resolví en O (n ^ 2) complejidad de tiempo. No me pidió que optimizara mi código.

Pregunta 4: ¿Qué estructura de datos usaría para llevar registros del mercado de valores?

Le pedí que aclarara el enunciado del problema.

Luego me preguntó: supongamos que tiene que mantener los valores de las acciones de varias empresas durante varios períodos y devolver el valor mínimo de las acciones de una empresa en particular durante un período de tiempo determinado.

Respondí árbol de segmentos (probablemente la respuesta correcta fue la estructura de datos de la cola).
Sin embargo, el entrevistador procedió con las preguntas en el árbol de segmentos.
Me pidió que escribiera un código para
a) Crear un árbol de segmentos
b) Realizar una consulta de rango mínimo en un árbol de segmentos
c) Actualizar el árbol de segmentos
Me pidió que analizara la complejidad del tiempo para construir el árbol de segmentos y realizar la consulta de rango mínimo en el árbol de segmentos.
Luego me preguntó: si va a mantener el valor de las acciones de una empresa durante los últimos 6 meses… entonces debe actualizar el árbol de segmentos todos los días eliminando un valor de las acciones e insertando un nuevo valor de las acciones. ¿Cómo lo harías tú?
Aquí me quedé atascado y no pude realizar la actualización en un tiempo mejor que O (n). (Sin embargo, al usar la cola, se puede realizar en el tiempo O (1)).

Finalmente me preguntó si tenía alguna pregunta.

Ronda 3: (cara a cara) (20 min)
Solo me hicieron una pregunta técnica en esta ronda.

a) Me pidió que hablara algo sobre mí y mis logros técnicos.

b) Cómo almacenar un árbol binario en un archivo y luego volver a leerlo. (No es necesariamente un BST)
Primero respondí que almacenaría el recorrido del árbol por orden de niveles.
Luego me preguntó cómo mantendría los Nodes en varios niveles (a lo que no pude responder). Entonces, cambié mi enfoque y dije que: almacenaría recorridos del árbol en orden y pre-ordenados desde los cuales el árbol original se puede recuperar fácilmente.
Pero luego me dijo que optimizara mi enfoque (ya que este enfoque requeriría el doble del espacio original para almacenar los datos en los Nodes). No pude optimizar más mi enfoque (sin embargo, el mejor enfoque fue usar paréntesis.

                                    A
                                      /   \
                                        B    C
                                        /   \
                             D      E

Si este es el árbol binario, entonces se puede almacenar como (A(B(D),(E)),(C)) en el archivo). c) Luego hubo
una discusión de 10 minutos sobre mi proyecto, los problemas que encontré y como los solucione.
d) Finalmente me preguntó si tenía alguna duda.
Pregunté sobre los proyectos de prácticas en Amazon y el uso de DBMS y NETWORKING en el mismo.
Comenzó elaborando todo el proceso de trabajo en Amazon y su experiencia laboral… la mayoría de las cuales apenas podía entender. También me dijo que tuviera un buen conocimiento de JAVA, ya que será necesario en algún momento durante los proyectos.

Finalmente me seleccionaron.

Muchas Muchas felicidades al autor. Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo electrónico a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.