Experiencia de la entrevista de Microsoft | Set 100 (en el campus para pasantías en IDC y TI)

Microsoft visitó nuestro campus para selecciones de pasantías en IDC y perfil de TI. Hubo tres rondas para el proceso de selección del perfil IDC

Primera ronda: codificación de la ronda
3 Se hicieron preguntas en diferentes conjuntos. De los cuales las personas que resolvieron 2 y más están preseleccionadas. Las personas que resolvieron 3 fueron preseleccionadas para la entrevista personal, mientras que las que resolvieron 2 fueron preseleccionadas para la ronda de vuelo grupal.

Las preguntas fueron:

1. Se le darán edificios de cierta altura que se encuentran adyacentes entre sí. El sol comienza a caer desde el lado izquierdo. Si hay un edificio de cierta altura, todos los edificios a la derecha de él que tienen alturas menores no pueden ver el sol. Necesita encontrar el número total de esos edificios que reciben luz solar.
   Encuentre la subsecuencia creciente (no estrictamente) con el primer edificio como edificio inicial.
   Solución : Enlace GeeksforGeeks
2. Se le darán dos arrays de igual tamaño y deberá maximizar la primera array con los elementos de la segunda array (intercambie los elementos de la primera array con los elementos de la segunda array. Una vez intercambiados, ya no podrá usar el elemento)

   For ex: A: 3 4 6 8 9 and A : 5 7 3 6 8
   
   B : 6 7 8 8 9 B : 3 4 6 9 10
   
   Op: 9 8 8 8 9 Op : 10 9 6 6 8
   

   Solución : GeeksforGeeks Link
   Ordene la segunda array y comience a intercambiar si a[i] < b[i] . de lo contrario, espere el siguiente elemento de a que sea menor que b [i] e intercambie (procedimiento de combinación ingenuo)

3. Se le darán dos árboles t1 y t2. Debe verificar si t2 es un subárbol de t1 . Si es un subárbol, debe devolver el tamaño de t2 (número de Nodes en él).
   Si t1 o t2 son NULL, devuelve -1 .
   Si t2 no es un subárbol de t1, también devuelve -1
   La solución más eficiente fue:
   Cualquier árbol tiene 2 recorridos únicos. (Ya sea (preorder, inoder), (in, post), (post, pre)). Por lo tanto, atraviéselos y almacene dos recorridos para ambos árboles. Verifique el primer recorrido de ambos árboles ( Coincidencia de strings usando KMP O (N + M)) y de manera similar para el segundo recorrido. Si ambos resultan ser verdaderos (me refiero al patrón existe en el texto). Entonces ya está. De lo contrario, devuelve -1
   Esta Complejidad es O(N+M) y espacio O(N+M) . Si desea prescindir del espacio, intente con el enfoque recursivo que, en el peor de los casos, requiere una complejidad O (N * M)

Aparentemente, fui preseleccionado para la entrevista personal, por lo que no asistí a la ronda de Group Fly.

1. Encuentre la mediana de una array sin clasificar . Le dije que lo ordenara y lo encontrara según la paridad de N (par o impar). Solución NLogN. Me pidió que lo optimizara. Luego le hablé sobre la mediana de una array no ordenada en el método O(N) del peor de los casos… (puedes encontrarlo en gfg). Me preguntó si podía hacerlo usando Selección rápida… Le dije cómo hacerlo. y le sugirió que en el peor de los casos podría llegar a O(N^2). Me dijo que estaba bien y me pidió que escribiera el código. Mi código era un poco tedioso, pero finalmente pude obtener el código correcto.
2. Luego me preguntó sobre hash (enstringmiento y direccionamiento abierto: inserciones, eliminaciones, etc.) y mapas de c ++ y sus complejidades.