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 .