## Microsoft Interview Questions

- 0of 0 votes
Implement Thread safe timer with start, stop and reset functionality.

- 0of 0 votes
There are two integer array arrayA and arrayB in the same size and two integer countA and countB. If arrayA[i] > arrayB[i], then we increase countA by 1, if arrayB[i]>arrayA[i], then we increase countB by 1. We will do nothing otherwise. Now you are given arrayA and arrayB, write a function to shuffle arrayA and so you can get countA > countB. Assume the input array are always valid, not empty and the input is guaranteed to have answer.

For example:

arrayA = [12, 24, 8, 32]

arrayB = [13, 25, 32, 11]

After shuffle:

arrayA = [24, 32, 8, 12]

arrayB = [13, 25, 32, 11]

- 0of 0 votes
Given two strings representing very large integer numbers, find the Product. Do not use BigInt.

`using System; public class Program { public static void Main() { Console.WriteLine( GetProduct("18888888888888888888888888","19999999999999999999999999999999999999999999999999999999999")); } public static string GetProduct(string s1,string s2) { int digit1=0; int digit2=0; char[] str1=s1.ToCharArray(); char[] str2=s2.ToCharArray(); int carry; string[] result=new string[str1.Length]; string finalproduct=string.Empty; int padding=0; for(int i=str1.Length-1;i>=0;i--) { digit1=str1[i]-'0'; string resval=string.Empty; carry=0; int j; for(j=str2.Length-1;j>=0;j--) { digit2=str2[j]-'0'; int product=digit1*digit2+carry; carry=product/10; resval=resval+(product%10); } if(carry>0) { resval=resval+carry; } for(int k=0;k<padding;k++) { resval="0"+resval; } result[i]=resval; padding++; } int max=findMax(result); int count=0; int car=0; while(count<max) { int sum=0; for(int x=0;x<result.Length;x++) { if(count<result[x].Length) { sum+=result[x][count]-'0'; } } sum+=car; car=sum/10; int p=sum%10; finalproduct=p+finalproduct; count++; } finalproduct=car+finalproduct; return finalproduct.TrimStart('0'); } public static int findMax(string[] s) { int max=0; for(int i=0;i<s.Length;i++) { int len=s[i].Length; max=Math.Max(max,len); } return max; }`

}

- 1of 1 vote
The following code has a bug, find it and fix it

`Release() { m_refCount--; m.lock(); if (m_refCount == 0) { free(this); return 0; } m.unlock() return m_refCount; }`

- 1of 1 vote
Write a function that receives a string an returns a list of all the substrings (of length >= 2) composed by consecutive characters. E.g input : "BCCDE" , output: ["BC","CD","CDE","DE"]

- 0of 0 votes
Given a linked list rotate it on the Kth element. For example, given 1->2->3->4->5 the list should be transformed into 4->5->1->2->3

- 2of 2 votes
Design a stock market system

- 0of 0 votes
Print elements of a matrix in spiral form.

- 0of 0 votes
Given 2 sorted linked lists, return a linked list that has all the elements and is sorted.

- 0of 0 votes
Given 3 strings "s" ssearch" and "sreplace", search string s for the substring ssearch and for every instance of ssearch you find, replace that part of the string with sreplace

- 0of 0 votes
Given an NxN Boolean matrix, find how many true regions there are in the matrixj

- 0of 0 votes
Create a basic minesweeper game that allows for board creation with custom height, width and number of mines. Create a <click> function that will take in a board location and return whether the user has won, lost, or the number of surrounding mines.

- 0of 0 votes
Given a string, print out all of the unique characters and the number of times it appeared in the string

- 0of 0 votes
What is the smallest number *n* by which the given number *x* must be divided to make it into a perfect square?

`n = find_number( x )`

- 0of 0 votes
Given a singly linked list of integers, write a function in java that returns true if the given list is palindrome, else returns false

- -2of 2 votes
Convert an unordered tree to a binary tree

- 1of 1 vote
merge two binary search trees

- 0of 0 votes
Sort a stack using only one other stack and no recursion.

- 1of 1 vote
Given a dictionary and an char array print all the valid words that are possible using char from the array.

Ex- char[] arr = {'e','o','b', 'a','m','g', 'l'}

