Experiencia de entrevista de Microsoft | Conjunto 54 (para SDE)

Ronda 1 (45 minutos):
Cuéntame sobre ti.

1. Dada una array de strings con R , G y B como caracteres. Ordene la array de modo que todas las R estén primero, seguidas de Gs y seguidas de Bs. Hazlo en complejidad de tiempo O(n) . ( Código de papel )
   Por ej. array es:
       I/P: GGRBRBBGRBR
       O/P: RRRRGGGBBBB

Sugerencia: el mismo problema que ordenar strings de 0, 1 y 2.

Hecho usando la misma lógica que la de ordenar 0, 1 y 2 en poco tiempo. El entrevistador estaba feliz. *:) contento

2. ¿Puede hacer el mismo programa anterior usando la Lista de enlaces únicos (SLL) y la Lista de enlaces dobles (DLL) en una complejidad de tiempo O (n) ?

Hecho usando DLL cómodamente.
Pero al usar SLL me quedé atascado ya que tenemos que realizar un seguimiento del puntero PREV cada vez. Quería que se hiciera en UNA SOLA PASADA si era posible. No pude hacer esto para SLL.

Ronda 2 (1.30 h):

Cuéntame sobre los proyectos en los que has trabajado.

1. Multiplicación de arrays de 2 arrays. Ambas arrays están distribuidas en un grupo de Nodes. Y las arrays son de gran tamaño ( BigData ). ¿Cómo puedes multiplicar estas arrays de manera eficiente? Quería saber el enfoque solamente, pero no el código real.
(Me preguntó este problema distribuido, especialmente porque trabajé en la arquitectura distribuida de Apache Spark y Hadoop en mi proyecto. Por lo tanto, estaba muy interesado en verificar mi conocimiento en el dominio Distribuido y BigData).

Sugerencia: piense en términos de trabajos de MapReduce .

Mi enfoque : como sabemos que en la multiplicación de arrays, la fila i se multiplica con la columna j, la fila (i + 1) se multiplica con la columna (j + 1), y así sucesivamente hasta la fila (n-1) con ( m-1)ésima columna.

Asigne cada i-ésima fila a la j-ésima columna, (i+1)-ésima fila a (j+1)-ésima columna y así sucesivamente hasta (n-1)-ésima fila a (m-1)ésima columna.
La idea es hacer Claves como índice de FILA y Valores como índice de Columna.
Mientras realiza la operación de reducción , multiplique las filas y columnas respectivas utilizando las filas y columnas asignadas anteriormente. Debido a que, en general, en la operación de reducción de los trabajos de MapReduce, Spark/Hadoop trae todos los datos asignados a un servidor para realizar el cálculo y almacenar el resultado. Por lo tanto, en la operación de reducción, Spark/Hadoop traerá solo la fila y la columna asignadas mientras realiza la multiplicación real. NO necesitamos traer todos los datos de filas y columnas a la vez.

Este fue mi enfoque. Uno puede pensar en el otro enfoque también y compartir su mejor enfoque también.

Posteriormente, me preguntó sobre los trabajos de MapReduce con más detalles y me preguntó sobre Hadoop y la arquitectura distribuida (NameNode, DataNode, etc.). Algunas preguntas sobre Escalabilidad.

2. Dado un árbol N-ario con miles de Nodes en él. Emparejar (unir) los Nodes hoja que NO COMPARTEN la ruta común. es decir, dos hojas se pueden emparejar solo si NO tienen una ruta de intersección .

Por ejemplo,

       A
    /  |  \
   B   C   D
 /   / | \
E   F  G  H 

Nodes de hoja : E, F, G, H y D

Pares posibles en O/Ps:
                    a) (EF), (GH) o
                    b) (EG), (FH) o
                    c) (EH), (FG) o
                    d) (ED), (FG) o
                    e) ( ED), (GH) o
                    f) (ED), (FH) o
                    g) (DH), (FG) o
                    h) (DG), (FH) o
                    i) (DF), (GH)

Nota: Si emparejamos (unirnos), digamos, (EF) , entonces NO podemos emparejar ninguno de los (DG) o (DH) ya que COMPARTEN la ruta COMÚN de A a C.
Es decir, EBACF —> (EF) emparejar
       DACG —> Par (DG)
       DACH —> Par (DH)

