## Microsoft Interview Questions

- 0of 0 votes
Write a function that does an in-order traversal of a tree and prints out the contents (Assume each node has 1 piece of content which is an integer).

Write this function without using recursion (you can assume a library that has stack/queue/list objects with some standard methods is available for use by you).

What is the maximum size your stack can grow to and what is the expected size that your data structure can grow to assuming that the tree has n nodes?

- 0of 0 votes
Find and fix the bugs in the following function that is supposed to remove the head element from a singly linked list.

`void RemoveHead (node * head) { free(head); head = head - > next; }`

- 0of 0 votes
Write a function that takes a string as an input and outputs an integer, e.g. turning "1234" into 1234.

- 0of 0 votes
Design your own String Pooling system. It should return a String with request of more length. String pool should have strings of different sizes available. When requested, it should just be returned to client and when client is done using string, it should be added back to string pool for other client to use.

- 0of 0 votes
Given a string, write a function to determine whether it is a valid IP address or not. Regex solutions are acceptable, but what other ways can it be done?

boolean isValidIP(String s) {

//code here

}

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

- 1of 1 vote
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).

- -3of 3 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.