Blog # 21 : Microsoft Internship 2010

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 :)