## Microsoft Interview Questions

- 1of 1 vote
A Matrix of 1s and 0s is given, all zeros are water and 1s are land, first find out the number of ponds in the array (Reverse of islands problem). If one change can convert 1s in to zero then find out minimum number of changes that we need to make so that there will be only one pond in matrix..

Any algo how to make 1 pond ?

- 0of 0 votes
You have a chess board of size NxN. You have a horse at a given starting position. You also have a function that gives you all the positions that the horse can reach from it's current position.

Given an ending position, find the path to it that uses the minimum number of moves.

- 0of 0 votes
Given an array of integers when the difference between every two neighbored elements is either -1 or +1 or 0.

Write an efficient search algorithm to find a given number of x in the array.

- 0of 0 votes
Given two string you need to tell whether edit distance between two string is 1 or not.

- 0of 0 votes
Two sorted array of integer are given, you need to find nth rank element from combine array.

- 0of 0 votes
There is a set of n bolts and n nuts given. You have only API that tells whether given nut is smaller or larger then for a bolt no any other relative number. You need to match all nuts and bolts in O(nlogn).

- -2of 2 votes
Given an sorted array having duplicates and another which is not sorted and have duplicates.Find array b is found continuously in array a. if so print position of array b in array a

- 0of 0 votes
How would test this method ?

public static bool DateBetweenDates(DateTime startDate, DateTime endDate, DateTime dateToTest)

{

if (startDate.Year > dateToTest.Year)

return false;

if (endDate.Year < dateToTest.Year)

return false;

if (startDate.Month > dateToTest.Month)

return false;

if (endDate.Month < dateToTest.Month)

return false;

if (startDate.Day > dateToTest.Day)

return false;

if (endDate.Day < dateToTest.Day)

return false;

else

return true;

}

- 0of 0 votes
In a matrix of characters, find an string. String can be in any way (all 8 neighbors to be considered), like find Microsoft in below matrix.

A-C-P-R-C

X-S-O-P-C

V-O-V-N-I

W-G-F-M-N

Q-A-T-I-T

String Microsoft is present in the matrix above ?

There also a slight variation where a diagonal neighbor is not considered.

- 0of 0 votes
Given n rows of integers, such that the ith row (1 <= i <= n) contains i integers, find the path having the maximum weight.

Path traversal rules:

1. A valid path sequence would be top-down i.e. begins with the integer in the first row, and traverses all rows selecting only one integer in each row.

2. From any jth integer in the ith row i.e row[i][j], traversal can happen either downward (i.e to row[i+1][j]) or diagonally downward to the right (i.e to row[i+1][j+1])

The weight of a Path is the sum of values of integers in the Path sequence.

Sample Input:

No. of Rows: 5

4

2 9

15 1 3

16 92 41 44

8 142 6 4 8

Expected Output: 4, 2, 15, 92, 142 (Max weight is 255)

- 1of 1 vote
Java: You're given a very large array of char's. Write a method to remove duplicates in the array, in place. Optimize for space complexity, not time complexity.

- 0of 0 votes
Say you're the development lead for a mobile application. A user submits a bug report saying that something isn't working right even though internal tests show that it should. What do you do?

- 0of 0 votes
write a program to find the minimum value in an unsorted array of integers. how many assignment operations happen within the loop?

- 0of 0 votes
what does this code do?

`unsigned mystery(unsigned x) { unsigned i=0; while(x) { x=x&(x-1); i++; } return i; }`

- 0of 0 votes
write a program to return min value from an unsorted array of integers. How many assignment operations happen within the loop?

- 0of 0 votes
what does this code do?

`unsigned mystery(unsigned x) { unsigned i=0; while(x) { x=x&(x-1); i++; } return i; }`

- 0of 0 votes
You are writing a simulation for a print server. This print

server can accept jobs from 3 places - network, USB, or operator. It can dispatch only one job at a time. Each input job should contain an integer t which is the time in seconds it will take to process the job. Write a multi-threaded program to simulate the server and provide some simulated load with jobs. Think, of some interesting statistics your program should emit and code them in.

