Company : Microsoft
I appeared in Microsoft interview recently and I would like to contibute to crazyforcode.com. This website is very helpful for interview preparation.
Written Round: 60 minutes, 3 programs, no compiler; just type and submit.
Round 1:
Initially he started with a discussion of my final year project. After about 10 minutes of discussion, I think he concluded it was too early for me to know my own project topic well. Since the area of my project is network security, the rest of the discussion revolved around it. He went into the details of cryptography and attacks like buffer overflow, asking me to basically just assure him I knew what I was speaking (discuss those things orally, and occasionally write small snippets). One particularly ridiculous part of this interview that I happen to remember was me having uttered the term ‘canary bit’, followed by him torturing me around it for about 10 minutes, he asked me what exactly it is, how I thought it could be implemented, if I could draw a rudimentary design of such a subsystem and all. The whole discussion went on for say 50 minutes or so.
Q1. After that he asked me a problem.“Compress a text string in place”. Having seen the famous string expansion in place problem many times, I promptly said run length encoding (i.e. compress aaaaaabbbbbccc to a6b5c3 for example). He asked me to code it and write a few test cases for it. The most important test case in my opinion is the following:
a -> a and not a1, i.e. for a single occurrence of a character, do not write its count – the reason
being that the string, instead of getting compressed, gets expanded in that case.
Q2. Given a binary search tree and a no. N in the tree, print the leftmost node at the same level as N.
ROUND 2:
This was a nice, pure problem-solving round.
First, he asked me the famous “Tell me about yourself” and “How were your earlier rounds”
questions. But they were just ice-breakers.
Q1. WAP to print a matrix spirally. I told him I knew the problem so he skipped it.
Q2. Search for an element in a rotated sorted array (of course in sublinear time!).
Q3. Nice DP problem. Given an amount and an array containing possible coin denominations, determine the smallest no of coins in which the amount may be formed. Assume you have infinite units of each denomination.
ROUND 3:
This was the most enjoyable round. The interviewer was a final round specialist!
First, he asked me about my internship, which I explained to him. He discussed it for hardly 10
minutes.
Then he started his attack! (Yes, it literally felt like an attack – just like Ronnie O’Sullivan 
There were three questions here:
Q1. Given a linked list, swap its nodes pairwise. A good test of pointer manipulation with many edge
Q2. Given an array, bring all its distinct elements to the top in any order, the rest of the array is not
important. First I suggested in O(n) space. Then he asked me to do it without extra space. I
needed a sorted array for that, which he asked me to assume. The rest of it is based on swapping
elements in order to bring the required elements to the top.
Q3. Given a matrix, find an element that is max in its row and min in its col. The actual question
(after I wrote the function) was whether there can be more than one such element in the matrix,
assuming all elements are distinct. Wrote a small proof that there cannot. He literally asked for a
formal proof “as I would write it in an exam”!
Finally I got placed. I was on cloud 9.. All the best. 
Thanks Pratul S. Dube for contributing this article. If you would like to contribute, mail us your interview experience at [email protected]. We will like to publish it on CrazyforCode and help other job seekers.