Entonces el caso anterior NO es posible.

Además, si hay un número PAR de niños, entonces son posibles exactamente n/2 pares. En caso de un número IMPAR de Hijos, 1 de los Hijos quedará Sin emparejar .

Le he dicho que use BFS ya que atraviesa cada borde exactamente UNA VEZ . La idea era, mientras se realizaba el recorrido BFS, emparejar hijos de un Node visitante si ambos hijos son Nodes hoja.
Si el Node visitante tiene solo UN hijo (hijo izquierdo o solo hijo derecho), almacene este hijo en la array TEMPORAL (array de punteros a los niños).
Una vez que finaliza el recorrido BFS, empareje los niños restantes en la array TEMPORAL uno por uno.
Una vez más, NO estaba satisfecho ya que BFS funciona NIVELADAMENTE . Así que me dijo qué pasaría si algunos de los Nodes tienen un subárbol sesgado con miles de Nodes.
Me quedé atorado. 🙁

Me dijo que aplicara la Inducción Matemática .
Si podemos probar para el caso base que se pueden emparejar al menos 2K niños. Luego emparejamos y probamos para 2K+2, 2k+4, , , , , , 2K+n Childs también.
Estaba en blanco en los conceptos de MI. NO
fue capaz de resolver este problema. 🙁

Estaba tan impresionado *:) feliz con el enfoque de mi primer problema usando MapReduce. Estaba un poco satisfecho con el enfoque del segundo problema. Así que me enviaron a la tercera ronda.

Hora de comer. Muuuuy bien. La comida era tan buena. Realmente me gustó

Ronda 3 (50 minutos):

Había mirado rápidamente mi CV. Luego me pidió que le contara algo sobre los proyectos en los que he trabajado y en los que estoy trabajando. Como he trabajado principalmente en el dominio de Machine Learning y NLP , me hizo algunas preguntas sobre NLP . ¿Cómo escalará su proyecto actual?

1. Dada una oración, inviértala palabra por palabra .
   Por ejemplo,
      I/P: “Microsoft Azure es una de las mejores soluciones en la nube”
      O/P: “las mejores soluciones en la nube son Azure Microsoft”

   Tan fácil. Dado en GFG. 🙂
   Hecho en poco tiempo.
   Me pidió que lo hiciera en UN SOLO PASO . Como la solución requiere 2 PASES de la sentencia. (Primero para invertir cada palabra individual y segundo para invertir la oración COMPLETA).
   Quedó atascado. 🙁 Me tomó mucho tiempo pensar en esto. No pude hacer esto. Finalmente me hizo otra pregunta.

2. Detectar un bucle en una lista enlazada individualmente . *:) feliz
   Teniendo en cuenta el enfoque de GFG. Él era feliz.

3. Retire el bucle en SLL anterior.
Nuevamente dada la misma solución GFG. 🙂

Me han dicho que espere a la cuarta y última ronda.

Ronda 4 (Ronda de Diseño):

¿Qué sabes sobre computación en la nube ?
¿Sabe algo acerca de Microsoft Azure .

Diseñe un WindowsBox como el almacenamiento en la nube de DropBox .

Proporcione todos los servicios IaaS , PaaS y SaaS usando Arquitectura Orientada a Servicios (SOA) .
Han dado un diseño de muy bajo nivel. NO está a la altura de sus expectativas. Como NO he trabajado antes en la tecnología de la nube. 🙁
NO pudo desempeñarse bien en esta ronda. 🙁

Consejo :
    Prepárese para las preguntas de diseño y escalabilidad .
    Se puede ir a través de este enlace: https://www.quora.com/How-should-I-prepare-system-design-questions-for-Google-Facebook-Interview
    Mira este video. Es muy bueno.
    Buscan los conceptos básicos de estructuras de datos y algoritmos . (especialmente listas vinculadas y árbol)

Por último, GeeksForGeeks es la mejor fuente para todos. GFG realmente me ayudó mucho en la preparación.

Gracias 🙂

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.