Pragna Technologies Interview

I think this is an IT consultant company. This is the screen interview for a Microsoft full-time/contractor software position. The interview has two part, first they send me a question documents containing three questions:

1. Given a linked list, write a function void DeleteBefore(node **head, data). For example, if the list has values 1->3->6->7->8->9->13, if data is 7, then element with data = 6 will be removed. This is fairly straightforward.

2. Given a sorted array say int num[10]={-5,1,6,7,9,9,20,25,31,45}, write a function void findsum(int [],int x) that can print out all possible pair of elements in array that can make a sum equal to x. For example if value of x is 26, then function should print {1,25}, {25,1}, {-5,31}, {31,-5}. The tricky thing is that they asked for a O(N) or O(2N) solution, and not O(N^2) solution, i.e., no nested loops. I can only come up with a O(N^2) solution, and the interviewer don't think there's O(N) or O(2N) solutions too.

3. OptimalQueues problem from topcoder


In the phone interview they basically asked me to go through the code I wrote for the first three questions, and check for any bugs. They also asked two additional questions:

4. Given 10 empty buckets and distributed 1000 coins to these 10 buckets, what's the distribution for the coins so that give any number between 1~1000, all you need to do is to return the corresponding buckets to have that number. For example, if the number is 1000, then all 10 buckets will be returned. The answer is actually quite easy but I failed at this one because I was doing it in reverse. The correct distribution is 1, 2, 4, 8, 16, 32, 64, 128, 256, 411.

5. Count the number of 1s in an integer. There's an added twist to this question as well since the integer can be negative. I gave the answer that work for unsigned int (from the programming interview exposed). To deal with negative numbers, we first check if its negative, then reverse it.

Since I don't care for contractor jobs I didn't spend much time on this. But I actually like the second part of the interview since the interviewer is very patient and actually give and explain the answers.