Microsoft Interview Questions
- 0of 0 votes
AnswersConsider 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.
- Rob September 05, 2014 in United States| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 5of 5 votes
AnswersGiven 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.
- jeevanus September 04, 2014 in India for Microsoft CRM| Report Duplicate | Flag | PURGE
Microsoft SDE1 Algorithm Data Structures Sorting - -1of 3 votes
AnswersWhats 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 } }
}
- gdg August 31, 2014 in United States| Report Duplicate | Flag | PURGE
Microsoft - 0of 0 votes
AnswersDesign a thread safe hash table from ground up.
- Poison August 27, 2014 in United States for Cloud
Follow up question: How do you design it without using any locks.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven a doubly linked list, copy the list.
- Poison August 27, 2014 in United States for Cloud
Edit:
Struct node{
node *pNext;
node *pPrev;
node *pRandom;
};
pRandom has connection to any random nodes.
Write a program to clone this list.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - -3of 3 votes
Answersdesign a durable API
- careercup2003 July 31, 2014 in United States| Report Duplicate | Flag | PURGE
Microsoft Java Developer - 0of 0 votes
Answersweb-based chatroom application
- careercup2003 July 31, 2014 in United States| Report Duplicate | Flag | PURGE
Microsoft Java Developer Algorithm - 0of 0 votes
Answersgiven 50K static online web pages, how do I identify all of them that have a phone numbers (assme 10 dights in a row)
- careercup2003 July 31, 2014 in United States| Report Duplicate | Flag | PURGE
Microsoft Java Developer Ideas - 0of 2 votes
AnswersGiven 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.
- abcd July 21, 2014 in United States
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| Report Duplicate | Flag | PURGE
Microsoft Algorithm - 0of 0 votes
AnswersAn input file called input.txt consists of data in the following format:
- Nascent July 19, 2014 in India
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#.| Report Duplicate | Flag | PURGE
Microsoft - 5of 5 votes
AnswersHow to find median of a stream of integers....
- Kavita July 08, 2014 in India
interviewer was not interested using insertion sort....
Any better way to do this??| Report Duplicate | Flag | PURGE
Microsoft Computer Scientist - 2of 2 votes
AnswersI was asked to design an application that sends a message to two friends if they come within two miles of each other.
- gdg June 28, 2014 in India
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| Report Duplicate | Flag | PURGE
Microsoft - 0of 0 votes
AnswersI was asked to design an application that sends a message to two friends if they come within two miles of each other.
- gdg June 28, 2014 in India
I gave him a solution indicating the data structures used to maintain the friend list and model of the solution .| Report Duplicate | Flag | PURGE
Microsoft - 2of 2 votes
AnswersA quadra tree is a tree where each node has atmost 4 child nodes(similar to a binary tree which has atmost 2 child nodes).
- gdg June 28, 2014 in India
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.| Report Duplicate | Flag | PURGE
Microsoft - 1of 1 vote
AnswersGiven 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).
- unordered_map June 17, 2014 in United States| Report Duplicate | Flag | PURGE
Microsoft Software Engineer Intern Algorithm - 0of 0 votes
AnswersBelow is the hash :
- maccaroni June 11, 2014 in United States
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.| Report Duplicate | Flag | PURGE
Microsoft Scientific Officer Algorithm - 0of 0 votes
AnswersWrite 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.
- warunthambi June 10, 2014 in India for teamviewer| Report Duplicate | Flag | PURGE
Microsoft Developer Program Engineer Coding - 0of 0 votes
AnswersImplement a class that does string manipulation by overloading the following operators: <<, >>, = and ==. For example consider the following code:
- warunthambi June 10, 2014 in India for teamviewer
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.| Report Duplicate | Flag | PURGE
Microsoft Developer Program Engineer Coding - 0of 0 votes
AnswersWrite a class that represents a minimal heap. The heap class should at a minimum support the following methods:
- warunthambi June 10, 2014 in India for teamviewer
- 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.| Report Duplicate | Flag | PURGE
Microsoft Developer Program Engineer Coding - 1of 1 vote
AnswersGiven a BST, find out the minimum length form root to leaf with sum S. Note that:
- Nascent May 29, 2014 in India
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 ?| Report Duplicate | Flag | PURGE
Microsoft SDE1 - 1of 1 vote
AnswersImplement thread-safe circular queue that has 2 methods Read & Write n bytes.
- Goooogle2014 May 29, 2014 in United States for Azure
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..| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Coding - 0of 0 votes
AnswersR4 | Q2. Given a BST, find out the minimum length form root to leaf with sum S. Note that:
- dutta.dipankar08 May 19, 2014 in India for MS Office Platform
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.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersRound 4( 2h 30 min)
- dutta.dipankar08 May 19, 2014 in India for MS Office Platform
===================
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).| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersR3 | 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.
- dutta.dipankar08 May 19, 2014 in India for MS Office Platform
(Note : Min-Heap + List )| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersR3 | Q3. What the different issue in multi-threading ? What is the difference between mutex and semaphore.
- dutta.dipankar08 May 19, 2014 in India for MS Office Platform| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersR3 | Q2. Reverse a 32-bit integers. write code for it.
- dutta.dipankar08 May 19, 2014 in India for MS Office Platform| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersRound 3:(1.h 15min)
- dutta.dipankar08 May 19, 2014 in India for MS Office Platform
===================
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.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswerR2 | Q3. Design a Chip-Encryption system. Which will do following operation:
- dutta.dipankar08 May 19, 2014 in India for MS Office Platform
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.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersR2 | 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.
- dutta.dipankar08 May 19, 2014 in India for MS Office Platform| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersRound 2:(1.h 15min)
- dutta.dipankar08 May 19, 2014 in India for MS Office Platform
===================
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]| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm