Experiencia de la entrevista de Microsoft | Conjunto 108 (en el campus)

Ronda 1: Aptitud
Ronda 2: 2 preguntas de la estructura de datos

Ronda 3: Ronda de vuelo en grupo

1. Encuentre el ancestro menos común de dos Nodes en un árbol binario.
   Determine si el valor raíz actual coincide con uno de los valores clave. Si es así, se devuelve esta raíz. De lo contrario, el procedimiento se repite para los subárboles izquierdo y derecho. El Node que tiene una clave en el subárbol izquierdo y la otra clave en su subárbol derecho es el LCA. Si ambas claves se encuentran en el subárbol izquierdo, el primer Node cuyo valor coincide con uno de los valores clave es LCA. Del mismo modo para el subárbol derecho. La complejidad del tiempo es O(n). El entrevistador pidió optimización. Sugerí un mejor enfoque para BST.
2. Dadas dos arrays ordenadas (con elementos repetitivos), encuentre el k-ésimo número mínimo de ambas arrays.
3. Mantenga un índice para cada array, ambos inicializados en el primer elemento de su array respectiva. Repita k veces y en cada iteración encuentre el elemento mínimo entre los índices actuales e incremente el índice de la array que contiene el mínimo. Si los elementos son iguales, incrementa ambos índices. La complejidad del tiempo es O(k).

Ronda 4:

1. Dado un Node en un BST, elimínelo. El vínculo principal no forma parte de la estructura del Node.
   Si el Node es un Node hoja, elimine el Node.
   Si el Node tiene un hijo, reemplace el valor del Node con el valor del hijo y elimine recursivamente el hijo.
   Si el Node tiene dos hijos, encuentre el sucesor en orden, reemplace el valor del Node actual con el valor del sucesor en orden y elimine recursivamente el sucesor en orden.
   La complejidad del tiempo es O(h). El entrevistador sugirió una posible optimización para el caso de un niño, que la eliminación recursiva no es necesaria para un niño. Solo tenemos que copiar sus punteros secundarios izquierdo y derecho al Node que estamos tratando de eliminar.
   Artículo relacionado : Enlace GeeksforGeeks
2. Rompecabezas: hay nueve monedas, de las cuales una es defectuosa (diferencia en peso de las demás). Encuentre el número máximo de iteraciones para encontrar el defectuoso.
   Sugerí un enfoque de divide y vencerás, con un máximo de 5 iteraciones.

Ronda 5:

1. Discusión del proyecto
2. Un programa se ejecuta en un bucle infinito en el sistema. Si intentamos ejecutar otro buen programa mientras se ejecuta este bucle infinito, ¿se ejecutará el buen programa?

   Respondí que el programa se ejecutará, pero se reducirá la utilización de la CPU.

3. Escriba un código para implementar la función strtok() en C.
4. Mantenga un índice para representar el inicio del siguiente token, inicializado en 0. Busque la string linealmente, si se encuentra una coincidencia para el patrón, almacene la substring desde el índice de inicio hasta la posición anterior del patrón en una array de strings y actualice el inicio índice para el siguiente token. La complejidad del tiempo es O(n).
   El entrevistador quería saber por qué había usado malloc() en lugar de asignación estática.

Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.