Microsoft Interview questions for internships
Posted by Atul Bhatia on December 2, 2008
I recently faced the interview of Microsoft for summer internship
I am posting the questions asked to me in the written test and interview
Written exam was a subjective test comprising only 3 questions, 2 for coding and 1 for testing. The questions are as :-
1). There is a concept of some magic numbers like we have numbers from 1 to a big number and in first iteration we delete the numbers leaving one gap like initially numbers are : 1 2 3 4 5 6 7 8……… After first iteration we delete numbers 2 4 6 8….. Therefore now the remaining numbers are 1 3 5 7 9 11 13 15 17 19. In second iteration we delete numbers leaving two gaps, hence after it left no.s are 1 3 7 9 13 15 19 21…… then we delete no.s leaving 3 gaps and hence left nos. are 1 3 7 13 15 19 25…….The numbers which are never deleted are termed as magic number. Write a function, given a number, that weather a number is a magic no. or not
2). There are 2 lists (both singly non-circular). Both lists merge at one common node. Write a function returning pointer to a node at which the two lists merge and NULL if they do not merge.
3). You are given above function to use, but you cannot access the code of the function implemented in Q.2. Now you have to write the test cases for the same.
I did first two questions correct as written in the comments column and got selected for the interview. I will be posting the interview question soon.
For solutions refer to the “comments” column. Or for any querries post it in the comments..
Atul Bhatia said
1). There is simple funda for that.
If an element is given then after 1st iteration number of integers deleted b4 that element is n/2
after 2nd it is n/3
after ith it is n/i
therefore apply for loop as
while(i < n)
{
if(n%i == 0){
print : not a magic no;
return;
}
n = n – n/i;
i++;
}
print : magic number
return
Vijit said
Hello sir,
Though I am not very good in calculating the complexities, but still I was wondering what will be the complexity of this problem, it has to be much less than O(n), I think the no. of iterations should be-
i>=n-(n/2-n/3-n/4-…..n/i), so can we say the complexity to be O(n) or are we supposed to solve this eqn to calculate the exact complexity?
Kindly give your suggestions and correct me if I am wrong.
Atul Bhatia said
2) Following are the steps to implement Q2 in the best possible way that “I KNOW”
* Traverse both the lists and calculate their lengths as : len1 and len2
* Subtract smaller from bigger and save the result in variable “i”
* traverse first i nodes of bigger list and stop
* initialize pointer2 to smaller list now
* now start traversing both list simultaneously “one at a time” and after each step keep checking if pointer1 is equal to pointer2.
* if it is equal return the node where it is pointing to, otherwise return NULL.
3). The most important test case for it was checking for the loop in the linked list.
Mohit said
hey, in Q2 you forgot the case of trivial reject, once u have reached the end of both the linked lists(while calculating lengths), you can compare the last node if its different, then its trivial reject and no need to carry on any further checking..
Atul Bhatia said
@Mohit
Thanks for pointing it.