# Microsoft Interview – Set 1

I appeared for MS interview for developer profile recently. I would like to contribute for CrazyforCode by sharing my experience.

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. How the memory is structured (heap, stack, etc). He wrote a program and asked which variables would be stored where etc.
As I mentioned that I like Algorithms, he then went on to Algos.

Q4. 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

This interview went on for about an hour.

Q1. Given a node in a binary tree, find the leftmost node in the same level. I wrote the pseudocode, and testcases.

Q2. Find the nth largest number in a binary tree.

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 three 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 working experience. 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.