Written Round 1 :  50 multiple choice questions in 60 mins time. Had 2 sections – Aptitude and

Programming Ability.

Written Round 2 : 3 coding questions in 1 hour.

1.   Swap every consecutive odd and even positioned bit in a number.

Ex:- 10101011010101 =  01010111101010

2.   Given a binary search tree . Convert it into a doubly linked list in place (no extra space) such that prev points to left child and next points to right child.

3.   Given a linked list that contains 0,1 and 2 . Sort this linked such that it contains 0s first,then

1s and then 2s in O(n) time.

Ex:- 2->2->1->0->0->2->1->1->0 = 0->0->0->1->1->1-2->2->2

PI round 1 (Technical):

1.   About urself, most challenging project of all you have done and about ur internship.

2.   Remove from string s1, all the characters that are present in string s2.

S1=”abcde” s2=”xyazbx”   Ans. S1= ”cde”

3.   Reverse alternate k nodes in an linked list.

Ex:- 1->2->3->4->5->6->7->8  if k=2; then return 2->1->3->4->6->5->7->8

4.   Always ask some questions to the interviewer at the end. That’s a good gesture.

5.   Write test cases for the programs above and see if ur program covers all the test cases or not.

PI round 2 (Program manager)

1.   Design a tic-tac-toe game for multiplayer on a smartphone.

2.   Design a vending machine for blind and deaf.

PI round 3 (Technical)

1.   Add numbers from 1 to n2  into a n X n matrix spirally.

1	2	3	4	5
16	17	18	19	6
15	24	25	20	7
14	23	22	21	8
13	12	11	10	9

2.   Remove duplicates from a string in place.

Ex-microsoft -> microsft

3.   Some question on recursive functions using memorization technique for optimization.

PI round 4 (Testing)

1.   Given a func ::    int *strcmp(char *s1,char *s2);

Write test cases to check functionality and security issues and even automate the generation of test cases.

2.   Given a func ::    int typeOfTriangle(int side1,int side2,int side3); (func gives a number for the type of triangle)

Write test cases to check functionality and security issues and even automate the generation of test cases.

3.   WAP to reverse words in a sentence.

I am a good boy -> boy good a am i

4.   WAP to get the next higher palindrome of a given number.

123 -> 131                1232 -> 1331

PS -  Functional issues are test cases that check the functionality of the program and Security issues are the ones where the program may crash.

PI round 5 (Technical)

1.   WAP to check if a binary tree is a BST or not.

2.   WAP to find Least Common Ancestor of two nodes in a BST.

3.   Reverse every two nodes in a linked iteratively and recursively.

Written:

1) A code was given and we had to print output. Had something to do with pointers to character array.

2) A code was given which finds the successor to any node in a BST, we have to find bugs in it.

3) A simple question about sorting. 

4) Given a function NextDate( string currentDate, int n ), which takes in current date and n and returns the date n days ahead of it, 

write the test cases you would test it with.

5) You are to design a system for elevators in a 100-storey building, what information you think you need before-hand to get started.

Interviews:

Round 1: 8 of us were seated at same time, a problem was explained and we were asked to code on paper.

Question: Given a structure consisting of numbers which is sorted row-wise and column-wise.

for ex:     1 ---> 2 ----> 5

               |

               6 ---> 8 ---> 10 --> 12

               |

               15 -->20

Length of each row can't be more than 5. You have to write code to insert any given number in this structure maintaining it's property. 

Try to code as cleanly and correctly in first attempt.

Round 2:

1) Given a sorted array of size m and another sorted array of size m+n, where the 2nd array contains only n elements, merge the arrays to create a sorted array.

They were interested in code that would do as little computations as possible, ie, for 2 algorithms with same complexity, the one doing fewer computations is better.

2) Classical Red Ball, Blue ball, mixed ball and wrong labels puzzle.

3) Another classical 12 ball 1 heavy problem. :)

Round 3:

1) Implement case insensitive strcmp function. Try to code correctly in first attempt.

2) In a Binary tree, the balance of each node is defined as ( maximum height - minimum height ) <=1. Write a function to check if a given tree is balanced or not.

At Microsoft:

