Latest Microsoft Interview Questions

These are the questions asked in 4 rounds of inteview.

Questions:

Round 1

1.Celebrity Problem:
In a set of n people, a celebrity is defined as: everybody knows him, and he does not know any one.
In a gathering of n people containing at most 1 celebrity, the only question you can ask a person X is: "X, do you know Y?". How will you find the celebrity in minimum number of questions?

2. Write a function to determine whether a given string matches a given wild card pattern. Given that the only one wild card allowed is *(star) which means 0 or more characters. Give test cases for the same.


Round 2

1. Given a character and a string, remove all occurences of the character from the string. Give test cases.

2. Given an array with even and odd integers, write a function which either puts all the even numbers on even positions in the array or all odd nos on odd positions in the array or both (if possible). What are the best and worst cases? Give test cases.

3. Given a starting word and an ending word and a list of all the valid words. Print a path from the starting to the ending to word consisting of valid words, such that each word in the path differs from the previous one, in exactly one letter.


Round 3

1. Given a file, print the last n lines. Give test cases.

2. Can a binary tree be reconstructed given 2 out of the 3 different types of traversals? Write a program to reconstruct a tree, given the pre and in(or post) order traversal. Modify the code so that it can handle incorrect traversals (wrong orders, or missing values etc.).



Round 4


1.Given a matrix all whose columns and rows are individually sorted, search for a number in this matrix.

2. What is the difference between a 32-bit OS and a 64-bit OS? What kind of programs could run better on a 64-bit OS than a 32-bit one?

3.Why should we hire you?

4. Why do you want to work for Microsoft?