Microsoft Interview Questions – Set 6 (On campus Internship)

Company : Microsoft
Branches : CS & IT
Interview Type : On campus (Internship)

Interview Process: There were a total of 4 rounds.

Round 1: (MCQ round )

In this round there were a total of 15 MCQ’s and the time alloted was 30 mins.The questions were mainly from C/C++/Java output finding, pointers and references and basic puzzles.
I was able to solve 12 + mcq’s. I managed to qualify this round.

Round 2: (ONLINE CODING ROUND)

In this round 2 coding questions were given to us which need to be solved in 1hr time.

Q1. You are given a matrix of dimensions m*n where each cell in the matrix can have values 0,1 or 2 which has the following meaning :

0:empty cell

1:cells have fresh oranges

2:cells have rotten oranges

So we have to determine what is the minimum time required so that all the oranges will be rotten.A rotten orange at index [i,j] can rot other fresh orange at indexes [i+1,j] ,[i,j+1] ,[i-1,j] ,[i,j-1]. If it is impossible to rot every orange then simply return -1;

Q2. You are provided with a binary tree and given two integers n and k.You have to determine sum of data of all the nodes which are at a distance of k from the node which has data n.
I managed to solve question no. 2 completely .Both using BFS.Here is my way of how I did it:-

1. Use BFS directly to traverse the array once and can obtain the solution in O(n^2) only.

2. Form a graph out of the tree with the found node as the source point and then do BFS Sum to find the required answer.

Round 3:

Q1. Find the third largest element in the array

I first gave him a heap solution(kth largest element in the array )
He asked me to write the code for it. Then he asked me to improve it. And then I gave him O(n) solution .

He said that I should cover all the edge cases and left the room alone for 30 minutes. Then he came back and he was satisfied with my solution and immediately said that wait for the 4th round.

Round 4:

Q1. Mirror A Binary Tree.

Q2. Given Two BinaryTrees , check if they are mirror of each other.

Q3. Level Order Traversal in spiral form(Told me to code it)?

Suggestions:

- Strong Data Structures And Algorithms
- Focus On More Than One Solution Of The Question
Stay calm and confident.