Amazon Campus Drive (para pasantías de un semestre)

Ronda 1: Prueba en línea (Duración: 2 horas 30 minutos)

• Tenía alrededor de 20 preguntas de opción múltiple relacionadas con los fundamentos de la informática y 2 preguntas de programación.
• Las preguntas de programación fueron:
  • 1) Encuentre la longitud de la substring más pequeña que consiste en el número máximo de elementos distintos .
  • 2) Encuentra el número de formas de denominar una cantidad dada usando monedas de 3, 5 y 10 .
• Alrededor de 30 estudiantes fueron seleccionados para la segunda ronda.

Ronda 2: 1ra ronda F2F (Duración: 50-55 minutos)

• Comenzó con el habitual «Cuéntame algo sobre ti». El entrevistador fue muy amable.
• Me preguntó acerca de varios tipos de estructuras de datos basadas en árboles y sus propiedades. (T, BT, BST, AVLT, etc.)
• Me pidió que escribiera una función que toma el Node raíz de un árbol como entrada, devuelve 1 si el árbol es un BST y 0 en caso contrario.
  • Le di un enfoque lineal con O(n) complejidad de tiempo y O(log(n)) o O(altura del árbol) complejidad extra de espacio de pila. Estaba satisfecho con eso.
• Me dio una array que constaba solo de 0, 1 y 2 y me pidió que la ordenara.
  • Le di el método de tipo de conteo con complejidad de tiempo O(n) y espacio adicional O(1). Me preguntó si podía hacerlo de una pasada.
  • Lo intenté durante un tiempo y, con la ayuda de algunas pistas, pude codificar un enfoque segregativo. Artículos relacionados ( QuickSort de 3 vías (bandera nacional holandesa) )
• Me dio una array extraña de tamaño N donde los elementos N-1 ocurren K veces. El elemento restante ocurre solo 1 vez. Encuentre ese elemento que ocurre solo 1 vez.
  • Le di una solución basada en hash con tiempo y complejidad extraespacial de O(n). Luego me preguntó cómo se implementan std::unordered_map y std::map debajo. Le informé sobre ellos. Luego me preguntó si podía resolver el problema en tiempo O(n) y espacio extra O(1).
  • Me dijo que pensara en términos de bits. Luego, tomando algunos ejemplos, pude llegar a la solución. Un ejemplo donde K = 3 ( Encuentra el elemento que aparece una vez )
• Luego me hizo algunas preguntas relacionadas con Gujarat (mi lugar natal). Que bueno es la comida, los lugares turisticos, los viajes y todo. Esta discusión se prolongó durante 10 minutos. Luego me preguntó sobre algunos buenos lugares para comer en Jaipur (mi universidad estaba en Jaipur). Di algunas sugerencias. Fue muy amable e incluso me dijo que te enviaría para la segunda ronda de F2F.

Ronda 3: 2da ronda F2F (Duración: 50-55 minutos)

• El habitual “Cuéntame algo sobre ti”. Le dije que era el mejor jugador de Counter-Strike de The Batch y estaba intrigado. Me preguntó si sabía cómo funcionaba el juego. Pude darle información satisfactoria.
• Me pidió que le informara sobre mi ronda anterior, cuáles fueron mis enfoques de las preguntas.
• Me preguntó sobre la idea básica de la programación dinámica. Me preguntó acerca de mis pensamientos sobre “¿Dónde? ¿y cómo? son gráficos útiles para abordar problemas del mundo real”.
• Me preguntó si conocía los árboles de segmentos y los árboles Fenwick o los árboles indexados binarios y sus implementaciones. No me pidió que los codificara.
• Me dio un gráfico en forma de array de adyacencia y una array A separada para los valores de los Nodes. Me dijo que transformara la array A de acuerdo con la siguiente transformación:
  • Los valores de los nuevos Nodes deben ser iguales a la suma del producto de la suma de los Nodes de valores impares y la suma de los Nodes de valores pares en el subgráfico de ese Node y el propio valor del Node. es decir (new_node_val = old_node_val + PRODUCT(SUM(Nodes de valor de Node impar en el subgráfico), SUMA (Nodes de valor de Node par en el subgráfico)))
  • A le dio un enfoque DFS simple. Me dijo que yo fui el primero que me dio la solución y quedo satisfecho.
• Me dijo que queremos responder consultas Q (Q <= 1e4). En cada consulta se nos dará un número N (N <= 1e4) y tendremos que devolver 1 si N se puede expresar como suma de potencias de números menores que X (X <= N). Además, cualquier potencia 1 no está permitida (de lo contrario, no tiene sentido resolver, ya que N siempre se puede expresar como N ^ 1). Por ejemplo, para N = 242 y X = 7: devuelve 1 (como 242 = 1^2 + 3^2 + 6^3 + 2^4).
  • Me dio una pista para ver cuántos números en total puedes usar para expresar N. Números totales = (2^2, 2^3, …… 2^(log2(N)), 3^2, 3^3 , ……, 3^(log3(N)), ……, X^2, X^3, ……, X^(logX(N))). Esto resultó ser muy pocos.
  • En este punto pude reducir el problema a encontrar un subconjunto con una suma dada (aquí N). Le di la solución DP y quedó satisfecho. Artículos relacionados Problema de suma de subconjuntos

• Se seleccionaron alrededor de 7 personas y me alegré de poder hacerlo. Resultó ser una gran experiencia de mi parte. Los entrevistadores fueron muy amables y serviciales.