Round 1) Given a string, like abcdaddee, find all possible palindromes that can be formed by interchanging the positions of the characters present. You can't add or delete more characters and have to use all the characters. Write the code. for ex with abab, one can form abba and baab. 

Round 2) In a BST, the values of 2 nodes are swapped. Write the the code to find those values, O(n) complexity

9 balls are given and 1 is defective, however u don't know the type of defect. Use minimum weightings to find the defect and defective ball. Ans: 3

Round 3)

1) Given 2 different matrices, Column 1 of both matrices contain similar type of entries. You can assume that Matrix A contains Roll no and Names of some students and 

Matrix B contains Roll No and Grades of same students, however, the order of roll no can be different, ie, Roll 1 can be at position i in Matrix 1 and at any position j in Matrix B. You have to create a new matrix with the information merged, i.e, Matrix C will contain 3 columns-Roll no, Names and grades. [ Much like join operation in databases ].

After I proposed the solution, he asked if there are many merge operations going on, what changes could be done to make this efficient ?

2) Given a string a[] and a character ch, modify the string a[] so that there no instances of ch present. Keep in mind that there should be no blank spaces.

3) Given an array, which is sorted but rotated, like 4 5 6 1 2 3, find any element in it. O( lg(n) ).

4) Some discussions about compilers and pointers and other things. Fattebazi hui dono side se :)

1. You need to find leftmost right cousin of a node in a binary tree.

Leftmost of all the nodes present on the right side of the input node with the same height is called Leftmost Right Cousin.


2. void replace(int list[], int data, int pos)

This function takes a list of integers, an integer data, another integer pos.

It searches data in the list and after finding it, deletes the node containing data. Then it replaces the value present a index pos of the list with data.

You need to write test cases as the values of list, data, pos.


3. There is a call center. For any specific subject, there are agents. Any agent can help only one user at a time. Any agent can go to a break or full off for the day.
Answer the following:
a) Write down the agent's state machine.
b) What algorithm will you use to assign a proper agent to a user.
c) In case of the request sent by user is lost as the agent just went to the leave before getting message from server about the user. How will you handle this race condition.






p.s. : Please suggest to update any of these questions, if you find anything wrong in them.

1. Given a string s[1...n] and a reverse function reverse(s, i, k) which reverses the character sequence from i to k (inclusive of both) in string s, determine what the following operations result in.
1<k<n

reverse(s, 1,  k)
reverse(s, k+1, n)
reverse(s, 1, n)

a) Reverses the string
b) Rotates the String left k positions
c) Rotates the String right k positions
d) None of the above


Answer: b)

2. If len is the length of the string and num is the number of characters printed on the screen. Give the relation between num and len.

void abc (char *s){
if(s[0]=='\0')
return;

abc(s+1);
abc(s+1);
printf("%c ", s[0]);

}

a) num=2^len
b )num=2^len-1
c) num=2*len-1
d) None of the above




Answer: b)




3. Which of the following numbers cannot be represented accurately in binary?
a) 0.1  b) 6.5 c) 1/16 d)1.32 e) 0.590625 (not sure abt option e)

1. a only
2. a and b
3. a, b and d
4. a, b and e




Answer: a) and d) should be the answer



4. A process doesn't require additional processors to carry out 40% of it's execution since 40% is mostly sequential. Determine how many processors are required to execute the process in 150s if
the process takes 300s to execute on a single processor.

a)5
b)8
c)6
d)7


Answer: c)

5. Time complexity of a function f(m) is O(m). If the array[i...n] contains either 1 or 0 in each of it's locations, determine the worst case time complexity of the following piece of code written in C-like
language.


counter=0;
for(i=0; i=n; i++){
if(a[i]==1)
counter++;
else{
f(counter);
counter=0;

}
}

* i=n was given in the condition of for loop
a) O(n^2)
b) O(n^2 logn)
c) O(nlogn)
d) O(n)




Answer: d) if assuming everything else to be alright.




6. Increasing the RAM increases the efficiency of the CPU. The reason
is
a) Virtual memory increases
b) Number of page Page faults decreases
c) Page segmentation decreases
d) Increasing the amount of memory increases the speed of fetching
data.


Answer: b)


7. If a dice is thrown three times, what is the probability that a "six" comes atleast once.
a) 125/216
b) 25/216
c) 91/216
d) 1/216

Answer: c)