## Microsoft Interview Questions

- 0of 0 votes
Given an array of integer nos. All numbers are distinct.

WAP to find the two longest non-intersecting continuous subarrays

of equal size s.t. *all* elements of one of them are smaller than that of the other subarray:

a[i..i + k - 1] and a[j..j+k-1] where i + k <= j

s.t. a[i..i + k - 1] < a[j..j+k-1] or a[i..i + k - 1] > a[j..j+k-1]

and k is maximal

Example: a = {1,2,3, 7, 9, 8} then we have: {1, 2, 3} and {7, 9, 8}

a = {6, 5, 4, 1, 3, 7} then we have:

{6, 5} and {4, 1} or

{6, 5} and {1, 3} or

{5, 4} and {1, 3} ...

- 1of 1 vote
You are given a bag with N balls (where the value of N is unknown). Each ball in the bag is uniquely numbered with a value between 1 to N (inclusive) i.e. for each number between 1 and N, there is only one ball with that number. Now you pick a ball from the bag and see its number. You repeat this experiment K times. What is the best possible estimate of the value of N (the number of balls in the bag) you can make from the above experiment (of taking out a ball from the bag K times) in the following cases

a) With replacement

b) Without replacement.

- 3of 3 votes
Given a big rectangular plot of land that has rectangular or square sized buildings (all sides of every building are parallel to the big rectangular plot)... find the location and dimensions of the largest square that can be built in this rectangular plot

- 1of 1 vote
Find the number of bits set in a given character array.

After giving him a bit wise operation that was O(n) where n is the number of bits set, he wanted a more optimum solution

- 0of 0 votes
Given an array of integers and a number. WAP to find the pairs which sum of upto given number.

I solved it. Then he asked about writing test cases for this function.

I wrote below test cases

1.) All the elements should be number.

2.) Length of array should not be 0.

3.) Array itself should not be null.

4.) Given number, arrayLength can be represented by 32bits or 64 bits.

5.) number should not be negative.

6.) Input does not has pair, It should return false

7.) Input has pair, It should return true

8.) Input has all negative values and pair exists, then function should return true

9.) Input has all negative values and pair does not exists, function should return false

He told that he is looking for more test cases. Can you guys think of some more complex test cases.

- 0of 0 votes
How do you traverse a binary tree and output the nodes in-order? Do it in O(1) space.

Hint: You can modify the tree.

- 0of 0 votes
Insert a value into a sorted linked list.

Using C/C++ write a small function (around 5 lines in the body) to insert a value in a sorted linked list. Take into consideration that the list might be empty at first, and the function should cover the cases of insertion at the head and tail...

PS what the interviewer is looking for is the ability to write a small C/C++ code that solves the question and not the algorithm per se which is trivial

- 0of 0 votes
Given array of marks and array of time taken to finish the question, and a passing mark P maximize on marks which will get you P but minimizing the time t.

I tried to solve this by dividing the marks by time which will give factor of utilization of a particular question, and then partition the marks on P, and choose only marks less than P, try to sort the selected marks, time pair in small subset, and minimize on t. Is this a right approach.

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

- 1of 1 vote
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
Find whether a number (which is less than 10000) is a perfect square or not. If it is perfect square, calculate square root in O(1) without using sqrt function.

Example : 1024 => 32

1025=> not perfect square.

- 2of 2 votes
Given a dictionary that contains mapping of employee and his/her manager like this

Dictionary<string, string> employees = new Dictionary<string, string>()

{

{ "A","C" },

{ "B","C" },

{ "C","F" },

{ "D","E" },

{ "E","F" },

{ "F","F" }

};

Write a function to get no of employees under each manager in the hierarchy not just their direct reports.

In the above dictionary the root node/ceo is listed as reporting to himself.

Output should be a Dictionary<string,int> that contains this

A - 0

B - 0

C - 2

D - 0

E - 1

F - 5

- 0of 0 votes
Point errors (if any) in the following pointer code and explain what it does...

char* cp(char *a)

{

char *f;

f=(char*)malloc(strlen(a)*sizeof(char));

while(*a != 0)

{

*f=*a;

f++;

a++;

}

cout<< f;

return f;

}