- 2of 2 votes
Write a function which gives the length of the largest palindrome found within a string.

- -2of 2 votes
Write a function that detects if a string is a palindrome.

- -1of 1 vote
Difference between a crash and exception.

Difference between macros and inline functions.

Mfc: message maps and virtual functions.

Different calling convention.

Late n early binding...

Garbage collector algorithm. When gc will fail to clean the memory.

How to know heap size, crash dump analysis, What is a stack n how to know stack memory size.

Commands in windbg.

Questions on Critical section, mutex, semaphores. Can we use mutex in single process and how?

Working of MSIL and JIT COMPILER.

Can a C# code, use c++ code and call kernel functions like createfile.

Areas: dot net, oops, operating systems, thread synchronization.

Difference in execution steps of c++ and c# code

- 0of 0 votes
Given a graph where every two nodes are either friends or enemies with each other. Find a way to go from one node to the other.

Restrictions:

1) You can also travel from one node to next if they are friends with each other

2) You have some “magic potions”. You can convert an enemy path to a friend path with a magic potion.

I know this can be solved easily using dfs or bfs but i want to know the time complexity of each approach

- 0of 0 votes
Consider a MxN matrix. You are given a start element(index) and an end element. The question is to find a path from start to end. Please note that in some blocks 'X' is marked which means your path cannot go through that element. My solution was to have a tree with 4 nodes (top/left/right/bottom) and recursively check if there is a path from start to end.

- 4of 4 votes
Given a Sorted integer array which is rotated N number of times. You have no idea what that N is. An element in the array can occur more for any number of time. Write a method to search the position of a given element. If there are more than one of the same element, return the position of the first element.

- 0of 2 votes
Whats the time complexity of this code?

When I told him its O(N^3), he told me to look carefully, its O(N^2),

I dont know why? Any idea?`for (int i = 0; i < n-2; ++i) { //some code for (int j = i+1; j < n-1; ++j) { //some code for (int k = j+1; k < n; ++k) { //some code } }`

}

- 0of 0 votes
Design a thread safe hash table from ground up.

Follow up question: How do you design it without using any locks.

- 1of 1 vote
Given a doubly linked list, copy the list.

Edit:

Struct node{

node *pNext;

node *pPrev;

node *pRandom;

};

pRandom has connection to any random nodes.

Write a program to clone this list.

- -1of 1 vote
design a durable API

- 0of 0 votes
web-based chatroom application

- 0of 0 votes
given 50K static online web pages, how do I identify all of them that have a phone numbers (assme 10 dights in a row)

- 0of 2 votes
Given 13 cards only of one suite say spade. You have to write algorithm to arrange the cards in stack such that you put cards in sequencial order at bottom & remove top you should get cards in sequencial order.

forex:- put first top card at bottom now remove the topmost should be one of spade.

-put top two cards one by one at the bottom, now remove the topmost should be two of spade.

- similarly do three time.. four time .... and so on till king.

Jack=11, queen=12, king=13

time complexity should be nlogn

Ans should be like this:

4, 1, K, J, 2, 10, 6, 7, 3, 5, Q, 9, 8

From this sequence put top one card at bottom & now top card should be number 1. as below

1, K, J, 2, 10, 6, 7, 3, 5, Q, 9, 8, 4 - top one card placed at bottom

K, J, 2, 10, 6, 7, 3, 5, Q, 9, 8, 4- top card is 1 which is removed

Now do same with two cards as below

2, 10, 6, 7, 3, 5, Q, 9, 8, 4, K, J- top two placed at bottom.

Now topmost is 2nd number so remove it

10, 6, 7, 3, 5, Q, 9, 8, 4, K, J

do same for 3, 4 ... till K

3, 5, Q, 9, 8, 4, K, J, 10, 6, 7

5, Q, 9, 8, 4, K, J, 10, 6, 7

.

.

The card we remove should be in 1 to k sequence i.e. 1,2,3,4,5,6,7,8,9,10,J,Q,K

But here we need to find how to form the sequence in NlogN i.e.

Ans should be like this:

4, 1, K, J, 2, 10, 6, 7, 3, 5, Q, 9, 8