## Microsoft Interview Questions

- 0of 0 votes
Given a very large binary number which cannot be stored in a variable, determine the remainder of the decimal equivalent of the binary number when divided by 3. Then generalize to remainder of any number 'k'

- 0of 0 votes
Given a pre-order traversal, construct a binary search tree in O(n) time.

- 0of 0 votes
Given a large text file, find an efficient algorithm to find the least distance(measured in number of words) between any two given words.

- 1of 1 vote
You are given a text file. You have to return the list of starting index of the given word in text file. Design an efficient DS for that.

Example :-

Text file content : “geeks for geeks”

word : “geeks”

List : {0,10}

- 0of 0 votes
In a file, there are two columns, first column has some word (String) and 2nd column has some value (Double).

Example :-

ABC 23.4

ERF 34.89

WERT 122.9

Now user wants some arithmetic operations like

1) ABC + ERF = 23.4 + 34.89 = 58.29

2) ABC – WERT = 23.4 – 122.9 = -99.5

Design an efficient DS for these kind of operations.

- 0of 0 votes
Implement a queue using only one stack.

- 0of 0 votes
It’s a two player game. Both the players are equally intelligent to win the game. Give n no. of stones. A player can choose either 1 stone or k stones or l stone (1<k<l). Suppose player 'A' starts game then challenge was to identify the player who will win the game. Player who picks the last 1 stone or last k stone or last l stones win the game.

- 0of 0 votes
Design bus booking system:- Each row has x seat. If customer wants K seats if you have K consecutive seats available, reserve them. Otherwise give seats from any row.

- 0of 0 votes
There is a bridge and N no. people takes (a1,a2,—an) time to cross it and there are K torch and at any time x no of people can pass the bridge and it takes maximum of x people time to cross it. Minimum time required for N persons to cross the bridge.

- 0of 0 votes
There is a graph where each node represents a city and it contains specific no. of people. A tournament is going on and each match is playing in one city. All city’s people gather to watch match. Traffic department wants to manage how many people travel through city x if match is playing in city y for each x. City x and y can be any city.

- 0of 0 votes
Got Sp00ked by MS simple question..

Eight Ball problem, find Minimum steps to determine the heaviest one.

Anyone know the answer is 2 in case of 8 balls.. Question is code getHeavy when number of balls are not determined.

int getHeavy(List<Integer> balls){

// Your solution

}

- 1of 1 vote
Design a mall where there are 'm' entry gates and 'n' exit gates. There can be only 'x' number of people inside it. No more then 'x' people can be inside mall at any time.

- 0of 0 votes
How will you design a true collar?

- 0of 0 votes
Given an array of co ordinates (x,y). WAP to figure out if a square can be formed from any four points.

- 0of 0 votes
Given a 2d matrix and 4 points. WAP to figure out if they are row wise, column wise of diagonally wise consecutive.

- 0of 0 votes
Find the number of ways you can have breakfast in 'n' days, given Bread-butter can be eaten every day, Pizza can be eaten every alternate day and Burger can be eaten every two days.

- 0of 0 votes
/*Find minimum size of text window which contain all keywords of a search query from document.

Order of keywords don't matter.

Input:

Document: "MS(1) x y Is MS(5) x y MS(8) x Is Awesome x y z Awesome"

doc index dictionary:

{

Keyword: Index Position for keyword in doc

"MS": [1,5,8],

"Is": [4,10]

"Awesome": [ 11, 15] (n)

}

Search Input 1 : "MS is" ( k)

Result: "Is MS Ms" --> [Ms: 5 ; "Is" : 4] --> 2

Search Input 2: "Ms is Awesome",

Result : "MS x is Awesome" --> [Ms:8, Is: 10, Awesome: 11] ---> 4

for -> n

n^k

[1 4 5 8 10 11 15]

*/

- 0of 0 votes
Design an IEvictionPolicy interface that allows users to perform put , get, delete functions based on user specified eviction policy.

Tried to use the strategy pattern here but the interviewer wasn't happy. He did not want me to have reference to the cache in the eviction policy's concrete implementation

- 1of 1 vote
Given input - xyzonexyztwothreeeabrminusseven as a string, return an integer as the sum of all numbers found in the string

Output - 1 + 23 + (-7) = 17

- 1of 1 vote
For a given Sum and N print all the combinations

For Example Sum = 16 and N=2

Then Answer :

16,0

15,1

14,2

13,3

12,4

11,5

10,6

9,7

8,8

7,9

6,10

5,11

4,12

3,13

2,14

1,15

0,16`private void recursivePrint(int sum, int n, int data[], int len, int originalSum) { if (n == 0) { int sum1 = 0; for (int j = 0; j < len; j++) { sum1 += data[j]; } if (sum1 == originalSum) { for (int j = 0; j < len; j++) { System.out.print(data[j] + " "); } System.out.println(); } return; } for (int i = 0; i <=sum; i++) { // System.out.println(" len: "+len+" sum: "+sum+" i: " + i+" n:"+n) data[len] = i; recursivePrint(sum - i, n - 1, data, len + 1, originalSum); } } }`

Need a better solution so that we can store previous results by using hashmaps

- 0of 0 votes
Was asked to implement a code profiler, which takes a piece of code and provides the run time of a particular function in the code .

If a function is internally calling other functions, we just want to see the time spent executing the original function, and not the overall time.

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

- -1of 1 vote
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; }`

}

- 0of 2 votes
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.