Microsoft Technical Paper | Placement Papers - Technical & HR Questions - Interview Preparation PDF Download

Q1. Give a very good method to count the number of ones in a n (e.g. 32) bit number.

ANS: Given below are simple solutions, find a solution that does it in log (n) steps.

Iterative

function iterative count (unsigned int n)

begin

int count=0;

while (n)

begin

count += n & 0x1 ;

n >>= 1;

end

return count;

end

Sparse Count

function sparse count (unsigned int n)

begin

int count=0;

while (n)

begin

count++;

n &= (n-1);

end

return count ;

end

Q2. In a Xs and 0s game (i.e. TIC TAC TOE) if you write a program for this give a fast way to generate the moves by the computer. I mean this should be the fastest way possible.

ANS: The answer is that you need to store all possible configurations of the board and the move that is associated with that. Then it boils down to just accessing the right element and getting the corresponding move for it. Do some analysis and do some more optimization in storage since otherwise it becomes infeasible to get the required storage in a DOS machine.

Q3. Reverse a linked list.

ANS: Possible answers -

iterative loop

curr->next = prev;

prev = curr;

curr = next;

next = curr->next

endloop

recursive reverse(ptr)

if (ptr->next == NULL)

return ptr;

temp = reverse(ptr->next);

temp->next = ptr;

return ptr;

end

Q4. Given an array of integers, find the contiguous sub-array with the largest sum.

ANS: Can be done in O(n) time and O(1) extra space. Scan array from 1 to n. Remember the best sub-array seen so far and the best sub-array ending in i.

Q5. Given an array of length N containing integers between 1 and N, determine if it contains any duplicates.

ANS: [Is there an O(n) time solution that uses only O(1) extra space and does not destroy the original array?]

Q6. Sort an array of size n containing integers between 1 and K, given a temporary scratch integer array of size K.

ANS: Compute cumulative counts of integers in the auxiliary array. Now scan the original array, rotating cycles! [Can someone word this more nicely?]

Q7. An array of size k contains integers between 1 and n. You are given an additional scratch array of size n. Compress the original array by removing duplicates in it. What if k << n?

ANS: Can be done in O(k) time i.e. without initializing the auxiliary array!

Q8. An array of integers. The sum of the array is known not to overflow an integer. Compute the sum. What if we know that integers are in 2s complement form?

ANS: If numbers are in 2s complement, an ordinary looking loop like for(i=total=0;i< n;total+=array[i++]); will do. No need to check for overflows!

Q9. An array of characters. Reverse the order of words in it.

ANS: Write a routine to reverse a character array. Now call it for the given array and for each word in it.

Q10. An array of integers of size n. Generate a random permutation of the array, given a function rand_n() that returns an integer between 1 and n, both inclusive, with equal probability. What is the expected time of your algorithm?

ANS: Expected time should ring a bell. To compute a random permutation, use the standard algorithm of scanning array from n down to 1, swapping i-th element with a uniformly random element <= i-th. To compute a uniformly random integer between 1 and k (k < n), call rand_n() repeatedly until it returns a value in the desired range.