Experiencia de la entrevista de DE Shaw | Conjunto 16 (en el campus para prácticas)

Primera preselección basada en CGPA >= 7.5 y ÚNICAMENTE estudiante de CSE autorizado a sentarse en la entrevista. Ellos (DE-Shaw) tenían 2 fases de procedimiento de selección.

ENTREVISTA TÉCNICA:

Primero me pidieron que me presentara y me preguntaron mi interés. Les hablé de mí y mencioné mis áreas de interés como Estructura de datos y algoritmos. Luego comienzan una discusión sobre DSA.

P 1). Implemente Stack usando dos Queue .

P 2). Implemente Queue usando dos Stack.

Ambas preguntas son bastante fáciles, PERO debe saber a fondo cómo implementar y qué acción debemos tomar en la consulta particular y el código de trabajo también.

Luego me pidieron que escribiera código para ambos problemas y analizara la complejidad del tiempo de cada operación.
(Consejo: lea este libro Estructuras de datos y algoritmos simplificados – Narasimha Karumanchi para comprender a fondo los conceptos básicos de la estructura de datos…)

Después de esto, me preguntaron sobre mi proyecto (basado en el sistema operativo) y me hicieron la siguiente pregunta:
1). ¿Qué has hecho en tu proyecto que no está presente antes?
2). ¿Cómo puede afectar a una aplicación del mundo real?
3). ¿Qué dificultades enfrentó en su proyecto?
4). ¿Cómo se puede implementar en Real-Time OS?
…… muchas más cosas al respecto.
E hizo muchas más preguntas sobre el sistema operativo.

(Consejo: no mencione el proyecto en el que su contribución es muy inferior o no sepa completamente sobre ese proyecto. No esperan mucho proyecto de los pasantes, PERO quieren saber cuánto esfuerzo pone en su proyecto y qué tan bien conoces tu proyecto… Prepárate con todo….)

Por otra parte, hicieron una muy buena pregunta basada en algoritmos (paso a paso, aumentaron el nivel de dificultad).

Dijeron…
Tienes un tamaño de array con algún número entero. Debe devolver la suma del índice Lth al índice Rth de un elemento de array (inclusive).
Simplemente escribo una función que se ejecutará dentro del rango dado y devolverá la suma.
Complejidad temporal de cada consulta: O(RL)

Me pidieron que optimizara aún más esta solución… ya que no están contentos con mi solución.

Después de un tiempo, encontré una solución usando una array más, digamos cumm_Array en la que almacenaré la suma de todos los elementos del 1 al i-ésimo elemento indexado en cumm_Array[i]. Para cada Consulta devolveré (cumm_Array[R]-cumm_Array[L-1]).

No puedo dejar de escribir código porque me encanta programar……….

Aquí está el código:

//here all array is 1-Based indexed
  
int cumm_Array[size+1];
void cumm_Sum(int arr[],int size){
  
    int cumm_Array[0]=0;
  
          for (int i=1;i<=size;i++)
           cumm_Array[i]=arr[i]+cumm_Array[i-1];
}
  
int Query(int L,int R){
  
    return (cumm_Array[R]-cumm_Array[L-1]);
}

Complejidad de tiempo de cada consulta: O(1)
Complejidad de todos los tiempos: O(N*1)

Ahora me dijeron…tienes que hacer dos consultas.
Consulta 1). Actualice el elemento i al valor dado, digamos x
Consulta 2). Calcular la suma del rango dado

Ahora la pregunta se vuelve difícil.
(Sugerencias: esto se puede hacer usando el árbol indexado binario o el árbol de segmentos… no se preocupe si no sabe…

aquí está mi código…
Implementación del árbol de segmentos.
Implementación del árbol indexado binario.

Ahora Complejidad de tiempo para Consulta 1: O(logN)
Complejidad de tiempo para Consulta 2: O(logN)

Ahora me pidieron que escribiera un pseudocódigo para esto… He hecho esto… Después de esto, vi caras de ellos. Se ven impresionados porque no esperan que yo haga esas cosas… porque para resolver las dos primeras preguntas me tomó de 10 a 15 minutos cada una.

ENTREVISTA DE RRHH
En esta fase, nos preguntaron sobre nosotros, algunas preguntas habituales de RRHH. Después de esto, preguntaron algunos acertijos y muchas más cosas que solo se refieren a nuestra conciencia general.
Consejo: Sea fresco y atento.

Primero me dijeron: “Ahora estás en 2ª ^fase ”. Me preguntaron sobre la experiencia de la entrevista de la primera ^fase .

Después de eso, hicieron la primera pregunta basada en el problema real que requiere conceptos de estructura de datos.

P 1). Suponga que tiene que almacenar id_comprador, tiempo_compra, departamento, info_contacto_beyer. Diseñe una estructura de datos para almacenar esta información.

Ahora agregaron algunas cosas más a la pregunta para hacerlo más difícil. Dijeron: «Tienes que encontrar un comprador que haya gastado el máximo dinero en compras en cada intervalo de media hora en cada departamento». Nuevamente pidieron encontrar un comprador que gastara el máximo dinero de la lista de compradores seleccionados previamente.

Más tarde me pidieron que anunciara el ganador dado algunas limitaciones más. Esta pregunta fue muy pesada en todo el proceso de la entrevista.

Me pidieron que escribiera código (no pseudocódigo) para este problema rápidamente y analizara la complejidad del tiempo y la complejidad del espacio.

P 2). Diseñe un DFA para entrada binaria (string de 0 y 1) cuyo valor decimal sea múltiplo de 5.

P 3). Tiene dos números, digamos A y B. Tiene un rango dado, digamos [L, R], establezca todos los bits en B en un rango dado, donde todos los bits están configurados en A en ese rango. (No entendí, a veces mencionan cosas que parecen muy ambiguas, quieren saber cómo abordas este tipo de problemas… Si alguna vez te enfrentas a este tipo de situaciones… Pide más aclaraciones…)

No recibí una pregunta en absoluto. Se rieron de mi……….lol..Yo también me siento muy triste. Por fin, lo que me pasó.

Luego aclaran así…

Debe configurar todos los bits en la representación binaria de B que están configurados en A entre la posición L-ésima dada y la posición R-ésima en la representación binaria de A.

Luego les mostré un ejemplo… (Si no entendieron, vean el ejemplo).

A = 10(1010)
B = 13(1101)

[L,R] = [2,3]

bit position    1   ,2   , 3   ,4
               A     1    0     1    0
               B     1    1     0    1

Aquí puede ver entre el rango [2,3], A tiene el bit de 2ª ^posición no configurado, que está establecido en 2ª posición en B y el bit de 3ª posición de A no se verá afectado. Debe establecer un solo segundo ^bit de A

Respuesta final: A = 14(1110)

NOTA: no desconecte bits en A que ya estén configurados y no realice ninguna operación fuera de rango.
Solución:

La primera solución que les di, simplemente convertir A y B en binario y realizar la operación requerida como se menciona en la pregunta y recuperar el valor decimal de la respuesta.

Luego me pidieron que optimizara aún más diciendo que la computadora almacena toda la información en binario.

Estaba pensando que esta pregunta se puede hacer simplemente con XOR, ya que ya había resuelto un problema en bits.

Después de un tiempo, se me ocurrió una solución de complejidad de tiempo constante.
Diseño una máscara de bits que tiene todos los 1 en un rango dado y AND con B, finalmente OR con A;
Elegir dicha máscara de bits programáticamente no es tan difícil, por lo que se deja al lector.

LA MEJOR DE LAS SUERTES

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.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.