Amazon Entrevista | Conjunto 28

Hola, recientemente me entrevistaron para el puesto SDE1 para Amazon, Hyderabad, pero no pude hacerlo. Aunque no fui seleccionado, fue una buena experiencia y GeeksforGeeks ha sido de gran ayuda.

Las siguientes fueron preguntas de la entrevista
: tuve una ronda escrita y una ronda telefónica antes de 4 entrevistas en persona en Hyderabad.

Ronda 1 (escrita):
había cuatro preguntas que debían enviarse en un lapso de tiempo de dos horas. Las preguntas fueron:
1. Dada una string de caracteres, mostrar los caracteres que aparecen más de una vez en esa string.
2. Rotar una array 90 grados a la derecha
3. Convertir un BST a DLL.
4. Encuentra el k-ésimo elemento más grande en un BST dado.

Ronda 2 (Telefónica):
1. La primera pregunta era sacar dos números de un BST cuya suma fuera igual a k . Lo respondí usando un recorrido de preorden para obtener una array ordenada y luego comenzar dos índices desde ambos extremos para encontrar si existen dos elementos con suma como k o no. Luego preguntó si se puede resolver sin usar una array o espacio adicional. Intenté resolverlo atravesando desde dos extremos del árbol en eoder y orden de pedido inverso y tomó algún tiempo codificar. La ejecución en seco del código parecía ser correcta, pero no estaba seguro. De todos modos, la mejor manera de no usar espacio adicional puede ser convertir el árbol en DLL (en el espacio) y usar la misma técnica que se usa en la array.

2. Para la segunda pregunta me preguntaron si había escuchado la pregunta antes o no. La pregunta era que se da una array con sus filas y columnas ordenadas y se debe buscar un elemento en esa array. Había escuchado la pregunta antes pero no la había resuelto y le dije lo mismo al entrevistador. Después de pensar por un momento, podría obtener un algoritmo comenzando en el elemento más a la derecha de la primera fila. Si el elemento es más grande, lo movemos hacia abajo o lo hacemos hacia la derecha. La solución estaba bien pero dudaba que lo hubiera resuelto antes.

3. Pidió escribir un programa para encontrar la raíz cuadrada de un número sin usar funciones de biblioteca. Yo lo había hecho antes y le dije lo mismo. Usé el método de Newton-rapson para obtener la solución, pero él la quería a través de algo parecido a la búsqueda binaria. Casi obtuve la solución, pero puede ser que me estaba quedando sin tiempo, por lo que dejó la pregunta solo allí y me pidió que dictara la solución del segundo problema.

Dos días después recibí una llamada de que había limpiado mi ronda telefónica y debo estar presente en Hyderabad para más rondas (cuatro). Los arreglos los hice mi Amazon y me presenté a las siguientes rondas el 27/4/2013 en su oficina de Hyderabad.

En el sitio:
Ronda 1 (Técnica):
1. La primera pregunta fue encontrar la suma vertical de un árbol binario. Le dije la solución usando y array/hash. Cada vez que nos movemos a la izquierda, disminuimos el índice mientras que al movernos a la derecha incrementamos el índice. Le pareció que la solución estaba bien, pero no se sentía muy cómodo con la indexación negativa. Entonces pidió otra solución usando una lista doblemente enlazada. Inicialmente, no lo entendía, pero cuando me dio alguna pista, estaba dispuesto a resolverlo, pero me llevó algo de tiempo cubrir los casos extremos. Con la solución final parecía convencido.

2. La siguiente pregunta era tener operaciones de pila de Push, Pop y FindMax en tiempo O(1) . Empecé a hacer esto usando solo un índice de variable máxima, pero me di cuenta de que necesitaba un índice máximo en todos los niveles, así que le di una solución usando dos pilas. Uno que tiene el elemento y el otro que tiene el índice máximo correspondiente. Parecía convencido con la solución.

Ronda 2 (Técnica):
1. En la segunda ronda había dos entrevistadores y casualmente uno de ellos era el mismo que tomó mi entrevista telefónica. La primera pregunta estaba relacionada con cómo elegir la lista de artículos ‘relacionados’ cada vez que se muestra un producto en el sitio web de Amazon. el problema era encontrar el producto menos relacionado para un producto dado. Inicialmente respondí usando el árbol n-ario, pero le dije que tendríamos entradas duplicadas. Pidió una solución optimizada, así que sugerí usar la tuerca de la lista de adyacencia y finalmente me di cuenta de que se puede resolver usando gráficos. Se convencieron y se les pidió que codificaran. Lo resolví usando una Cola, así que al atravesar una array empujamos los elementos en la cola con su nivel de relación. Estaban convencidos con la solución.

2. La segunda pregunta era eliminar un elemento de la lista doblemente enlazada. Lo resolví, pero me perdí un caso límite en el que el elemento que se eliminará no está presente en la lista. Agregué ese cheque más tarde.

3. En tercer lugar, para un BST dado, se invirtieron los signos de los elementos y finalmente se obtuvo un nuevo BST . Me hizo clic en la mente que después de la inversión de signos será un árbol espejo y dio la solución para el mismo.
Hasta este momento, los comentarios se veían bien.

Ronda 3 (Técnico-Gerencial):
1. El siguiente entrevistador era un tipo senior y me preguntó sobre mi trabajo. Le explicó detalladamente.

2. Más tarde me preguntó que para un árbol binario dado que tiene tres campos de dirección, es decir, izquierdo, derecho y bfs sucesor, los campos izquierdo y derecho están llenos y el campo sucesor debe ser llenado. Lo resolví usando el orden de nivel transversal con una cola, pero él quería una solución sin usar espacio adicional. Me estaba tomando el tiempo para resolverlo cuando me dio una pista sobre cómo hacer un seguimiento de los padres. Después de esta pista, pude resolverlo con pocas condiciones faltantes, pero con su intervención pude dar un código de trabajo (como él y yo miramos).

Ronda 4 (Técnico-Gerencial):
1. Hubo dos entrevistadores. La primera pregunta fue cuéntame sobre ti y tu trabajo.

2. Dada la array am*n, necesitamos encontrar la cantidad de formas en que un bot puede alcanzar el bloque (m-1,n-1) si el bot solo puede moverse hacia la derecha y hacia abajo comenzando desde (0,0). Le di una solución usando DP. Construya el árbol de recurrencia mostrando la solución final. No pidió codificar, pero pidió encontrar la relación de recurrencia. Me quedé atascado, no sé por qué. Supongo que esto fue el comienzo del declive. me dio algunas pistas y finalmente pude escribirlo, todavía.

3. Para un árbol binario dado y una clave, poda el árbol con todos los caminos (raíz a hoja) que tienen una suma menor o igual a k. Pude resolverlo con alguna pista. La solución parecía convincente.

Cuatro días después, recibí un correo electrónico que decía: “ Desafortunadamente, no podemos continuar con su candidatura en este momento. Sin embargo, sus credenciales son extremadamente impresionantes y deseamos conservar sus datos en nuestra base de datos activa. Nos pondremos en contacto con usted tan pronto como se presente otra oportunidad similar .”

Este artículo está compilado por Rohit. 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.