Experiencia de entrevista de Microsoft para FTE

Ronda de codificación (60-65 minutos): 2 preguntas

1. Dada una array, seleccione el subconjunto más grande de modo que una operación para todos los elementos sea distinta de cero.
2. Dada una string y una array de costos asociada con cada índice de la string. Elimine elementos de la string de modo que no haya dos caracteres adyacentes iguales y encuentre el costo mínimo para construir esa string.

40 personas fueron preseleccionadas después de la ronda de codificación para las entrevistas.

Todas las rondas de entrevistas fueron en Microsoft Teams

Entrevista Ronda 1 (Media): El entrevistador fue útil. Primero, se presentó y me contó sobre su trabajo en Microsoft, y luego me dijo que me presentara.

Luego comenzó con una simple pregunta:

1. Dada una array de n enteros, todos los números son únicos excepto uno de ellos.
   • El número repetido se repite n/2 veces si n es par
   • El número repetido se repite (n-1)/2 o (n+1)/2 veces si n es impar
   • El número repetido no es adyacente a sí mismo en la array.

   Escriba un programa para encontrar el número repetido sin usar espacio extra

   Resolví el problema en O(n). Luego me pidió que lo resolviera en O(1) yo hice lo mismo y quedó contento con la solución.

2. Transportar los materiales

   Algunos materiales deben transportarse del lugar A al lugar B. Para transportar los materiales, se han proporcionado dos camiones. Suponga que cada camión tiene suficiente capacidad para transportar todos los materiales de una vez del lugar A al B. Desafortunadamente, algunos materiales tienen restricciones para apilarse con otros materiales en el mismo camión. Los materiales que no pueden ir juntos se proporcionan en pares.

   Escriba un programa para averiguar si todos los materiales se pueden enviar utilizando los dos camiones de una sola vez.

   Además, si es factible enviar de una sola vez, enumere los materiales que se envían en cada camión.

   Tenga en cuenta que solo hay 2 camiones.

   Al leer la pregunta, solo le dije que estoy sintiendo la implementación de gráficos con materiales como Nodes y pares de restricciones como bordes.

   Entonces solo tenemos que comprobar si el gráfico es bipartito o no.

   Me preguntó la complejidad y le dije que, dado que usaremos DFS, la complejidad del tiempo será O (n + m), n son Nodes y m son bordes

El entrevistador estaba feliz porque di la solución justo después de 1-2 minutos de leer la pregunta.

Ronda de entrevista 2 (media): después de mi presentación, comenzó con preguntas

1. Primero me preguntó sobre la memoria virtual y sus ventajas.

   Respondí correctamente y luego me preguntó con un ejemplo de cómo podemos ejecutar un juego de 1,5 GB en un dispositivo con 1 GB de RAM.

   La respuesta fue «sí» y la razón es la ventaja de la memoria virtual, pero puede ocurrir un retraso debido a las fallas de la página.

Luego me hizo una pregunta de codificación.

2. Recorrido por orden de niveles de un árbol binario pero en forma inversa, es decir, desde el último nivel hasta el primero.

   Eg:
        1
      2    3
    4  5 6   7
   
   Output:
   4 5 6 7
   2 3
   1

   Quería que usara una estructura de datos para lo mismo. Podemos ejecutar BFS usando Queue y para almacenar los Nodes en forma inversa podemos usar stack

3. La última pregunta de esta ronda fue el problema de entrelazado de strings (preguntas DP estándar). Me dijeron que escribiera la relación DP y el enfoque tabular.

   Le expliqué correctamente y quedó contento con la solución final.

Entrevista Ronda 3 (Mediana): Esta ronda/ronda final fue fácil pero el entrevistador fue estricto. El entrevistador me ayudó, pero quería que yo escribiera el código de manera eficiente, sin redundancias y en un formato adecuado. Primero, me preguntó cómo estuvo mi día y cómo ha ido el aprendizaje de forma remota.

Preguntas de codificación:

1. Encuentre el ancestro menos común de 2 Nodes en un BST.

   Pregunta simple pero hubo muchas condiciones que debemos aclarar con el entrevistador.

   ¿Qué pasa si ambos Nodes son iguales? en este caso, devolver el padre de ese Node

   ¿Qué pasa si ambos Nodes son iguales pero el Node es la raíz? devuelve NULL para este caso

   ¿Qué pasa si un Node es el padre de otro? devolver el padre del Node que era el padre de otro

   Con la discusión adecuada, pude codificarlo correctamente.

Veredicto final: Seleccionado

Consejos: tenga confianza y haga preguntas al entrevistador cuando se le pregunte.