Microsoft Internship Interview 2011 (Hyderabad Revisited) | using namespace LIFE;

Finally I get a couple of minutes to blog about my recent interview at Microsoft for the position of a summer intern. Microsoft came to our college campus and conducted a written test. I performed well enough to be selected for the on-site interview and was invited to Microsoft’s Hyderabad campus along with a couple of other batchmates. I will just mention the good questions which were asked during the interview/written test to me and others.

The written test was pretty simple. The only objective question that can be called challenging was related to Semaphores. But if you know the concept, you are good to go.

There were 5 subjective questions. One output problem (very easy), one question that was cancelled (lol), one question for test cases (pretty simple), one algorithm and one design question. I’ll only be listing the moderately difficult questions here along with little hints.

The algorithm related question was as follows : (don’t remember the exact words, but this is the essence)

Q: We have a sorted shifted array,i.e., an array initially sorted in ascending/descending order and then rotated by a certain amount (lets say k). We don’t know which direction the array has been rotated in. What you are supposed to do is find an element in the array.

Hint : Everyone can do it in O(n) time. Think about the search algorithm that gives O(lg n) and try and modify it.

The design question was also pretty simple. Here it is :

Q : Design a system for a hospital for the staff to get details about the patients.

Concepts to remember : Object Oriented Programming, Databases (Views, ER Models, Schemas, etc), Artificial Intelligence (Speech recognition, NLP), Algorithm Design (for searching, sorting, etc.)

These were the questions for the written test. Answering most of them correctly, I earned a free trip to Hyderabad. Better still, I got to see the aw-f-some campus of Microsoft in Hyderabad. Table tennis tables, no formal clothes required, coffee and comfortable chairs everywhere – now that is what I call work environment!

Since the post is interview oriented, I won’t go into the details of my trip (although I want to…so badly!) Let me directly come to the questions asked and my hints

Q : You have been given an inorder expression and a preorder expression. Now get the postorder expression from the same.

Hint : Trees

Q : Write a program to reverse a string and its test cases.

Hint : D-uh! You really want a hint for this?

Q : There is an array with every element having a duplicate except one element. How will you find the number without a duplicate?

Hint : Are you thinking about O(n lg n) ? That is simple. Think about O(n). Try and use XOR.

Q : Let us modify the above question. Now there are two such elements which do not have a duplicate. Find them.

Hint : Use XOR. Try to separate the two numbers into 2 different arrays. Then apply the same solution you did above.

Q : Write a program to add numbers stored in 2 linked lists, i.e., if one number is 367, the first node has 3, the next 6 and the next 7. So you have to add two such numbers. Write test cases for your program.

Hint : Basic traversal and corresponding addition after reversing the linked lists. Take care of memory issues.

These were the questions that I was asked. Although I was hoping they would ask me about my projects, none of my interviewers asked me about them and instead focused on coding. No sweat.

Let me now list some other questions that my friends were asked in their interviews.

Q : How will you reverse a linked list (use recursion)?

Hint : Store the current node’s position in a pointer, call the function again, and after that exchange the link. Hope you get what I mean. Otherwise, leave a comment.

Q : Is there a difference between a null string and an empty string?

Hint : Think in terms of memory.

Q : Write a program for string concatenation and its test cases.

Hint : Be careful to give test cases from the user’s point of view.

These are all the questions I remember at the moment.

Oh! And did I forget to mention, the interview process is not over yet. I still have to face one phone interview (you can read about my phone interview here) before the final decision will be made! Let us keep our fingers crossed! Hoping to clear the last round too \m/