Mi currículum fue enviado a Microsoft a través de una empresa de consultoría. Me llamaron para un proceso de entrevista de un día de duración en Microsoft IDC, Bangalore.
Ronda 1 (1 hora o más):
Pregunta 1: https://www.geeksforgeeks.org/median-of-stream-of-integers-running-integers/
Primero le di el algoritmo de clasificación por inserción, me dijo que lo mejorara. Estuve atascado durante algún tiempo, así que me dio otro problema: https://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/ . Pude resolver esto en unos minutos usando el método Min Heap, entonces me dijo que pensara de manera similar para la pregunta original que me dio. Después de alrededor de 20-30 minutos de lluvia de ideas, pude resolverlo usando el método Heaps.
Pregunta 2: https://www.geeksforgeeks.org/count-possible-paths-top-left-bottom-right-nxm-matrix/
Resolví esta pregunta bastante rápido. Me preguntó si me había encontrado con esta pregunta antes; No mintió, le dije que ya sabía esto.
Esto fue seguido por una discusión sobre lo que sucede en el Equipo Bing de Microsoft.
Ronda 2 (1 hora o más):
Pregunta 1: dado un archivo de texto grande, encuentre un algoritmo eficiente para encontrar la distancia mínima (medida en número de palabras) entre dos palabras dadas.
Resolvió esto usando hash; luego extendió el problema diciendo que este programa se ejecutaría una gran cantidad de veces (para encontrar distancias entre muchos pares de palabras), por lo que necesito mejorar mi algoritmo para que la complejidad del tiempo se reduzca después de la primera iteración de resolución del problema. Resolvió esto usando hashing y luego usando búsqueda binaria para encontrar el índice más cercano de la segunda palabra al índice de la primera palabra en el hash.
Pregunta 2: Primero dio información sobre cómo funciona la función de autocorrección en los teclados de los teléfonos, explicando que la probabilidad de la palabra autocorregida sería mayor que la palabra escrita. Me dijo que encontrara un algoritmo para encontrar la palabra más probable de longitud n que pueda ocurrir dado que hay m caracteres posibles. La probabilidad de que una palabra pueda ocurrir se da como: P(1.ª letra) * P(2.ª letra dado que la 1.ª ya se ha pulsado) * P(2.ª letra) * P(3.ª letra dado que la 2.ª ya se ha pulsado) …. y así sucesivamente. Todos los valores de los términos individuales en esta ecuación ya están dados.
Piense en el problema como una cuadrícula mxn donde cada elemento de una columna está conectado a cada elemento de la siguiente columna por algún peso. Resolver este problema por fuerza bruta sería O(m^n). Al almacenar las soluciones de los subproblemas, la complejidad se reduciría a O(m*n), que es la solución que buscaba el entrevistador.
Ronda 3 (1 hora): Ronda de gerentes de contratación: pregunta genérica pero un poco inesperada. Comenzó preguntándome sobre mis trabajos actuales y por qué quería cambiar, luego la conversación se centró en por qué había elegido un curso que no era de informática en mi licenciatura, la conversación tomó un camino completamente diferente sobre lo que pueden hacer las computadoras y qué la informática no puede hacer hasta que llegó hasta la máquina de Turing. Para ser honesto, estaba más nervioso después de esta ronda.
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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA