## Microsoft Interview Questions

- -2of 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

- 0of 0 votes
An input file called input.txt consists of data in the following format:

22 Data Structures 45

23 Maths 2 52

23 Maths 3 57

22 English 51

26 Data Structures 72

23 Data Structures 63

26 English 81

Each line consists of three fields "Student ID," "Subject," and "Marks." "Student ID" and "Marks" are integers and "Subject" is a string that does not contain '|' or newlines (but might contain digits). There can be any number of students and up to 6 subjects. You have to read this file, and print the average marks in "Data Structures," across all students.

Thus for the above file, the output would be:

60

Kindly let me know the soln in C#.

- 3of 3 votes
How to find median of a stream of integers....

interviewer was not interested using insertion sort....

Any better way to do this??

- 1of 1 vote
I was asked to design an application that sends a message to two friends if they come within two miles of each other.

I gave him a solution indicating the data structures used to maintain the friend list and model of the solution .

He pointed out the cons of the solution and I modified the data structure

- 0of 0 votes
I was asked to design an application that sends a message to two friends if they come within two miles of each other.

I gave him a solution indicating the data structures used to maintain the friend list and model of the solution .

- 2of 2 votes
A quadra tree is a tree where each node has atmost 4 child nodes(similar to a binary tree which has atmost 2 child nodes).

A monitor screen (black and white) is represented by a qudra tree in the following way:

case 1: If the entire screen is white then the value in the root node is white.

similarly if the entire screen is black then the root stores black.

case 2: If the screen is neither completely black nor white then the screen is divided into 4 quadrants and the node has 4 child nodes each representing one of the quadrants.( the screen is recursively divided into subscreens).

Now given two screens represented by two quadra trees, return a quadra tree which represents the overlapping of the two screens.( assume when white and white overlaps results in white,black and white overlap results in black , black and black overlap results in black).

algo and code both have to be given.

- 0of 0 votes
Given an unsorted list with each node having a random pointer to another node, sort the list such that each node points to the next node in the list (n1->n2->n3).

- 0of 0 votes
Below is the hash :

c31843b739e61ec7bf5f63da93d97d0321f42f0304750c41ae88a3b04727ba21f5c7061e7517101f3b8f2fa53d3a32960c03e3b78112619b2674802429d831fcdb38fdff909bdcb6a2da09a462e35671c310e4954d1578a0194cf86b6e4b2550a58893d756c0d557451c487546b7a908377d5cc436daa6bd0cebbd8a2593db7ccc536aab131d8ca8c4c5daf505190d6e61a0c80b65d337e839c4c77c5a7f90daaf5aed8aff7d43876194d64a289cf42aedd977889120178500f4ef48aa3cdae78b1a4383d8f4f136f02c1d2d122f8819d8a2c66de0240ce2416ba43b0346de0450684f874fdb5d34b698e8a93ee45e15e8994c361f387a9fe94107b2d11f743cc34843d9031a7a0c01976ecf1f88056a6fa1b40744a88a37ee95fc66058370def144c686d692f012b07f56c497955a8fc40a51652240928e3c899aca8791a8e5f345f65745cfbec16f0446bafaa3e0593ab2d69e02b2562029178779e835cc933c99d289cc96b51f63a0c8abb01bc9df2659480fbb2f17f3b0817c807d222abbd58d1c60037ec5e35c06f2080a3b593928be4af515573024bdf5603f9696de81af8b065f6e2976a2efaa097d6613431c162c7acb00f7892acb3a2ffef15701bd

First, A series of string prefixes is generated with lengths increasing by 2. For example, if our secret word was "abcxy@hoho.com", we would generate:

ab abcx abcxy@ abcxy@ho ... ...... abcxy@hoho.com

Then, for every prefix s, following hash H is computed: md5(md5(e) + s + md5(s)) [where + is the string concatenation operator and e is "xxxxx@hehu.xxx.edu"].

Finally, all hash strings H are concatenated to form the long hash above....

For example, for abcxy@hoho.com, - the hash would be computed as

md5(md5('xxxxx@hehu.xxx.edu') + 'ab' + md5('ab')) +

md5(md5('xxxxx@hehu.xxx.edu') + 'abcx' + md5('abcx')) +

md5(md5('xxxxx@hehu.xxx.edu') + 'abcxy@' + md5('abcxy@')) +

...

For the sake of simplicity, you can assume that secret word only contains alphanumeric characters and these 4 characters: _ . @ +

and using e= xxxxx@hehu.xxx.edu, the hash is generated.

and we have to find out that secret word (from the hash).

These are the details I have researched:

Hash from MD5 is always 128 bits/16 bytes/32 ascii characters long

Collision Attack

Birthday Attack

Any Hidden paterns in the given hash

I am looking for a direction here. The given hash is exactly 896 letters long. Any ideas or redirects are much appreciated. Thanks.

- 0of 0 votes
Write a method that takes a given string and replaces all occurrences of one string with another string, returning the number of replaces made. For instance given the string “Microsoft” if you were to replace all occurrences of “ic” with “MSFT” the result would be “MMSFTrosoft” with a return value of 1. As part of a final solution please provide unit tests done as well as any test cases ran. Please note that you may not use String.Replace or string::replace depending upon the language you use; you must write this functionality yourself.

- 0of 0 votes
Implement a class that does string manipulation by overloading the following operators: <<, >>, = and ==. For example consider the following code:

StrShift example;

example = “Microsoft”;

printf(“\”example << 2\” results in %s\n“, example << 2);

In the above code the output would be “ftMicroso” which shows the last two characters of the string “Microsoft” rotated to the left of the string. Please note that state is maintained so two calls of example << 1 would give the same end result as calling example << 2 once. Consideration will be given to correctness, design, code readability as well as any unit testing. As part of a final solution please submit test cases you used to verify correctness in addition to any unit tests done.

- 0of 0 votes
Write a class that represents a minimal heap. The heap class should at a minimum support the following methods:

- AllocTinyHeap() which should initialize the heap with a given amount of bytes

- DeleteTinyHeap() which frees all memory associated with the heap

- TinyAlloc() which allocates a given number of bytes on the heap if there is room

- TinyFree() which frees a specific location on the heap

You may define whatever parameters are necessary for the above methods as well as write any additional methods. Overall consideration will be given to correctness, design, code readability as well as any unit testing done. As part of a final solution please submit test cases you used to verify correctness in addition to any unit tests done.

- 0of 0 votes
Write a method that takes a given string and replaces all occurrences of one string with another string, returning the number of replaces made. For instance given the string “Microsoft” if you were to replace all occurrences of “ic” with “MSFT” the result would be “MMSFTrosoft” with a return value of 1.

- 0of 0 votes
2. Write a method that takes a given string and replaces all occurrences of one string with another string, returning the number of replaces made. For instance given the string “Microsoft” if you were to replace all occurrences of “ic” with “MSFT” the result would be “MMSFTrosoft” with a return value of 1.

- 1of 1 vote
Given a BST, find out the minimum length form root to leaf with sum S. Note that:

a) Path from root to leaf node.

b) Sum of node of the path is S.

c) if multiple such path exist, print minimum length path.

d) What is advantage of BST rather than BT used for this algorithm, how it improve the performance. in BST, is it required to explore both side ?

- 1of 1 vote
Implement thread-safe circular queue that has 2 methods Read & Write n bytes.

The entire design and implementation was open for discussion.

Discussion went for locking, multi threading, boundary cases, all sets of issues related to multi threading..it was quite intense..

- 0of 0 votes
R4 | Q2. Given a BST, find out the minimum length form root to leaf with sum S. Note that:

a) Path from root to leaf node.

b) Sum of node of the path is S.

c) if multiple such path exist, print minimum length path.

d) What is advantage of BST rather than BT used for this algorithm, how it improve the performance. in BST, is it required to explore both side ?

e) Write working codes for it.

- 0of 0 votes
Round 4( 2h 30 min)

===================

Q1. You are given a Text, where all space, full stop and all punctuation mark is removed. You want to reconstruct the text by putting spaces between words.

A dict is given and following API < bool isInDect(word) > is also given.

