When I started school, I learned that Microsoft didn't have a presentation and written test center in Xi 'an this year, thinking that Microsoft was not going to recruit people in Xi 'an. Later, I saw in official website that this year was an online written test. I submitted my resume at the end of March, and my Chinese resume is ready. I was in a hurry to ask for a very rough English resume. At the beginning of April, I received the notice of the first round of written examination. The first round of written test is 2 hours and 4 English programming questions, which is easier than ACM. What I did at that time was a pity. The third question wrote an algorithm of N 2, and I only got 10. At that time, I thought I would leave it if I exceeded the time limit. Later, I heard that a classmate in the college wrote a completely violent N 3 program and got a score of 100. I sighed. Maybe I kept checking bugs in the program and got at least 300 points. The second test is divided into two types of questions. One is the math ability test: they are all simple statistical math problems, but there are many problems that need to be completed within one minute, and some need calculators to calculate the results. The other is the language proficiency test: Chinese middle school is not very good, and I am most afraid of this. It is probably to give a paragraph A first, and then a paragraph B. According to A, whether B is right or wrong is uncertain, and time is tight.
On April 20th and 24th, I received an interview notice, which was an online interview. Then I read a lot of Microsoft face books online.
The interviewer on one side is JJ. Although he can only hear the other person's voice, he should feel very young. On the one hand, Microsoft JJ is very amiable and likes to laugh, which reduces my nervousness to some extent. I probably introduced myself as soon as I came up, and then Microsoft JJ began to ask me questions: the first one asked me in general how I would check if the program output the wrong result. According to my usual experience in doing problems, I said that if I handed in the questions in oj, I would check the possible bugs in the program according to the type of the returned results, such as WA, TLE or RE, balabala ... (I felt naive and couldn't figure out how to answer JJ's questions at that time). Later, JJ said, if the input data and code of the program remain unchanged, but the results of repeated running are different, what may be the reason? To be honest, I am more afraid of this open question than the specific algorithm. After holding back for a long time, I probably said several possibilities: the program applies for heap memory with commands such as new and malloc, the program calls a function to get system time, the program reads data from the network or files, and the program uses random algorithms. But JJ kept asking me to go on, and then I couldn't think of anything else, so my sister changed the question. After the end, I found that there was a key and obvious multithreading that I didn't say at the time (it is estimated that this will be deducted a lot).
Later, JJ gave a specific topic: give a Chinese character string and a pinyin string, and ask how to judge whether the Chinese character string and the pinyin string match.
At first glance, I think it's simple. I said that there should be data storage of each Chinese character pronunciation first, and then scan Chinese characters and pinyin strings from left to right. If one of them doesn't match, it means they don't match. JJ said there would be disyllabic words, and suddenly she felt naive again. I said, then search. If you encounter polyphonic words, do whatever it takes. If all else fails, go back. Then JJ asked me the approximate time complexity of this method. I said that the worst time complexity in theory would be exponential, but in fact there should be no such limit data. The feeling is to scan it, because the polyphonic words will go back soon if they can't stand it, not too deep. Then JJ asked me to start writing these codes on the whiteboard. I was confused at that time. Whiteboard is equivalent to txt without tab key. I asked JJ if I could write it on the local IDE, and JJ said yes. Reading in data is not the key, so I mainly wrote dfs search function. In the process of writing, JJ also said that I went out to do some shopping. Then JJ asked me the time complexity of the code. What I said is similar to the analysis just now. The worst is exponential, and the average value should be O(n). Then I said something outside the technology, and it was over. Later, in the discussion with BW, it was found that in fact, the code written by memorizing a two-dimensional array can avoid the theoretical exponential complexity (I usually wrote so many memorized search questions, but I didn't expect the key interview. Maybe JJ kept asking about complexity until I said optimization). With this lesson, I will definitely pay attention to thinking more calmly in future interviews, and I will also think about the intention of the interviewer to ask each question, and be sensitive to the interviewer's guiding direction.
The interviewer on the second side is a GG GG speaks in an orderly way, and sometimes the signal is not very good. I can feel that GG deliberately slows down when talking about problems so that I can hear clearly. The questions asked on both sides are rather broken, and some of them may not be remembered, so just write what you remember.
He first asked a hypothetical question, that is, there is a news release platform where at most one user can send messages at any time and ask me how to achieve it. I'm a little confused about the core of GG, but I'm not just asking how to avoid mutual exclusion. Crustily skin of head, I said to use a lock to publish information, a user can only unlock it after sending information, and must obtain a lock before sending information. Then GG changed the question without saying anything. Let's ask a question: There is an array of integers of indefinite length, and each integer is between 1- 1000. How to copy? I am secretly happy. How could I ask such a simple question? I confirmed to GG that the core of this problem is de-duplication, not how to deal with the indefinite length of arrays, and then I explained the method of creating bool arrays with the length of 1000, and the time complexity is O(n) (it has reached the lower limit and cannot be optimized). GG said the method was correct, and then asked me if there was any way to optimize the spatial complexity. Confused again, can the spatial complexity of O(n) be optimized? Is it O( 1), O(0)? Later, it was said that the space could be sorted first and then copied, and the space was optimized to O(0), but the time was increased to nlogn. GG only said it was a way to optimize the space and then changed the question. (So far, I have forgotten my bit optimization space at that time, and GG must have been waiting for this method when he said that he optimized the space. Awkward).
Then GG asked a geometric question: give two triangles and ask how to judge whether the two triangles overlap. Anyone who has done a simple computational geometry problem in ACM should be able to solve this problem in a few seconds. Then I said my own solution; Divided into two overlapping situations:
First, judge whether there is nesting (judge whether all three points of a triangle are in another triangle). Then I said the method to judge whether a point is inside a triangle: calculate the sum of the directed angles of this point and three line segments clockwise. If the sum inside the triangle is 360 degrees, then the outer points will get 0 degrees.
Second, if there is no nesting, then if two triangles overlap, there must be line segments intersecting. At this time, it is enough to judge whether the line segments intersect. Then I said the judgment method of the intersection of two line segments: if two line segments AB intersect with CD, points A and B must be on both sides of the straight line CD, and points C and D must be on both sides of the straight line AB. The way to judge whether two points A and B are on both sides of a straight line CD is to multiply the cross product of AC and AD vectors with the cross product of BC and BD vectors. If the result is negative, A and B are on both sides of the CD. If it is positive, at least one of them is on the straight CD. After that, GG affirmed my method and changed the question.
In all kinds of Microsoft technologies, it seems that writing programs on the spot is indispensable. The last problem of bilateral GG is a programming problem: the root node of binary tree is defined as level 0. Write a function, input the address and m of the root node, and realize the task of saving the data of the m-th node. A very basic recursive topic, handed in after writing, GG said yes, ending both sides. The interviewer on three sides is still a GG. He said he was from Xidian, not far from our school. Since GG on three sides turned on the video function actively this time, I also turned on my own video function, so that I can see each other (in fact, it is best not to turn it on, because seeing each other will make me more nervous, which is my personal feeling). GG also played a few jokes, probably to let the interviewer relax and play well. But I seem to be very nervous all the time (I knew it would be my do or die). In the first ten minutes, I talked a few words. GG asked a few points on my resume and also talked about my college life. Later, GG said that according to Microsoft's practice, programs must be written. Then he asked me if I could multiply large numbers (this is a relatively basic tool in ACM). I said that I had written a template that used arrays to simulate the operation of large numbers, and overloaded symbols such as+-*/. Then he said that this time he would write a string to simulate the multiplication of large numbers. I said I didn't write it, but I should be able to write it (I felt really empty at that time, afraid of writing badly, and almost refused, but I thought refusing to write almost meant being eliminated, so I bravely agreed). Then three GGs gave me my function statement, turned off his voice and said to give me half an hour to write, but I was always under his supervision. I probably drew a picture on a piece of paper, and when I thought it over, I began to write. It took about 10 minutes to finish, but I couldn't get any grades. Some data are input and output in garbled code, and it takes more than 20 minutes to get the correct result. After several groups of test results are correct, it is called interview GG, and that's all. GG asked to send an email. But there is a delay in sending e-mail. He said, in this delayed time, let me talk about my idea of the program first. I said, blablabla. . . Later, GG asked him why he didn't receive the email, and his mind was in a mess. He just said it, but he didn't send the email first. It was embarrassing, so I quickly sent it. GG also smiled and said that he had made such an embarrassing thing. After sending it, I found that the input 0* 0 program returned an empty string, so I quickly changed it and sent it again. Later, GG said that if I came to test what kind of data my program would use, I probably said that I would use boundary data such as 0 (obviously 0*0 was wrong just now) and then multiply it by negative numbers (I told GG that my program doesn't handle negative numbers, but it is easy to modify, so I just started to judge symbols, and GG said it doesn't matter). Then GG continued to ask me what kind of data I would input, during which the sound signal was not good. GG also asked me to continue typing to supplement the answer to this question. I really didn't expect to use any data myself (what I was thinking at that time was to try a few more sets of data, which should be similar. But certainly can't say that). Later, the interviewer GG kept quoting into it, and finally he himself said: If you input data like 0000000 123456789 and multiply it by another number, will there be many useless calculations in the function (I never thought about it at that time, and I felt like kneeling when GG said it). I said yes, if there is such data, it should be processed by removing the prefix 0 when entering. Later, GG didn't ask anything in the interview, so he asked me if I had any questions. I asked three times and informed the result in a few days. GG said that the human resources department would inform me in a week or so. Then I said hello and hung up.