I arrived at the hotel at 1:45PM, asked the receptionist where the Microsoft interview was, and told to wait at the lobby as she was busy with something else. I waited for about 5 minutes before asking again and was directed to the 10th floor. On my way up, I met two other persons who were also here for the interview. I went to the room, and there I met another 3 persons, so there were a total of six persons for that interview session.
There were no MS people anywhere in-sight. Maybe they had just finished their previous interview session and were having lunch. All six of us waited in that room, where the bed had been taken out and there was this big table with these
Geomag toys, wooden blocks puzzle,
Seattle magazine, Microsoft
SDE/
SDET brochure, plenty of coffee and tea to keep all of us from getting bored I guess. Only shortly afterwards, a MS guy, the HR maybe, came in. He welcomed and briefed us about what the interview might look like. Basically we would meet at least 3 people, 45 minutes each, and if deemed necessary, we might meet one more people. There were six interviewers; each would go one-on-one with each interviewee. After each 45 minutes, we were supposed to return to this room, and waited to be called for the next one.
My first interview was with a
PM in the
Exchange group. He was a really nice guy, smiley guy, I liked him. First he introduced himself, his work, his team, that he had been involved in Exchange since it was nothing 'till now where Exchange had a huge installation base. It was amazing. Then he asked about why I wanted to work in MS, what my interests were, some work I had done, etc. Then it proceeded to the exciting stuff where he asked me to write codes on paper (no whiteboard). I was asked to write a function
findNth(int n, Node* root), which would return the n-th node of the given tree if the tree were traversed in-order. But instead of traversing the whole tree, I was supposed to traverse directly to the requested node, without doing any backtracking, etc. For example, given this tree:
E
/ \
/ \
C H
/ \ / \
A D G I
whose in-order traversal returns:
ACDEGHI. If n equals 3, then I'm supposed to return node D (directly traversing
E->C->D). I won't post any answer here, but I think I did well for this task. Btw, during the interview we were allowed to ask any clarifications, which I think we should. And I also tried to verbalize my thought as much as possible.
My second interview was with an SDE in the mailbox team. He first asked me to introduce myself, tell him a little bit about myself, etc. Then it went to the technical stuff again. He wanted me to write a function
hexStr2Int that takes a string (pointer to array of chars) representing a hexadecimal string and returns it as an integer value. I think I did well too here, including identifying any possible pitfalls, etc. He then gave me a second problem, where assumed I was given a line-drawing algorithm on a cartesian coordinate of (-N, -N) up to (N, N) and I was supposed to write test cases for this algorithm. What kind of input test cases would I write? All in all, I feel like I did well for this task too.
Third interview was with another SDE. After some initial introduction, he asked me to find a contiguous subset given an array containing positive and negative values where the subset sum would be maximized. For example, given this array: [2, -1, 3, -5, 7], the maximum subset would be [7]. No, brute force was not allowed, in fact he wanted an O(n) algorithm. Somehow I totally screwed myself up this time. I was unable to come-up with an O(n) algorithm. My mind was somehow fixed to an O(n^2) solution (maybe, I didn't pursue further). Until the end of the interview, I could not come up with a good solution. I did really bad and felt down. Later that night, I found out that I should have known about this because I learnt about this some time long ago.
When we all gathered back at the waiting room, we were wondering if there would be a fourth interview. Apparently there was, my fourth one was with the HR guy. The interview wasn't too technical in nature. It was more about my interests, my background, what I would do for Microsoft (my vision) if I were Bill Gates. This last question was particularly interesting: imagine you were Bill Gates, what would you do? Although there were no right/wrong answers, I didn't feel like I had answered well though. After the discussion, he presented me with some problem solving, the famous Microsoft riddles. My first riddle was like this. Two old friends came to meet each other while they were sitting on a bench waiting for a bus. The first man asked, "How old are your daughters?" The second man answered, "Well, I have 3 daughters, the product of their ages is 36; the sum of their ages is equal to the address of that house across the street". The first man replied, "I still don't have enough clues". The second man added, "My oldest daughter has a red hair". And the first man said, "Oh, I see. I know their ages now". So do you know their ages? After several discussions, I managed to find the answers. It was really an interesting riddle. Then he presented me another riddle: there were three jars in front of you. Each was labeled: apples, oranges, apples + oranges, respectively. But all those labels were wrong and misplaced. You could not see what inside each jar was. You were only allowed to reach-in into one of the jar, picked exactly one of the fruit, and decided which label should go to which jar. I managed to find the answer for this riddle as well.
Four interviews and I thought those were all. Apparently I was wrong and I again had my fifth interview. This time it was with Matt, who had interviewed me before via the phone, before I came to Sydney. I was really glad to finally be able to meet him. He was the one who decided that I be invited for this on-site interview after all. Matt seemed like a nice, cool, and relax guy. He just wore a short. After several short introductions, what my interests, what I didn't like to do, my backgrounds, some work I had done, he asked me to write this function which would "fix" a URI like:
http://www.microsoft.com/office/../sp2/../sp2a/ into
http://www.microsoft.com/sp2a/. No
STL string, no
CString, just pure
#include <string.h>. It was the longest code I wrote among all interviews, I spent like 3 pieces of paper, but I managed to finish it all. I think there could be some syntax error here and there though.
After that, I returned to the waiting room. Shortly afterwards, two of the candidates (one was named Sun Jae, the other Rony) joined me in the room. We waited until about 7PM when a MS guy, the first guy that we met earlier, came in and told us that the interview had ended. We would receive the decision the following week. He then collected our transcript, passport, and bachelor certificate, which we had been instructed to bring copies before. Oh btw, I didn't see the other three candidates that were initially with us. I was told later that those three guys had only four interviews instead of five. This could mean a good sign or a bad sign. A bad sign for me because these three guys were good enough that they didn't need the fifth one whereas I might not have impressed them yet; or a good sign for me because these three guys were simply not good whereas I still might not have impressed them. Both were probably signaling the same thing, they could not achieve a unanimous vote on whether I was good enough to work for MS. I kept my fingers crossed for the result. In fact, the next few days would make me really nervous waiting for the result as I didn't feel like I had done well enough. Whatever the result would be, this had been a worthwhile experience.
PS3. I've always loved this kind of picture. Mind you that this was taken by an amateur photographer :-). TC's version will be better. Now have fun identifying each, some prominent people are missing though :-(. 
