Some of the On-site Interview Questions :

Q1.  You have an array of size 1 mil, whose contents are numbered starting from 1, 2, 3 ..... but the last element turns out to be (1mil +1)... which implies one element is missing somewhere in between.  What is the quickest way to find out which is the missing element. 

Ans: Binary Search.

Q2.  Design and algorithm for :

            byte[] compress(string a)

Details: The output should be lesser in size than the input.. the function should ONLY return a byte array... nothing smaller or bigger than that.. For the sake of simplicity, the input was only a-z, A-Z, 0-9.

Ans: 

1. Use ASCII Table.

2. Since you're only using the above mentioned characters, you will not be using the entire the entire byte to represent them.  (since a-z+A-Z+0-9 is only about 62 characters, you can make a mapping table where a = 000000, b = 000001 and so on... )

3.  When you stream them, now you will be able to send 4 characters in the same number of bits as what used to be 3 characters (since 4*6 bits = 3* 8 bits).  => You've achieved compression. 

PS : This was by far, the most challenging for me.

Q3.  How would you test a vending machine, the compose screen of an email; There was a specific Stress test scenario given..

Q4. What if the developer tells you halfway through the project that you have to switch to .NET 3.5?

Q5. You have a deck of cards.  Shuffle them in such a way that no card is in its original position after the shuffle.  The shuffle should be non-deterministic as in you should not be able to guess who gets what card, so shifting each card by one position won't do. 

Q6. The most important question was what do you want to do in 5 years from now?Better be prepared with a good answer for this, and you'll be asked the same thing multiple times.  It helps them decide whether you're a good fit for the position and vice versa, and it looked like they give a great deal of importance to both the sides.

  And if you're a developer be prepared to face the why testing question.  Also, Why Microsoft?.. They don't like 'because its Microsoft' obviously.. even if you have an answer to the above questions, be prepared to be grilled on everything you say...