a) Decide if the text can be converted a sentence with valid words or NOT.

b) Find how many way you can do the reconstruction of the text

c) Find what is the minimum number of space can be used for this reconstruction.

d) For case (c) find out the indexes where you suppose to put a space.

e) Now recover the text to sentence in place .

Subsequent Question:

1. Why Greedy technique will not work for this

2. yes ! Backtracking will work, what is the problem of using backtracking

3. Illustrate and explain how the solution is contracted from the Dynamic table.

4. Write the correct working code for (c),(d),(e).

- 0of 0 votes
R3 | Q4. You have a file with million words in it. Find most frequent 10 word in that file. Node that you can store all word in memory.

(Note : Min-Heap + List )

- 0of 0 votes
R3 | Q3. What the different issue in multi-threading ? What is the difference between mutex and semaphore.

- 0of 0 votes
R3 | Q2. Reverse a 32-bit integers. write code for it.

- 0of 0 votes
Round 3:(1.h 15min)

===================

Q1. In a plane n points (X and Y) is given. How will you find out maximum co-liner points. Extend this algorithms. it for point(x,y,z) in 3D plane.

- 0of 0 votes
R2 | Q3. Design a Chip-Encryption system. Which will do following operation:

1. Take a word from user

2. Encrypt the word by some Private or public key cryptography or any other algo.

3. Transmit the encrypted word by TCP or UDp or SSL.

Design the class diagram using OOD. Which design pattern you are using to achieve this.

- 0of 0 votes
R2 | Q2. You have a dictionary of words. Given a word, print all anagram are in dictionary . State the data structure to be used to solve this problem.

- 0of 0 votes
Round 2:(1.h 15min)

===================

Q1. Given a sorted array having duplicate elements,how would you find first index of a given element in O(nlogn).

Write code for it. Change the condition to find out last index of that elements.

[ Hint Binary search]

- -1of 1 vote
R1 | Q2. Find an element in a sorted rotated array in O(nlogn ) complexity.

- 0of 0 votes
Round 1: (1 h)

==============

Q1. Design a Garbage collector like java. How would you detect depended reference loop ?

Hist : Class design, Cycle detection algorithms for disjoint graph( List of connected graph)

- -2of 2 votes
There is a byte array which contains the character of one byte and two bytes. One byte character has range 0 to 127 and first character of 2 byte character is 128 to 255 and second byte character has range 0 to 255. Now, two pointers are given, one points to the start of the and another points to somewhere else.

Tell which character 2nd pointers points to?

- 0of 0 votes
Given a set of 21 tasks = {A, B,....Z} except I, O, U, X and Q. Each task requires 4 hours of processing. Except for tasks E, Y, P, R, W that require 8 hours of processing.

You have 3 machines to process these tasks = T1, T2, T3. T1 and T2 are available everyday for 8 hours. T3 is available only on Mon, Wed and Fri for 8 hours.

You are given 3 lists that indicate the dependency list among the tasks.

L1 = A->R->K->M (eg A can be completed if R is completed, R can be completed only if K is completed etc.)

L2 = N->G->V->E->Z->H

L3 = C->F->Y->D->J->P->T->S->W->B->C (cycle)

Each task needs one machine for its duration to complete.

Tasks cannot be resumed. Which means the 8 hour tasks cannot be executed over 2 days.

Each machine can process only one task at any time.

T1, T2 and T3 can process different tasks in parallel.

You are starting your schedule on a Wednesday.

Machines can be scheduled only during weekdays.

The first Monday in your schedule is a downtime for all the machines.

Given these constraints, write a program that generates a schedule between the tasks and machines such that all the tasks are completed at the

earliest.

- 1of 3 votes
Given a linked list with next and high pointers, populate high pointers to the next higher node, inplace and O(n).

- 0of 0 votes
Given a table of the form:

1 A,B,C,A,B

2 A,B,A,A,A

3 C,D,C

Give the number of duplicate characters, eg: for 1 there are 2 A's and 2 B's, so the result is 2

For 2 A is repeated 4 times so the result is 3

For 3, C is repeated twice so the result is 1

My suggestion was to use a CLRSQL function to calculate it