## My Microsoft interns interview questions

Thought it wub be useful if i put it down here. There was only one panel. No HR 🙂 . The questions were easy .

Before he started the questions, he discussed my written paper. I had made a mistake in the complexity of one of the problem and he asked me to explain and then he went on to ask questions. First one seemed really stupid. When i was asked this question i was wondering what the interviewer had in mind. So here goes the question ” Given an array A of n unique elements from X to X+n , sort them ” . I told him the most obvious O(n) soln of putting the (X+i)th number at the position i . But he asked for some other better solution . This is where i began to doubt if i was making a mistake in understanding the problem. This couldnt be done less than O(n) . So i told the same solution in a diff way .. I said start from i=0 and put the value of a[i] at a[i]-X and put the value of a[a[i]-X] at the corresponding postion and keep doing the same. He was satisfied with this solution though both were same . 😛

The second question was better.Given a cycle of n nodes. Each node has a money Bi and each edge of the cycle has a cost Ci.Now whn i am at a node, i acquire the money at the node and if i have to move to the next node in the cycle , i have to pay a cost corresponding to tht edge. Now the cycle is unidirectional and we define a trip as starting from a node and coming back to it. After explaining this question , he asked me to asnwer for the following.

1. Give a necessary and sufficient condition for a trip to exist.

2. Given 1, give an algorithm to find the start node.

I took some time .. Figured out the necessary and sufficient condition and gave first the brute force O(n²) . And i told him i need some more time to think of better solution. And then i made some reductions and converted it another porblem with linear array and gave a O(n) solution . He then asked me to write a prog for the same. And was looking happy and was thinking for abt 5 mins about my solution and noted down something in his laptop.

The third question was again simple one. He asked me to write a cpp program to insert into a sorted double linked list. I happily gave the code and came out. All those guys who went in after me had come out long ago and were queued up for second round. Most of them were asked some linked list operation or string operations like reversing , concatination. And in the end me and nr, who again was interviewed for some one hour , were sent off telling there were no second round for us. I could see that they were running out of time .

They probably want you to work for Google 🙂

Akhil RavidasJanuary 14, 2009 at 5:00 pm

yeah .. their chances of bringing down google 😛

Sathya NarayananJanuary 14, 2009 at 5:59 pm

hi machi…. i think u could have used that manthra algo….. it worked… try it out….

arun nd rishiJanuary 14, 2009 at 9:51 pm

wht manthra machi ????

Sathya NarayananJanuary 14, 2009 at 9:52 pm

whats d O(n) solution to 2nd problem??

SnehaJanuary 7, 2010 at 10:10 pm

I will also like to know O(n) solution to 2nd problem.

please mail me if possible.

🙂

VikasJanuary 12, 2010 at 10:25 am

O(n) is a notation used to determine the performance of logic but not a solution for the problem.

satheeshJune 7, 2011 at 11:41 am

cud u pls tell me how will u sort in 0(n)????

anurag mishraAugust 25, 2011 at 1:35 pm

ya whats manthra algorithm ?

kireetiSeptember 6, 2011 at 9:20 am