- 0of 0 votes
You are tasked with implementing a method that returns the lowest possible number that could be generated after removing n characters from a string of digits. The method signature should look like:

`public static string GenerateLowestNumber(string number, int n)`

Where the number parameter is a string that contains a number (e.g. “4205123”), and the n parameter represents the number of characters to remove from the string. The goal of this method is to return the lowest number that can be generated by removing n characters from the number provided while keeping the positions of the remaining characters relative to each other the same (i.e. the method should remove n characters from the string, but it cannot re-order the characters).

For example, if number is “4205123” and n is 4, the lowest possible number that can be generated after removing any 4 characters is “012”. If number is “216504” and n is 3, the lowest possible number that can be generated after removing 3 characters is “104”.

- 0of 0 votes
Identify the flaws / limitations in the following ConvertToNumber method:

`public static bool ConvertToNumber(string str) { bool canConvert = false; try { int n = Int16.Parse(str); if (n != 0) { canConvert = true; } } catch (Exception ex) { } bool retval = false; if (canConvert == true) { retval = true; } return retval; }`

- 0of 0 votes
You are tasked with migrating data between two systems that store movie metadata. The first system, which you are to use as input, keeps their movie metadata in the following structure:

MovieName ContributorType ContributorName

Pulp Fiction Director Quentin Tarantino

Pulp Fiction Actor John Travolta

Pulp Fiction Actor Samuel L. Jackson

Titanic Director James Cameron

The second system, which you are to output to, uses the following object for movie information:`class MovieInformation { public string Name { get; set; } public string Director { get; set; } public List<string> Actors { get; set; } }`

The first system provides an IDataReader that lets you access their data. Their data is always sorted on MovieName. You can call Read on the IDataReader to move the cursor to the next entry, and you can call GetString on the IDataReader to get the movie name, contributor type, and contributor name. For example, with the above data, if you were to call:

`MovieDataReader dataReader = new MovieDataReader(); int movieNameOrdinal = dataReader.GetOrdinal( "MovieName" ); int contributorTypeOrdinal = dataReader.GetOrdinal( "ContributorType" ); int contributorNameOrdinal = dataReader.GetOrdinal( "ContributorName" ); while ( dataReader.Read() ) { string movieName = dataReader.GetString( movieNameOrdinal ); string contributorType = dataReader.GetString( contributorTypeOrdinal ); string contributorName = dataReader.GetString( contributorNameOrdinal ); }`

Then at the end of the first iteration of this while loop, movieName would be “Pulp Fiction”, contributorType would be “Director” and contributorName would be “Quentin Tarantino”.

The second system provides a single method for posting movie information to their DB. This method should only ever be called once per movie:`class MovieInformationDatabase { public void SaveMovieInformation( MovieInformation information ) { } }`

Implement a method that migrates all of the data from the first system to the second system

- 0of 0 votes
This was asked in an Online written test that was timed (60 mins). And this question was one among the three.

"Write a method to merge three sorted integer arrays into just one array"

Nothing more or less was given. Since it was a written test I assumed that the 1st array had space towards to end which can fit the other two arrays. I can code this but given the timer limitations (of 20 mins per question) I thought it was a bit too much for me to handle unless there is a more obvious way to do this. I did it using two arrays and using the resultant array, I merged it with the 3rd array. That was the best i could think of at that time.

- 0of 0 votes
Remove duplicates in an array of numbers. You can use a second array or the same array, as the output array. (I used a hash table to do this).

- 0of 4 votes
You have 9 balls. 8 of them weigh the same, but one of them weighs heavier than the other 8.

How can we find the heaviest weighted ball in no more than 2 operations?

- 1of 1 vote
A 2-D array of 1's and 0's is given. Find the row with max 1's. The array is sorted row wise (all 0's in a row are followed by all 1's).

- 0of 0 votes
Given an array with 10000 numbers from the range 1-10. WAP to sort them.

- 0of 0 votes
Describe in terms of computer architecture, how would you optimize running a search on a large database? Assume a PC with regular specs and database size of several terabytes.

- 1of 1 vote
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 ?

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