¿Cómo es la entrevista para los pasantes de Microsoft en 2014?
Al comienzo del semestre, me enteré de que Microsoft no tendría un seminario ni un centro de pruebas escritas en Xi'an este año, y pensé que Microsoft no planeaba reclutar gente en Xi'an. Luego vi en la web oficial que este año era una prueba escrita online. Envié mi currículum a finales de marzo y mi currículum chino está listo. En ese momento, pedí apresuradamente un currículum muy aproximado en inglés. Recibí la notificación para la primera ronda de exámenes escritos a principios de abril. La primera ronda de la prueba escrita dura 2 horas y contiene 4 preguntas de programación en inglés, que es más fácil que ACM. Lo que hice fue una lástima. Escribí un algoritmo N 2 para la tercera pregunta y solo obtuve 10 puntos. En ese momento pensé que no me importaría si excedía el límite de tiempo. Más tarde, escuché que un compañero de clase en la universidad escribió un programa N3 completamente violento y de hecho obtuvo 100 puntos en el examen. Tal vez si continuara revisando los errores en el programa, podría obtener al menos 300 puntos. La segunda prueba se divide en dos tipos de preguntas. Una es la prueba de habilidad matemática: son preguntas simples de matemáticas estadísticas, pero hay muchas preguntas que deben completarse en un minuto y algunas requieren una calculadora para calcular los resultados. El otro es la prueba de dominio del idioma: la escuela secundaria china no es muy buena, esto es lo que más temo. Probablemente sea como dar primero un segmento A y luego un segmento B. Según A, no es seguro si B está bien o mal, y el tiempo es escaso.
El 20 de abril recibí el aviso de entrevista, el día 24 era una entrevista online. Luego me conecté a Internet y leí muchos libros de caras de Microsoft.
El entrevistador de un lado es de JJ. Aunque sólo podía oír la voz de la otra parte, debería sentirse muy joven. Por un lado, Microsoft JJ es muy afable y le gusta reír, lo que reduce en cierta medida mi nerviosismo. Probablemente me presenté tan pronto como aparecí, y luego Microsoft JJ comenzó a hacerme preguntas: el primero me preguntó en general cómo comprobaría si el programa genera resultados incorrectos. Basándome en mi experiencia habitual respondiendo preguntas, dije que si envío las preguntas en do, comprobaré los posibles errores en el programa según el tipo de resultados devueltos, como WA, TLE o RE, balabala... (Creo que fui muy ingenuo y no supe cómo responder la pregunta de JJ en ese momento). Más tarde, JJ dijo, si los datos de entrada y el código del programa permanecen sin cambios, pero los resultados de ejecuciones repetidas son diferentes, ¿cuál puede ser la razón? (Para ser honesto, le tengo más miedo a este problema abierto que al algoritmo específico). Después de retenerlo durante mucho tiempo, hablé aproximadamente de varias posibilidades: el programa usa comandos new, malloc y otros para solicitar memoria dinámica, el programa llama a una función para obtener la hora del sistema, el programa lee datos de la red o archivo, y el programa utiliza un algoritmo aleatorio. Pero JJ siguió pidiéndome que hablara y luego no se me ocurrió nada más, así que mi hermana cambió la pregunta. Después del final, descubrí que había un subproceso múltiple clave y obvio que no se mencionó en ese momento (se estima que este punto se deducirá mucho).
Más tarde, a JJ se le ocurrió una pregunta específica: dada una cadena de caracteres chinos y una cadena Pinyin, cómo determinar si la cadena de caracteres chinos y la cadena Pinyin coinciden.
A primera vista, creo que es muy sencillo. Dije que primero debemos almacenar los datos de pronunciación de cada carácter chino y luego escanear los caracteres chinos y las cadenas pinyin de izquierda a derecha. Si uno no coincide, los dos no coinciden. JJ dijo que habría palabras polifónicas y de repente sintió que había vuelto a ser ingenuo. Dije, entonces busca. Si encuentra una palabra polifónica, no deje piedra sin remover. Si todo falla, regresa. Entonces JJ me preguntó la complejidad temporal aproximada de este método. Dije que, en teoría, la peor complejidad temporal sería exponencial, pero en realidad no debería haber tales datos límite. Se siente como escanear, porque si no soportas los caracteres multifonéticos, retrocederás rápidamente y no será demasiado profundo. Luego JJ me pidió que comenzara a escribir este código en la pizarra. Estaba confundido en ese momento. La pizarra equivale a txt sin la tecla de tabulación. Le pregunté a JJ si podía escribirlo en un IDE local y JJ dijo que sí. Leer datos no es la clave, por lo que escribí principalmente la función de búsqueda dfs. Mientras escribía, JJ también me pidió que saliera a comprar algo. Entonces JJ me preguntó la complejidad temporal del código. Lo que dije es similar al análisis de hace un momento. Lo peor es exponencial y el promedio debería ser O (n).
Luego dije algo no técnico y ese fue el final. Más tarde, durante la discusión con BW, descubrí que memorizar el código escrito por una matriz bidimensional puede evitar la complejidad exponencial teórica (normalmente escribo tantas preguntas de búsqueda memorizadas, pero no esperaba eso en la entrevista clave, tal vez JJ haya preguntado sobre la complejidad, espere a que hable sobre optimización). Con esta lección, definitivamente prestaré atención a pensar con más calma en futuras entrevistas. También pensaré en la intención del entrevistador al hacer cada pregunta y seré sensible a sus instrucciones.
El entrevistador de la segunda entrevista fue un GG. GG habla de manera ordenada, pero a veces la señal no es muy buena. Puedo sentir que GG ralentiza deliberadamente su discurso cuando habla de preguntas para que yo pueda escuchar con claridad. Las preguntas formuladas en ambos lados están relativamente fragmentadas. Es posible que algunas de ellas no se recuerden, así que simplemente escriba lo que recuerde.
Primero hizo una pregunta hipotética, es decir, existe una plataforma de publicación de noticias y como máximo un usuario puede enviar mensajes en cualquier momento y preguntarme cómo implementarla. Estoy un poco confundido acerca del núcleo de GG, pero no solo pregunto cómo evitar la exclusión mutua. Muerde la bala, dije que necesitas usar un candado para publicar información. Un usuario solo puede desbloquearlo después de enviar un mensaje, y el candado debe obtenerse antes de enviar el mensaje. Entonces GG cambió la pregunta sin decir nada. Pregunta siguiente: Hay una matriz de números enteros de longitud variable, cada número entero está entre 1 y 1000. ¿Por favor dime cómo copiar? Estoy secretamente feliz. ¿Cómo podría hacer una pregunta tan simple? Confirmé a GG que el núcleo de este problema es la deduplicación, no cómo manejar la longitud variable de la matriz, y luego le expliqué el método para crear una matriz bool con una longitud de 1000. La complejidad del tiempo es O (n) ( se ha alcanzado el límite inferior, no se puede optimizar). GG dijo que el método era correcto y luego me preguntó si había alguna forma de optimizar la complejidad del espacio. Confundido de nuevo, ¿se puede optimizar la complejidad del espacio O (n)? ¿Es O(1), O(0)? Más tarde, se dijo que el espacio se puede ordenar primero y luego copiar. El espacio se optimizó a O (0), pero el tiempo aumentó a nlogn. GG simplemente dijo que era una forma de optimizar el espacio y luego cambió la pregunta. (Hasta ahora, olvidé mi espacio de optimización de bits en ese momento. GG debe haber estado esperando este método cuando dijo que estaba optimizando el espacio. Vergonzoso).
Luego GG hizo una pregunta geométrica: dados dos triángulos, preguntó cómo determinar si los dos triángulos se superponen. Cualquiera que haya resuelto un problema simple de geometría computacional en ACM debería poder resolverlo en unos segundos. Luego hablé de mi propia solución; dividida en dos situaciones superpuestas:
Primero determine si hay anidamiento (determina si los tres puntos de un triángulo están todos dentro de otro triángulo). Luego hablé del método para determinar si un punto está dentro de un triángulo: calcular la suma de los ángulos dirigidos de este punto y tres segmentos de recta en el sentido de las agujas del reloj. Si la suma dentro del triángulo es 360 grados, entonces los puntos exteriores tendrán 0 grados.
En segundo lugar, si no hay anidamiento, entonces si dos triángulos se superponen, debe haber segmentos de línea que se intersequen. En este momento es suficiente determinar si los segmentos de línea se cruzan. Luego hablé sobre cómo juzgar la intersección de dos segmentos de línea: si dos segmentos de línea AB y CD se cruzan, entonces los puntos A y B deben estar a ambos lados de la línea recta CD, y los puntos C y D deben estar a ambos lados de la línea recta CD. la recta AB. La forma de determinar si dos puntos A y B están a ambos lados de una recta CD es multiplicar el producto cruzado de los vectores AC y AD por el producto cruzado de los vectores BC y BD. Si el resultado es negativo, A y B están a ambos lados de CD. Si es positivo, significa que al menos uno de ellos está en la recta CD. Posteriormente, GG confirmó mi método y cambió la pregunta.
En varios aspectos técnicos de Microsoft, parece que la redacción de programas in situ es indispensable. El último problema con GG bilateral es un problema de programación: el nodo raíz de un árbol binario se define como nivel 0. Escriba una función que ingrese la dirección del nodo raíz ym para implementar la tarea de guardar los datos del nodo m. Una pregunta recursiva muy básica. Después de escribirla y entregarla, GG dijo que sí y puso fin a ambas partes. El entrevistador del tercer lado sigue siendo un GG. Dijo que era de Xidian, no lejos de nuestra escuela. Dado que GG de Three Sides tomó la iniciativa de activar la función de video esta vez, también activé mi propia función de video para poder ver a la otra persona (en realidad, es mejor no activarla, porque ver a la otra persona Me pone más nervioso. Esta es mi opinión personal. GG también hizo algunos chistes, probablemente para que el entrevistador se relajara y se desempeñara bien. Pero parecía estar muy nervioso todo el tiempo (en ese momento sabía claramente que este sería un momento de vida o muerte para mí).
En los primeros diez minutos, charlamos un rato. GG me preguntó sobre algunos puntos de mi currículum y también habló sobre mi vida universitaria. Después de conversar más tarde, GG dijo que, según la práctica de Microsoft, los programas deben escribirse. Luego me preguntó si sabía multiplicar números grandes (esta es una herramienta relativamente básica en ACM). Dije que previamente había escrito una plantilla que usaba una matriz para simular un gran número de operaciones y símbolos sobrecargados como -*/. Luego dijo que esta vez escribiría una cadena para simular la multiplicación de números grandes. Dije que esto no fue escrito por mí, pero que debería poder escribirlo (me sentí realmente vacío en ese momento y tenía miedo de no escribir bien, así que casi me negué, pero sentí que negarme a escribir casi significaría siendo eliminado, así que acepté valientemente). Entonces tres GG me dio mi declaración de funciones, apagó la voz y dijo que me daría media hora para escribir, pero que siempre estuve bajo su supervisión. Probablemente hice un dibujo en una hoja de papel, lo descubrí y comencé a escribir. Me tomó unos 10 minutos completarlo, pero todavía no pude obtener el resultado. Algunos datos se ingresaron y generaron en código confuso y tomó más de 20 minutos obtener los resultados correctos. Después de que varios conjuntos de resultados de pruebas sean correctos, la entrevista se llama GG y listo. GG pidió enviar un correo electrónico. Pero hay un retraso en el envío de correos electrónicos. Dijo que, durante este retraso, primero déjame hablar sobre mi idea para el programa. Dije, blablabla. . . Más tarde, GG le preguntó por qué no había recibido el correo electrónico y su mente quedó confundida. Simplemente lo dijo sin enviar el correo electrónico primero. Fue demasiado vergonzoso, así que lo publiqué rápidamente. GG también sonrió y dijo que había cometido algo tan vergonzoso. Después de enviarlo, descubrí que el programa devolvió una cadena vacía cuando ingresé 0*0, así que la cambié rápidamente y la envié nuevamente. Más tarde, GG dijo que si venía a probar qué tipo de datos usaría mi programa, probablemente dije que usaría datos de límites como 0 (obviamente 0 * 0 estaba mal en este momento) y luego multiplicaría por números negativos (le dije GG que mi programa no maneja números negativos, pero es fácil de modificar, así que comencé a juzgar el signo y GG dijo que no importaba). Luego GG continuó preguntándome qué tipo de datos ingresaría, durante el cual la señal de sonido no era buena. GG también me pidió que siguiera escribiendo para agregar la respuesta a esta pregunta. Realmente no pensé en qué datos usaría (estaba pensando en probar algunos conjuntos de datos más, y debería ser más o menos lo mismo. Pero definitivamente no puedo decir eso). Más tarde, el entrevistador GG siguió citando y finalmente lo dijo él mismo: si ingresa datos como 0000000123456789 y luego los multiplica por otro número, habrá muchos cálculos inútiles en la función (nunca pensé en esto en ese momento). Tan pronto como GG lo dijo, sentí que me iba a arrodillar). Dije que sí, si existen dichos datos, deben procesarse eliminando el prefijo 0 al ingresarlos. Más tarde, GG no hizo ninguna pregunta durante la entrevista. Sólo me preguntó si tenía alguna pregunta. Pregunté tres veces y a los pocos días me notificaron el resultado. GG dijo que el departamento de recursos humanos me notificaría en aproximadamente una semana. Luego saludó y colgó.