Dict - {"go","bat","me","eat","goal", "boy", "run"}

Print - go, me, goal.

We can pre-compute as much we want but the query time must be optimal.

- 1of 1 vote
You are given a function getNum() that returns a random number in the range 1 to 10 million with repetitions. However, it may also return -1 when it no longer provides numbers. Write a function that calls getNum() continuously until it returns -1 (if a repetition, should not store it); as soon as u see -1, stop calling getnum() and print all the numbers seen so far in a sorted way. Condition: You have got very limited memory to work with.

- 1of 1 vote
You have a matrix that is sorted as such: For each value, every index to its right and below it must be larger than the current space's value. Likewise, all entries to its left and above it must be smaller than the current value. How would you go about searching this matrix for a specific number, given its sorted nature?

- 0of 0 votes
Just a disclaimer: I doubt you will ever get this interview question. My interviewer even started off by saying, "Hmm, well this isn't really fair, but..." So don't place too much stock in whether or not you can solve this.

Question: You have a group of pigs and buckets of food for said pigs. There are 1,000 buckets of food, and exactly 1 of them is poisoned. Your goal is to determine, by the end of 1 hour, which bucket is poisoned.

The poison takes 30 minutes to kill a pig, and you'd like to kill as few pigs as possible. The number of pigs you can test is limitless, and you can assign a number to each bucket and each pig so that you know exactly which pig ate from which bucket(s). You determine which buckets to feed to which pigs, but you have no timer and no way to guesstimate the time. What is the minimum number of pigs you need to use to solve the problem?

- 0of 0 votes
You are given an array of positive and negative integers. If a number n at an index is positive, then move forward n steps. Conversely, if it's negative, move backward n steps. Determine if there is a loop in this array.

For example, given the array [2, -1, 1, 2, 2], index 0 maps to index 2, 1 maps to 0, 2 maps to 3, and so on. There is a loop in this array because 0 maps to 2, 2 maps to 3, and 3 maps to 0 (use the modulo operator).

- 0of 0 votes
1. If I say quick sort takes O(e^n ) on the average, would I be wrong?

2. Do you think O( f ) is a good idea for real engineering?

3.Given a choice, what other 'order of' measure would you propose to use ?

4. Do you see a real problem with the modified *order of* ?

5. If you were to sort 10 elements, what sorting method would you have used?

6. If you were to sort 1 trillion unicode characters, what sorting method you would have used?

- 0of 0 votes
The actual problem from question?id=6289136497459200

Implement pow, with :`// Assume C/C++, as of now double pow ( double x, double power )`

No library functions allowed.

Should return : x^power

=== Edit ===

People took it a bit trivially, thus examples should help :`x = pow ( 4, 0.5 ) // x = 2.0 x = pow ( 8, 0.333333333 ) // 1.99999999986137069 x = pow ( 10.1 , 2.13 ) // 137.78582031242644`

- 1of 1 vote
determine whether a word is in a stored list;

the list doesn't fit into memory;

no disk access allowed, for lookups, memory access only;

no false positives allowed, false negatives ok

- 1of 1 vote
A list of words is given and a bigger string given how can we find whether the string is a permutation of the smaller strings.

eg- s= badactorgoodacting dict[]={'actor','bad','act','good'] FALSE

eg- s= badactorgoodacting dict[]={'actor','bad','acting','good'] TRUE

The smaller words themselves don't need to be permuted. The question is whether we can find a ordering of the smaller strings such that if concatenated in that order it gives the larger string

One more constraint - some words from dict[] may also be left over unused

- 0of 0 votes
Suggest a data structure and implement efficient phrase search along with word search in a huge chunk of text.

- 0of 0 votes
Design a system for searching strings in files present on a fileserver under a directory. there won't be any sub-directories. There could be more than thousand/lakhs files. And the file size could be in GBs. The matching line should be written to a single file. user will execute grep "string"

The sub-questions are

1) Design where the application executes on single machine.

2) Design where the application can execute on multiple machine.

3) Where could be the potential bottleneck.

4) What component would be bottleneck if 50 cores and slow disk.

5) What component would be the bottleneck if we 4 cores and fast disks.

- 2of 2 votes
You have two very large numbers that cannot be stored in any available datatypes. How would you multiply them?

How would you multiply more than two numbers?