# Microsoft Interview – Set 2

I recently have appeared for Microsoft interview process. I would like to share it with crazyforcode and help others.
Following questions were asked during interview.

Round 1

Q1. Two numbers are stored in two linked lists, with one digit in each node. Add the numbers and return the resultant sum in a linked list.
eg. if LL1= 2 ­> 3 ­> 5, LL2= 1­>4­>5, result should be LL3= 3­>8­>0
Q2. Check the no of repeated occurences of a substring in a string.
Q3. Data compression: Given a string “aabbbccc”, save it as “a2b3c3”.
Here, I was asked to write a pseudocode, followed by a code in C++, optimize it and then all the testcases.
Eg. “aabcc” would become “a2bc2” and not “a2b1c2”

Round 2

Q1. Given a node in a binary tree, find the leftmost node in the same level.
Q2. Find the nth largest number in a binary tree.
Q3. Insert an element into a sorted circular linked list. (Consider all cases, inserting in the beginning, end and middle).

Round 3

Q1. Given 5 points in a plane, prove that there will be atleast two points such that their midpoint is an integer.
Q2. Given a room with points pertaining to different groups, check whether the connection is planar or non­planar i.e. while connecting all the points in the same group, the wires of different groups should not overlap.
Q3. Find the nth power of a number in shortest computational time.
Q4. There is a roller which can have two types of wood blocks, 49 cm and 50 cm. Given two sensors 50 cm apart which call a function ring( ) whenever the sensor changes state, write the function ring( ) to calculate the number of blocks of boh types.

Round 4

After 3 interviews, I was called for a final interview. He started by asking me about my best project and the drawbacks I faced in it. He asked about my internship and the workingexperience. This interview went on for more than an hour with him grilling me on two questions and their testcases.

Q1. Given a linked list, invert every two nodes in the list.Eg. Given a ­> b ­> c ­> d, result should be b ­> a ­> d ­> c
Q2. A file or a directory can be represented as a node. The node has properties like ID no, parent ID no, name, no of children( 0 for a file). The entire file structure is represented as a linked list of the nodes. Only thing known to us is that the parent directory will always come before the children in the LL. It need not come immediately before.We have to implement a GUI such that when I press on the + button next to the root directory, I see its children folders and files. The child directories have a + button next to them and can be expanded similarly.Write a pseudocode to implement this in minimum time and space.I suggested the use of a tree, wrote a code to convert it to a tree. He wanted a better way of finding children from the parent so I suggested a hash table comprising a hashing of the parent IDs to a LL of the children IDs.
He was satisfied with the answer.

Thanks Tanvi. G. Nabar for contributing this article. If you would like to contribute, mail us your interview experience at [email protected] We will like to publish it on CrazyforCode and help other job seekers.

### 3 Thoughts on “Microsoft Interview – Set 2”

1. anil kumar on September 10, 2013 at 10:56 pm said:

how can u do round4 2nd question

2. Anonymous on September 11, 2013 at 8:18 am said:

Hi Tanvi, thanks for the info. I am starting to learn data struct. Can you give some pointers.

3. phanindra on September 14, 2013 at 11:35 pm said:

ya the post is good .apart from it is informative to post the answers as welll!!!!!!!!!!
finally thanks to crazy for code.com!!!!!!!!!