Microsoft Interview Questions

I am now placed at Microsoft, IDC.

As part of the ongoing campus placement program in our college, Microsoft recently came hunting for CS/IT students for its’ Development Center in Hyderabad. The process ran its course over Wednesday and Thursday this week. The pre-placement talk was held Wednesday afternoon, and the final results were announced almost exactly 24 hours later. The process consisted of two written rounds, and three rounds of personal interview. I am reproducing the questions I was asked below.

Written Round 1

1. Find the median of a Binary Search Tree. You are passed the root of the tree, and you should return the median which is the middle element, if the number of elements is odd, or the average of the two middle elements if the number of elements is even.

2. Write a function to check if the two passed strings are anagrams of each other.

3. We want to implement the functions allocstring, freestring, concatestring, and stringlength. We need to optimize the functions in this order : stringlength, allocstring, freestring, concatestring, with stringlength requiring the most optimizations. We are also given that the memory consists of a buffer of fixed size. We have to design and describe a data structure which would enable the above operations to be performed in an efficient manner.

Written Round 2

In this round, we were taken to a room, and each student was assigned a supervisor. The question would be written on the board, and we must write “tight” code to solve the given problem. Before writing the code however, we had to describe our algorithm to our supervisor, and convince them that our algorithm is correct and would work. Tight codes basically means that we had to check all the boundary conditions of our algorithms, and make sure that no test case crashes our program.

1. Implement the function bool isRegex(char *reg, char *string); This function is passed two strings : a regular expression, consisting of the [a-z] and the * and ? characters. We had to check if the string matched the supplied regular expression. For example, if reg is a*b, and string is acbcb, we should return true. And if reg is a?b and string is accb, we return false.

2. Implement the function : node * add(node *l1, node *l2). The lists L1 and L2 are linked lists where each node of the linked list contains a single hexadecimal digit, represented as a char. The whole list thus represents a hexadecimal number. We had to add the two hex numbers represented in l1 and l2, and return the head of the linked list representing the answer.

Personal Interview 1

1. Given an array consisting of only 0s and 1s, sort it. He was looking for highly optimized algos.

2. Given that an array consists of only 0s, 1s, and 2s, sort it. Again, only very efficient code was accepted. Good old counting sort was sneered at. He wanted an algo to do this in one pass of the algorithm without using any extra space, and which performed the minimum number of manipulations of the array.

Personal Interview 2

1. Implement a Queue using a Stack ADT. He told me to write “tight” code for this as well. He wanted optimized methods for this, and asked me to enumerate different ways of optimizing this data structure, and to analyze each one. After I did that, he asked me whether my code would handle multiple simultaneous access to the data structure, and asked to handle that case as well.

2. You are given a binary tree where each node consists of a left pointer, a right pointer, and a sibling pointer. The left and right pointers are initially populated and the tree is a normal binary tree. He wanted a function to populate the sibling pointers such that they point to the node to the right of the current node in the tree, and which is on the same level. If there is no such node, the sibling pointer must be set to NULL. He again wanted an optimized solution, optimized for space.

Personal Interview 3

This guy was a through and through OS guy I think.

1. What is a process.

2. How is it different from a thread.

3. How is common data shared between threads.

4. Semaphores and other locking mechanisms.

5. Code for some of the locking mechanisms.

6. Design a data structure which will support the following operation : given a seven letter word, return all valid words which are anagrams of this word. He wanted a data structure which would be optimized for space, and another one optimized for time.

7. Write the code to implement the aforementioned function given the data structure.

8. How does malloc work?

9. How is heap space managed in a C/C++ environment.

10. Explain paging.

A bunch of other OS related questions.