Microsoft Written test for SDE/SDET
Microsoft Written test for SDE/SDET
Category (Placement Paper or Interview Experience):
Placement PaperDate Conducted:
1 Dec 2007Paper/Interview:
based on my memory..
there were 2 paers .in first paper one need to only write the answers no need to give explanation.
where as in 2nd paper you need to write fully working code and with proper analysis of complexities involved.
written paper 1: 20/25 mins
q1: what does following code do , if we pass head pointer of a link list.
void list( struct node * head)
{
if(head)
{
list(head->next);
printf("%d",head->value);
}
}
Q2. some double link list code find 5 bugs and suggest remedy .
Q3. horse puzzle .. 35 horses and 6 racing tracks .. how many races you require to find top 3 horse.
Q4. already height balanced binary tree is given and an extra key . insert that key in the binary tree and finally balance it .
Q5.
void f(int n)
{
if(n>0)
{
f(--n);
printf("%d ",n);
f(--n);
}
}
print output if i call f(5);
/////////////////////////////////////////////////
paper 2 : 45 mins
Q1:. write fns for insertion and deletion for a circular and sorted link list . you should maintain the sort property .
Q2: a randomly filled array of 2N numbers ( N odd and N even) is given . arrange the array in such a way that odd numbers are at even indexes and even numbers are at odd indexes.
Q3. given a randomly filled array of N numbers and a number X . print all pair inside array such that they sum up to X.
Q4: design question:
design a bathroom for eye impaired people.
state all design constrains and also state limitations of your design.
/////////////////////////////////END of Papers////////////////
///////////Answers//////////
Paper1:
q1. prints link list in reverse order.
q2. Few illegal memory handling and pointers manipulation errors. no trivial syntactical error.
q3.8, standard puzzle .. goggle it.
q4. easy AVL tree question .
q5. very tricky . try it out and then run the code to check the output.output is not symmetrical, left and right subtree differ .
Paper2:
q1. trivial question . just requires careful coding
q2. there are number of possible solutions for it but for MS you need to give the best possible solution.
best possible is : O(n) time and O(1) space complexity
algorithm:
1. keep two pointers one at 0th index (even) and other is at 1st index(odd) of the array..
2. move both pointer towards other end by 2 position at a time and
3.keep checking if first pointer encounters a index where even number is at even place then stop first pointer there .and if 2nd encounters odd number at odd index then stop 2nd pointer . otherwise keep moving both of them until one of them reaches to the other end .
4. if both have stopped at 3rd step then swap numbers at the index pointed by two pointer and go to step 2.
5. END
since we require only one pass over the array hence it is O(n) algorithm without using any extra space.
try out this algorithm with an example.
q3.
1. sort the array
2. keep two pointers one at the start of the array and other at thh end of the array .
3. check
if sum of the value pointed by those pointer is equal to X then pritn the pair and move both pointer towards each other.
else if sum of the value is less then X then move first pointer towards end of the array by one step.
else move 2nd pointer towards start of the array by one step.
4. goto step 3 till first pointer index value is less than the 2nd pointer index value.
5.END
.. step 2-4 takes only O(n) .. since we are having only one pass over the array.
but step 1 takes nlogn time bcoz of sorting.without using any extra space.
so total complexity is O(nlogn) time and O(1) space.
q4. everyone will have different opinion about the design.:) /////////END of Answers////////////////
there were 2 paers .in first paper one need to only write the answers no need to give explanation.
where as in 2nd paper you need to write fully working code and with proper analysis of complexities involved.
written paper 1: 20/25 mins
q1: what does following code do , if we pass head pointer of a link list.
void list( struct node * head)
{
if(head)
{
list(head->next);
printf("%d",head->value);
}
}
Q2. some double link list code find 5 bugs and suggest remedy .
Q3. horse puzzle .. 35 horses and 6 racing tracks .. how many races you require to find top 3 horse.
Q4. already height balanced binary tree is given and an extra key . insert that key in the binary tree and finally balance it .
Q5.
void f(int n)
{
if(n>0)
{
f(--n);
printf("%d ",n);
f(--n);
}
}
print output if i call f(5);
/////////////////////////////////////////////////
paper 2 : 45 mins
Q1:. write fns for insertion and deletion for a circular and sorted link list . you should maintain the sort property .
Q2: a randomly filled array of 2N numbers ( N odd and N even) is given . arrange the array in such a way that odd numbers are at even indexes and even numbers are at odd indexes.
Q3. given a randomly filled array of N numbers and a number X . print all pair inside array such that they sum up to X.
Q4: design question:
design a bathroom for eye impaired people.
state all design constrains and also state limitations of your design.
/////////////////////////////////END of Papers////////////////
///////////Answers//////////
Paper1:
q1. prints link list in reverse order.
q2. Few illegal memory handling and pointers manipulation errors. no trivial syntactical error.
q3.8, standard puzzle .. goggle it.
q4. easy AVL tree question .
q5. very tricky . try it out and then run the code to check the output.output is not symmetrical, left and right subtree differ .
Paper2:
q1. trivial question . just requires careful coding
q2. there are number of possible solutions for it but for MS you need to give the best possible solution.
best possible is : O(n) time and O(1) space complexity
algorithm:
1. keep two pointers one at 0th index (even) and other is at 1st index(odd) of the array..
2. move both pointer towards other end by 2 position at a time and
3.keep checking if first pointer encounters a index where even number is at even place then stop first pointer there .and if 2nd encounters odd number at odd index then stop 2nd pointer . otherwise keep moving both of them until one of them reaches to the other end .
4. if both have stopped at 3rd step then swap numbers at the index pointed by two pointer and go to step 2.
5. END
since we require only one pass over the array hence it is O(n) algorithm without using any extra space.
try out this algorithm with an example.
q3.
1. sort the array
2. keep two pointers one at the start of the array and other at thh end of the array .
3. check
if sum of the value pointed by those pointer is equal to X then pritn the pair and move both pointer towards each other.
else if sum of the value is less then X then move first pointer towards end of the array by one step.
else move 2nd pointer towards start of the array by one step.
4. goto step 3 till first pointer index value is less than the 2nd pointer index value.
5.END
.. step 2-4 takes only O(n) .. since we are having only one pass over the array.
but step 1 takes nlogn time bcoz of sorting.without using any extra space.
so total complexity is O(nlogn) time and O(1) space.
q4. everyone will have different opinion about the design.:) /////////END of Answers////////////////
