An Interview with Microsoft

On Feb 10, 2006 I had my interview with Microsoft for the position of Software Design Engineer (SDE). I submitted my resume when they came to my campus (Univ. of Maryland, Baltimore County) last September and had an interview with them in October and got the on-site interview call. I went to interview totally unprepared, not knowing what to expect. People told me about famous puzzles and linked list questions that they usually ask. I was lazy and didnt prepare much. I just read a bit of "Programming Interviews Exposed" and did a few problems from the net. I also went through the various data structures from wikipedia.

Read more about preaparing for the interviews

Microsft takes due care of the intervieews. They book the flights, give 3days/2 nights at Marriot, pay for all your taxi and food expenses and make sure that you are totally comfortable with the process. I paid for the $50 for my cab from Seattle airport to Bellevue (where my hotel was) and the drivers there know well about Microsoft's interview process. I spent my evening of the first day, blogging, and at night went to a nearby Indian restaurant (near Bellevue there are a lot of Asian restaurants, including Taj Palace). It is highly advisable to spend the day before interview, in a less tensed fashion and I had a long sleep.

On the day of the interview, I went fully dressed (I counted the number of people wearing the suit, on the entire campus and still didnt get the count cross 5) to the Building 19 (the recruiting center for the Redmond Campus) at around 10am for the 10.30 interview. I registered at the front lobby and had a casual chat with other interviewees (around 100 interviewees come everyday). The place was bustling and at around 10.50 am (they are not famous for their punctuality) my recruiter met me. She explained me the entire process, and had a general interview for 30 minutes, where she asked me about the reason for liking Computer Science, reason for choosing to Microsoft, a major project done recently, interesting courses taken recently and other aspects of academics. She also asked me about other competing offers that I have and noted down other important aspects related to HR (like candidate's availability, future interests etc.). After that, she gave me the details of the teams that I'll be interviewing with (I was to interview with Security group and Subscription group) and indicated that there might be around 4-6 interviews on that day.

At around 11.30, they shuttled me to the office of Security group (I think building 25) and there I informed my arrival to the receptionist and a team lead had come to interview me. He took me to his office and had a hour long interview. Like all other interviewers on that day, he asked me about the reason for choosing Microsoft and had me explain about the distributed file systems project that I did recently. Then, he gave me a programming question and asked me to code the solution on the white board.

1. The question was: Finding maximum subsequence in an array of integers (containing positive and negative numbers).

The question is a standard question in many algorthmic courses and though I came across the problem, earlier, I didnt have the most efficient solution. I gave the O(n^2) overlapping window solution and gave an indication of the O(n) solution. He was moderately satisfied and gave the second question, which was a tougher design question.

2 A disk is partioned into two hemispheres colored in black and white and the disk is rotating.By appropriate positioning of sensors (A sensor can read the disk near it as black or white) we need to find the direction of the motion of the disk.

The problem was deceptive and I rushed into the solution, later realizing that the problem was not as simple as I thought it to be. It was an interesting design question and we had a brief talk about designing the algorithm. At the end of the interview, I knew I didnt have the best of the starts, but still it didnt go bad either and I hoped to catch up in the next interviews.

After this interview, there were confusions in their camp (few interviewers didnt turn up on that day) and the team lead found an alternative and the replacement guy reluctantly started interviewing. He was having problems with his system and didnt enjoy much of the intrusion. We started to get moving with the interview, when 10 minutes into the interview, the team lead found that the recruiter already made a replacement and he apologized for the confusion and lead me to another interviewer. He was a nice, young guy and after the 2 usual questions, (mentioned earlier) he gave me two more programming questions, after taking me for a lunch interview.

In the lunch, he asked generally about my preferences in working (client side/server side), team preferences and area preferences and we had a nice discussion about my career goals etc. After that he asked 2 programming questions in the office.

3 A sorted array has a number of elements repeated in it. I have to take this array and without using any extra memory, do in place copying to compact the array, so the resulting array would not have duplicates.

It was easier among the questions that I had in that day. I had my solution with two pointers - one to move with every unique item -p and other one moving for each item in the original array -i. Whenver a new item is encounterd by the i pointer, the data is copied on to the location of the p pointer and it is moved one step. The solution was cleaner and the interviewer was satisfied.

4 Given an n-ary tree represented as a list of items, containing a node and its parent, construct the n-nary tree from it.

I gave a recursive solution for this and kept reading from the list continously a node and its parent and moving to the node's parent and so on. I used a hash table to hash to the location of a node encountered in the list. Again the interviewer seemed to get pleased.

After the interview, I was waiting in the lobby for 20 minutes before they found a guy from MSN Messenger to interview me. I went to his office in Redwest campus, and he asked about the challenges that I faced in the distributed systems project and gave me a coding question:

5 Given 2 linked lists, merge them by alternating the elements on the two lists. If one of them is emty, join all the elements of the other list.

It was not pretty hard, but I did a few mistakes with the pointer. At the end I was able to give the solution, but the interview was not entirely satisfactory.

After this, I moved to Building 115 (I might not be exact, here) and I was to interview with the Subscription services group. One senior gentleman there, gave another coding question:

6 Given two nodes on a binary tree, find the smallest common ancestor. If the nodes are children of the same node, then the parent is least common ancestor, of the nodes are related by their grandparents, it is answer or if one node is the ancestor of another, it itself is the answer and so on.

My solution involved, building a new binary tree, with parent pointers and height information stored on every node. Then, the solution is very simple. Find the nodes in the binary tree, make both the nodes come to same level, by moving a lower node along its parents and till both the nodes have the same parent, continue moving both the nodes to their parents.

The solution is O(log n), though the other solution without involving parent pointers and height information (done recursively on the original tree) might take O(n). However, building the new tree takes O(n) and find step, if done by hash tables takes O(1), else can take O(n). The solution surprised the interviewer, and after a long look, he accepted the solution.

The last interview of the day was the best of the day. The interviewer was very good and he asked me on coding a simple board game.

7 In the board game battleships there are 1-d ships placed on the board and an enemy ship can be shot at. If we shoot at a position where a part of the ship is thee, it is counted as a hit and if he a shot at all the positions of the ship spread across the board, it is counted as a sunk, else it is taken as a miss. Construct data structures for representing the board and ships and write a function that takes a position as parameter and returns the result as miss, hit or sunk.

After changing my design for 2-3 times, I finally came up with a solution, where the ships are represented by an array, where each element stores the number of remaining parts of the ship. The board is a 2D array storing the refrences to the ship that a position contains, else an invalid value to indicate the absence of a ship. If the position shows invalid reference then I return a miss, else I goto the reference and decrement the ship's part count and if the part count is nil, I return sunk, else I returned hit.

The solution impressed the interviewer and asked me in detail, about group preferences and work styles etc. At around 6.30 the 8 hour interview 'ordeal' ended and I went back to my recruiter. She had her final comments and at 8 pm I returned back.

Looking back, it was a great day starting with a beautiful sun-shine and a hitch-free day. The interviewers were understanding and some of their design questions were challenging. Their in-depth questions about my distributed file systems project was intriguing and I liked the overall process.

Let me wait for few more days for the result!!!!