Experiencia de entrevista de Microsoft | Juego 56 (para SDE 2)

Primera Ronda (F2F) 1 hora:
———————————-

1. Dada una imagen con muchos píxeles, encuentra todos los pares de píxeles que están fuertemente conectados.

2. Dado un árbol N-ario con miles de Nodes, empareje los Nodes hoja que NO COMPARTEN la ruta común. es decir, dos hojas se pueden emparejar solo si NO tienen un borde común que se haya utilizado en un emparejamiento anterior.

For example, 
       A
    /  |  \
   B   C   D
 /   / | \
E   F  G  H 
Leaf nodes: E, F, G, H & D

Possible Pairs in O/Ps:
                    a) (E-F), (G-H) or
                    b) (E-G), (F-H) or
                    c) (E-H), (F-G) or
                    d) (E-D), (F-G) or
                    e) (E-D), (G-H) or
                    f) (E-D), (F-H) or
                    g) (D-H), (F-G) or
                    h) (D-G), (F-H) or
                    i) (D-F), (G-H) 

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.

i.e. E-B-A-C-F —> (E-F) pair
       D-A-C-G —> (D-G) pair
       D-A-C-H —> (D-H) pair

Entonces el caso anterior NO es posible

Intenté usar un par de soluciones.
Más tarde usó la inducción matemática (según su sugerencia)
Básicamente, un emparejamiento para n = 2 Nodes de hoja es verdadero
Suponga que existe un emparejamiento para n = 2k Nodes de hoja (k> 0)
Ahora necesita probar que existe un emparejamiento para n = 2k+ 2 Nodes de hoja

Entonces, básicamente, solo tiene que ver los casos en los que puede insertar los nuevos Nodes de manera diferente
. Probablemente intentaré contribuir con un artículo sobre esto.

Se pidió código para ambas preguntas.

Segunda ronda (F2F) 45 minutos – 1 hora:
—————————————————
1. Dado un árbol y un puntero a algún Node en el árbol, imprima el elemento más a la izquierda en el mismo nivel que ese Node
2. Dada una string C, conviértala en su string ASCII. Ej: “CAR” -> “676582” (C-67, A-65, R-82)
Las condiciones son que lo tienes que escribir en C y lo tienes que hacer en su lugar.
3. Muchas preguntas sobre programas, comunicación entre procesos, pthreads, recolector de basura de Java, etc. que duraron alrededor de 20 minutos

Tercera ronda (F2F) 1 hora:
———————————
1. Invierta k-Nodes alternativos en una lista enlazada
2. Dadas dos strings s1 y s2, encuentre si existe una substring en s1 que contiene un anagrama de s2 (en O(n))
3. Dada una entrada de los objetos de calendario de 10 000 empleados de Microsoft, la entrada es un intervalo de tiempo T y una array de empleado[], encuentre el primer intervalo donde todos los empleados en el empleado[] la array está libre durante un intervalo de tiempo mínimo T (es decir, programar la reunión)
      Hice esta pregunta usando árboles B+ y un Hash, me dijeron que se pueden usar algoritmos de flujo máximo.

Gerente de Contratación de Cuarta Ronda (F2F) – 1 hora:
———————————————————-
1. Proyecto/trabajo previo
1. Diseño de los sistemas back-end de whatsapp: (deberíamos poder para manejar 1 millón de requests por segundo y transmitir datos con la menor latencia)
      había usado muchos conceptos de sistemas distribuidos como colas de mensajes, fragmentación, CDN, monitoreo, InnoDB/MongoDB, etc.

Se recomienda preparar preguntas sobre escalabilidad y sistemas distribuidos.

¡Este sitio me ayudó muchísimo y espero que otros también encuentren el trabajo de sus sueños!
Gracias frikis 🙂

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.