Microsoft Interview - I

1. Given an Ellipse class can you derive a Circle class from it?
What all methods would you include in the circle class and what all in
ellipse?
Design a class of curve from which Circle and Ellipse can be inherited.


2. This contained series of questions on C++.
-What are virtual functions? Why are they used? Give examples.
-What are pure virtual functions and abstract classes? When do we use it?
-Where are virtual functions stored in the memory? How does the object knows
that the virtual function to be called is from base class or derived class?
-What is VTable (virtual table) and what does it do?


3. These were also series of Questions mostly on OS skills:
-What are DLLs? Why do we use them?
-How does DLL work? Can anybody call methods written in DLLs ?
-What are static and shared Library? Which is fast and why?
-Questions about paging, loading, linking etc.
-Concept of 32-bit OS, virtual memory, inter-process communication etc.

4. Given a BST (Binary search Tree) how will you find median in that?
Constraints:
-No extra memory.
-Function should be reentrant (No static, global variables allowed.)
-Median for even no of nodes will be the average of 2 middle elements and
for odd no of terms will be middle element only.
-Algorithm should be efficient in terms of complexity.

Write a solid secure code for it.

5. Modified 2 color sort problem i.e. you are given an array of integers
containing only 0s and 1s.You have to place all the 0s in even position and
1s in odd position. And if suppose, no. of 0s exceed no. of 1s or vice versa
then keep them untouched. Do that in ONE PASS and without taking extra
memory (modify the array in-place).
For e.g.
Input Array: {0,1,1,0,1,0,1,0,1,1,1,0,0,1,0,1,1}
Output Array: {0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,1}

Write a solid secure code for it.

6. You are given a Linked List and a function declaration as
node* KReverse(node* head, int k);

KReverse is a function that reverses the nodes of a Linked List k at a time
and then returns the modified Linked List.

For e.g.
Linked List : 1->2->3->4->5->6->7->8->9->10->11
For k = 2
Return Value: 2->1->4->3->6->5->8->7->10->9->11
For k = 3
Return value: 3->2->1->6->5->4->9->8->7->10->11

Write a solid secure definition for the function KReverse.

Constraints:
-If the no. of nodes in a link list is not a multiple of k then left-out
nodes in the end should remain as it is.
-You have to retain the memory address of the nodes without modifying it
i.e. you can't just interchange the values in the nodes.
-No extra memory allowed.


7.Suppose you are passing a string to a Formatter function. Get the
formatted news feed output string such that
-There should be one sentence per line.
-There shouldn't be any spaces i.e. the line shouldn't be blank.
For example:

Input String:
". ....West Indies reached the final of DLF series. .Lalu was invited
to IIM-A once again. . .. .. . Microsoft unveils Zune, an ipod killer. .
. . . "

Output String:

"West Indies reached the final of DLF series.
Lalu was invited to IIM-A once again.
Microsoft unveils Zune, an ipod killer."

Design and write solid secure code for the Formatter Function.

all the best

Microsoft Interview - 2

1.Given a string 'abcdef' and another string 'efg' remove all occurences of
the characters in 'efg' from 'abcdef'. Write 'to ship' code and give test
cases. Design a program to test any implementation of this problem

2.Given a unit square with a number of lines passing through it. These lines
are not parallel and they do not intersect within the square. They also
intersect with x=0 and x=1. Given a point I,j find the two closest lines to
it. Also describe what data structures you would use to store and solve
this.

3.Given a file with a lot of words (10 million) find out the top 10% most
frequently occuring words.


4.Given a word and a file containing words in the dictionary find anagrams of
that word.

5.Given a sorted, shifted array find the minimum element. Example from 34512
(the minimum is 1), 45123 (the minimum is 1) etc.

6.Given a set of numbers find the number that occurs more than N/2 number of
times.

Microsoft Interview - 3

Q1: given a string search it in a set of strings (say among 1000s of
string). What datastructure would you use to store those 1000 strings
and get the results fastest?

Q2: Reverse a linked list?

Q3: Find if there is a loop in a linked List?

Q4: given 2 arrays of no find if each of the two arrays have
the same set of integers ? Suggest a algo which can run faster
than NlogN ?

Q5: Validate a Binary search tree? ( as in the left- right child follow
the property )

Q6: Write a routine that takes as input a string such as ("aabbccdef"
and o/p "a2b2c2def" or "a4bd2g4" for "aaaabddgggg".

Q7: Given a NxN matrix with 0s and 1s. now whenever you
encounter a 0 make the corresponding row and column elements 0.
Flip 1 to 0 and 0 remains as they are.

for eg 1 0 1 1 0
0 1 1 1 0
1 1 1 1 1
1 0 1 1 1
1 1 1 1 1
results in

0 0 0 0 0
0 0 0 0 0
0 0 1 1 0
0 0 0 0 0
0 0 1 1 0

Q8: Given 2 set of arrays of size N(sorted +ve integers ) find the
median of the resultent array of size 2N. (dont even think of
sorting the two arrays in a third array , though u can sort them).
Try smthng better than order N ..order LogN >:) .

Q9: given 1000 bottles of juice, one of them contains poison and tastes
bitter. Spot the spoiled bottle in minimum sips?
(hint: try to mix them)

Q10: whats the diff b/w a thread and a process? are Word and
powerpoint different processes or threads of a single process?

Q11: How does a spell cheaker routine (common to both, word and
Powerpoint) used.. I mean is the code copied 2 times for each of the
processes in teh main memory, if they are diffent processes or how is
it used if they are threads.

all the best.

Microsoft Interview - 4

Q1. IF the Fibonacci series is 1,2,3,5,8,13,.....
then 10 can be written as 8 + 2 ==> 10010
17 can be written as 13 + 3 + 1 ==> 100101


Q2. I have a file in which there are supposed to be 4 billion numbers,
starting from 1 to 4,000,000,000 but unfortunately one number is missing,
i.e there are only 3,999,999,999 numbers, I need to find the missing
number. In this question he asked me concepts like fopen, what will be the
size of such a file and how such a big file will get loaded into RAM,
and also concepts of logical/virtual/physical memory and memory paging.


Q3. I have an array consisting of 2n+1 elements. n elements in it are
married, i.e they occur twice in the array, however there is one element
which only appears once in the array. I need to find that number in a
single pass using constant memory. {assume all are positive numbers}
Eg :- 3 4 1 3 1 7 2 2 4
Ans:- 7


Q4. There is a temple, whose premises have a garden and a pond. It has 4
idols, each of Ram, Shiv, Vishnu and Durga. The priest plucks x flowers
from the garden and places them in the pond. The number of flowers
doubles up, and he picks y flowers out of them and goes to offer it to
Lord Ram. By the time he reaches to the pond, he finds the remaining
flowers also have doubled up in the meantime, so he again picks up y from
the pond and goes to Lord Shiv.This process is repeated till all the Gods
have y flowers offered to them, such that in the end no flower is left in
the pond. Find x and y.

Q5.There is a central server and some clients connected to it. All the
changes made to data occur at the server, and all the clients have just
read access. You have two options:-
1. Push :- The server keeps pushing data to the clients.
2. Pull :- The client keeps requesting the server to send data.
What are the advantages and disadvantages of each type.
Design a system which uses both the push as well as pull strategy.

Q6.Implement atof function.
Write solid secure code only.

Q7. Find the first unrepeated character in a string of English language in O(n).

Q8. Difference between a 32-bit OS and a 64-bit OS.
Some questions on address space and fetch cycles/ Instruction Set of a
processor.

Microsoft Campus Recruitment Questions

# How did you first get interested in Computer Science?

# What do you like to do best related to computers now (programming, administration, testing, manage projects, etc)? What is it about that area that you specifically enjoy?

# What is your strongest programming language (Java, ASP, C, C++, VB, HTML,C#, etc.)?

# When is the last time you coded in C/C++? What is the most lines of original C/C++ code you have personally written in one project? How confident are you in your ability to write C or C++ without a reference?

# How do you test your code?

# Are there particular areas of technology you’re interested in, or specific products you would want to work on at Microsoft?

# Describe your ideal job.

# Given a simple program designed to take inputs of integers from 1-1000 and to output the factorial value of that number, how would you test this program? You do not have access to the code. Please be as specific as possible.

# Is there anyone else in your set of peers or friends who you would like to recommend as a great candidate for Software Development positions at Microsoft? If so, please list their name and email address below.

# What is your expected date of graduation if you are still in school? If you have already graduated, what was your graduation date?

Microsoft Interview Questions and Answers

# How could you determine if a linked list contains a cycle in it, and, at what node the cycle starts?

There are a number of approaches. The approach I shared is in time N (where N is the number of nodes in your linked list). Assume that the node definition contains a boolean flag, bVisited.
struct Node
{
...
bool bVisited;
};

Then, to determine whether a node has a loop, you could first set this flag to false for all of the nodes:
// Detect cycle
// Note: pHead points to the head of the list (assume already exists)
Node *pCurrent = pHead;
while (pCurrent)
{
pCurrent->bVisited = false;
pCurrent = pCurrent->pNext;
}

A much better approach was submitted by 4Guys visitor George R., a Microsoft interviewer/employee. He recommended using the following technique, which is in time O(N) and space O(1).

Use two pointers.

// error checking and checking for NULL at end of list omitted
p1 = p2 = head;

do {
p1 = p1-gt;next;
p2 = p2-gt;next->next;
} while (p1 != p2);

p2 is moving through the list twice as fast as p1. If the list is circular, (i.e. a cycle exists) it will eventually get around to that sluggard, p1.

# How would you reverse a doubly-linked list?

This problem isn't too hard. You just need to start at the head of the list, and iterate to the end. At each node, swap the values of pNext and pPrev. Finally, set pHead to the last node in the list.

Node * pCurrent = pHead, *pTemp;
while (pCurrent)
{ pTemp = pCurrent-gt;pNext;
pCurrent-gt;pNext = pCurrent->pPrev;
pCurrent-gt;pPrev = temp;

pHead = pCurrent;

pCurrent = temp;
}

# Assume you have an array that contains a number of strings (perhaps char * a[100]). Each string is a word from the dictionary. Your task, described in high-level terms, is to devise a way to determine and display all of the anagrams within the array (two words are anagrams if they contain the same characters; for example, tales and slate are anagrams.)

Begin by sorting each element in the array in alphabetical order. So, if one element of your array was slate, it would be rearranged to form aelst (use some mechanism to know that the particular instance of aelst maps to slate). At this point, you slate and tales would be identical: aelst.
Next, sort the entire array of these modified dictionary words. Now, all of the anagrams are grouped together. Finally, step through the array and display duplicate terms, mapping the sorted letters (aelst) back to the word (slate or tales).

Microsoft Aptitude Questions

# Mike has $20 more than Todd. How much does each have given that combined they have $21 between them. You can't use fractions in the answer.(Hint: This is a trick question, pay close attention to the condition)


# Here are four dogs, each at the counter of a large square. Each of the dogs begins chasing the dog clockwise from it. All of the dogs run at the same speed. All continuously adjust their direction so that they are always heading straight towards their clockwise neighbor. How long does it take for the dogs to catch each other? Where does this happen? (Hint: Dog's are moving in a symmetrical fashion, not along the edges of the square)


# If you had an infinite supply of water and a 5 quart and 3 quart pail, how would you measure exactly 4 quarts?


# If you are on a boat and you throw out a suitcase, will the level of water increase?


# On an average, how many times would you have to open the Seattle phone book to find a specific name?


# There are 3 ants at 3 corners of a triangle, they randomly start moving towards another corner. What is the probability that they don't collide?


# If you look at a clock and the time is 3:15, what is the angle between the hour and the minute hands? ( The answer to this is not zero!)


# What new feature would you add to MS WORD if you were hired?


# Why did you pick the school you graduated from?


# How would you weigh a plane without using scales?


# How would you move Mt. Everest?


# MIT math graduates bump into each other at Fairway on the upper west side. They hadn't seen each other in over 20 years.

The first grad says to the second: "how have you been?"
Second: "Great! I got married and I have three daughters now"
First: "Really? how old are they?"
Second: "Well, the product of their ages is 72, and the sum of their ages is the same as the number on that building over there.."
First: "Right, ok.. oh wait.. hmmmm.., I still don't know"
second: "Oh sorry, the oldest one just started to play the piano"
First: "Wonderful! my oldest is the same age!"
Problem: How old are the daughters?

# Why are beer cans tapered at the top and bottom?


# Why is it that hot water in a hotel comes out instantly but at home it takes time?


# How many times a day a clock's hands overlap?

Microsoft Interview Process

Hi,

Microsoft Interview process Depends on the position. If your technical you better know your weaknesses. Microsoft doesn't try to intimidate you, but they do ask detailed programming questions. Be able to go to the white board and code and/or answer logic scenarios.

The basic process, which can differ, is that you are placed in a room where 4 to 5 different people will come in and interview you. The questions are range from behavior to technical depending on the position.

If you are going for a programming position, expect to meet with at least 3 program managers. If a weakness is spotted they typically pass that information on to the next person to see how weak you are in a certain area.

But again. The goal is not to be a hard ass. And if you are weak in an area that doesn't mean you won't get the job - unless it directly applies to your job - but rather they want to make sure they know the candidate they are getting.

Suggestions ::

Refresh your algorithm and data structure knowledge ( binary trees, hashes, doubly linked stuff etc).

Data Structures, Data Structures, Data Structures.

Algorithms, Algorithms, Algorithms.You need to be good on data structure and C++ classes Ability to write code that not only works but has error handling as well. Analytical ability, thinking under pressure

Microsoft Interview Process

Hi,

Microsoft Interview process Depends on the position. If your technical you better know your weaknesses. Microsoft doesn't try to intimidate you, but they do ask detailed programming questions. Be able to go to the white board and code and/or answer logic scenarios.

The basic process, which can differ, is that you are placed in a room where 4 to 5 different people will come in and interview you. The questions are range from behavior to technical depending on the position.

If you are going for a programming position, expect to meet with at least 3 program managers. If a weakness is spotted they typically pass that information on to the next person to see how weak you are in a certain area.

But again. The goal is not to be a hard ass. And if you are weak in an area that doesn't mean you won't get the job - unless it directly applies to your job - but rather they want to make sure they know the candidate they are getting.

Suggestions ::

Refresh your algorithm and data structure knowledge ( binary trees, hashes, doubly linked stuff etc).

Data Structures, Data Structures, Data Structures.

Algorithms, Algorithms, Algorithms.You need to be good on data structure and C++ classes Ability to write code that not only works but has error handling as well. Analytical ability, thinking under pressure

Microsoft Interview Questions

These Are one of the Microsoft Interview Questions, if you attended Microsoft interview recently, please share you interview questions with us through comments or mail them at kchaitanyya@gmail.com

Round 1:


1. What are your interests? ( as in academics/topics)


2. Given a string, search it in a set of strings (say among 1000s of string). What data structure would you use to store those 1000 strings and get the results fastest?


Answer:I answered hash tables but he said suggest a better
one.He said suggest a better one and then gave me one
Tree sort of DS and then asked me to compare the two.



3. Reverse a linked list?


4. Find if there is a loop in a linked List?


5. Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than NlogN ?


6. Validate a Binary search tree? ( as in the left- right child follow the property )


Well i gave a the some weird eg where the struct was not
a Binary tree but if passed through the test will give
positive results.then he asked me to solve for that too.



Round 2:

The interviewer gets a bit serious with each stage. He will test ur work for all possible set of inputs.

Prologue: Well in my case he started with how they require not only a programmer but a designer and coder who writes perfect code.


1. Write a routine that takes input as a string such as


"aabbccdef" and o/p "a2b2c2def"
or
"a4bd2g4" for "aaaabddgggg"


write it perfectly as if it should ready to be shipped after you code it.


2. In the same Question (q1) why will u o/p "abc" for the i/p "abc" instead of "a1b1c1" ?


3. Given a NxN matrix with 0s and 1s. now whenever you encounter a 0 make the corresponding row and column elements 0.

Flip 1 to 0 and 0 remains as they are.

for example
1 0 1 1 0
0 1 1 1 0
1 1 1 1 1
1 0 1 1 1
1 1 1 1 1

results in

0 0 0 0 0
0 0 0 0 0
0 0 1 1 0
0 0 0 0 0
0 0 1 1 0



Round 3:


1. Some Questions on the projects listed on your resume?


For me some Qs on DB Lock Manager?



2. Given 2 set of arrays of size N(sorted +ve integers ) find the median of the resultent array of size 2N.
(dont even think of sorting the two arrays in a third array , though u can sort them. Try something better than order N ..order LogN )

3. Given 1000 bottles of juice, one of them contains poison and tastes bitter. Spot the spoiled bottle in minimum sips?


4. Whats the difference b/w a thread and a process? are Word and PowerPoint different processes or threads of a single process?


5. How does a spell checker routine (common to both, word and PowerPoint) used? I mean is the code copied 2 times for each of the processes in the main memory, if they are different processes or how is it used if they are threads.

Microsoft Freshers Interview Questions

There will be 3 interviews:- The first two are compulsory, if you do well in these, you will be called for the 3rd one.

First Interview:

1. If the Fibonacci series is 1,2,3,5,8,13,..... then 10 can be written as 8 + 2 ==> 10010 and 17 can be written as 13 + 3 + 1 ==> 100101. Got it??
The Question was, given n, I need to get all possible representations of n in Fibonacci Binary Number System.
as 10 = 8 + 2 ==> 10010
also 10 = 5 + 3 + 2 ==> 1110

2. I have a file in which there are supposed to be 4 billion numbers, starting from 1 to 4,000,000,000 but unfortunately one number is missing,i.e there are only 3,999,999,999 numbers, I need to find the missing number. In this question he asked me concepts like fopen, what will be the size of such a file and how such a big file will get loaded into RAM,and also concepts of logical/virtual/physical memory and memory paging.

3. I have an array consisting of 2n+1 elements. n elements in it are married, i.e they occur twice in the array, however there is one element
which only appears once in the array. I need to find that number in a single pass using constant memory. {assume all are positive numbers}

Eg :- 3 4 1 3 1 7 2 2 4
Ans:- 7

4. There is a temple, whose premises have a garden and a pond. It has 4 idols, each of Ram, Shiv, Vishnu and Durga. The priest plucks x flowers from the garden and places them in the pond. The number of flowers
doubles up, and he picks y flowers out of them and goes to offer it to Lord Ram. By the time he reaches to the pond, he finds the remaining flowers also have doubled up in the meantime, so he again picks up y from
the pond and goes to Lord Shiv.This process is repeated till all the Gods have y flowers offered to them, such that in the end no flower is left in the pond. Find x and y.



Second Interview :


1. Asked About My Btech Final year Project. Design your own compiler that does trace back optimization.Give hypothetical test cases for your compiler.

2. There is a central server and some clients connected to it. All the changes made to data occur at the server, and all the clients have just read access.
You have two options:-
1. Push :- The server keeps pushing data to the clients.
2. Pull :- The client keeps requesting the server to send data.

What are the advantages and disadvantages of each type.Design a system which uses both the push as well as pull strategy.


3. Implement atof function.Write solid secure code only.


Third Interview:


1. a) What is your CGPA?

b )What are your immediate goals?

c) What are your long term goals?

d) And some more questions on academics.

2. Find the first unrepeated character in a string of English language in O(n).

3. Simple questions on Probability.

4. Difference between a 32-bit OS and a 64-bit OS. Some questions on address space and fetch cycles/ Instruction Set of a processor.

Microsoft Written Test Questions

Microsoft visited our campus for recruitment. Here are the 3 questions asked for us in written round. Unfortunately, i couldn't clear the written round. Anyone, please post the answers if you know them.


1. There are 2 sorted arrays A and B of size n each. Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n). Full points are given for the solution bearing efficiency O(log n). Partial points for the efficiency O(n).


2. Given a string *Str of ASCII characters, write the pseudo code to remove the duplicate elements present in them. For example, if the given string is "Potato", then, the output has to be "Pota". Additional constraint is, the algorithm has to be in-place( no extra data structures allowed) . Extend your algorithm to remove duplicates in the string which consisted of UNICODE characters.


3. Given that, there are 2 linked lists L1 and L2. The algorithm finds the intersection of the two linked lists. i.e' "L1 intersection L2 " ( similar to intersection of 2 sets ). Write all the possible test cases involved in the above given problem.

Microsoft Intern Interview Questions

# Implement stack using linked list.

# Give 5 test cases when it will work and when it won’t.

# How many matches will be played in a knockout tournament between 9 teams (get the general formula for n teams).

# What are greedy algorithms? Give examples.

# Given the English dictionary and a string, find all the correct English words possible with the letters of the string.

# Given an array of strings, print them vertically.

E.g. cat, an, cool 
c a c
a n o
t o
l


# What are the parameters required to implement a strcpy function?

# An array is of size N with integers between 0 and 1024(repetitions allowed). Another array of integers is of size M with no constraints on the numbers.
Find which elements of first array are present in the second array.
(If you are using extra memory, think of minimizing that still, using bitwise operators)

Questions of Microsoft campus interviews

Here are some technical questions Microsoft interviewers frequently asking.

1. What's the difference between a linked list and an array?
2. Implement a linked list. Why did you pick the method you did?
3. Implement an algorithm to sort a linked list. Why did you pick the method you did? Now do it in O(n) time.
4. Describe advantages and disadvantages of the various stock sorting algorithms.
5. Implement an algorithm to reverse a linked list. Now do it without recursion.
6. Implement an algorithm to insert a node into a circular linked list without traversing it.
7. Implement an algorithm to sort an array. Why did you pick the method you did?
8. Implement an algorithm to do wild card string matching.
9. Implement strstr() (or some other string library function).
10. Reverse a string. Optimize for speed. Optimize for space.
11. Reverse the words in a sentence, i.e. "My name is Chris" becomes "Chris is name My." Optimize for speed. Optimize for space.
12. Find a substring. Optimize for speed. Optimize for space.
13. Compare two strings using O(n) time with constant space.
14. Suppose you have an array of 1001 integers. The integers are in random order, but you know each of the integers is between 1 and 1000 (inclusive). In addition, each number appears only once in the array, except for one number, which occurs twice. Assume that you can access each element of the array only once. Describe an algorithm to find the repeated number. If you used auxiliary storage in your algorithm, can you find an algorithm that does not require it?
15. Count the number of set bits in a number. Now optimize for speed. Now optimize for size.
16. Multiple by 8 without using multiplication or addition. Now do the same with 7.
17. Add numbers in base n (not any of the popular ones like 10, 16, 8 or 2 -- I hear that Charles Simonyi, the inventor of Hungarian Notation, favors -2 when asking this question).
18. Write routines to read and write a bounded buffer.
19. Write routines to manage a heap using an existing array.
20. Implement an algorithm to take an array and return one with only unique elements in it.
21. Implement an algorithm that takes two strings as input, and returns the intersection of the two, with each letter represented at most once. Now speed it up. Now test it.
22. Implement an algorithm to print out all files below a given root node.
23. Given that you are receiving samples from an instrument at a constant rate, and you have constant storage space, how would you design a storage algorithm that would allow me to get a representative readout of data, no matter when I looked at it? In other words, representative of the behavior of the system to date.
24. How would you find a cycle in a linked list?
25. Give me an algorithm to shuffle a deck of cards, given that the cards are stored in an array of ints.
26. The following asm block performs a common math function, what is it?
cwd xor ax, dx
sub ax, dx

27. Imagine this scenario:

I/O completion ports are communictaions ports which take handles to files, sockets, or any other I/O. When a Read or Write is submitted to them, they cache the data (if necessary), and attempt to take the request to completion. Upon error or completion, they call a user-supplied function to let the users application know that that particular request has completed. They work asynchronously, and can process an unlimited number of simultaneous requests.
28. Design the implementation and thread models for I/O completion ports. Remember to take into account multi-processor machines.
29. Write a function that takes in a string parameter and checks to see whether or not it is an integer, and if it is then return the integer value.
30. Write a function to print all of the permutations of a string.
31. Implement malloc.
32. Write a function to print the Fibonacci numbers.
33. Write a function to copy two strings, A and B. The last few bytes of string A overlap the first few bytes of string B.
34. How would you write qsort?
35. How would you print out the data in a binary tree, level by level, starting at the top?

Microsoft Job Inteview questions on Algorithms and Programming

# You're given an array containing both positive and negative integers and required to find the sub-array with the largest sum (O(N) ). Write a routine in C for the above.

# Given an array of size N in which every number is between 1 and N, determine if there are any duplicates in it. You are allowed to destroy the array if you like.

# Write a routine to draw a circle (x ** 2 + y ** 2 = r ** 2) without making use of any floating point computations at all

# Give a one-line C expression to test whether a number is a power of 2

# Given an array of characters which form a sentence of words, give an efficient algorithm to reverse the order of the words (not characters) in it.

# Give a very good method to count the number of ones in a "n" (e.g. 32) bit number

# Reverse a linked list.

# Insert in a sorted list

# Write a function to find the depth of a binary tree.

# Given two strings S1 and S2. Delete from S2 all those characters which occur in S1 also and finally create a clean S2 with the relevant characters deleted.

Latest Microsoft Interview Questions

# Given a Parent -Child binary tree ,build the child -sibling version of it? Minimize the space requirements wherever possible.
# Given a binary tree build a linked list of all its nodes such that the nodes of a level appear before the nodes of the next level?
# Given an infinite stream of bits with the bits being appended at the highest significant position. give an algorithm to to say whether the number formed by using the sequence of bits that had been processed till then, is divisible by 3 or not?
# Given a string S of words and no of character per line m ,with m being greater than the longest word in S,print S in a set of lines so that each line contains no more than m characters and no word split between 2 lines.
# Given an expression remove the unnecessary brackets in it with out creating an ambiguity in its execution.
input output
ex1: (a+(b)+c) a+b+c
ex2: (a*b)+c a*b+c
# Propose a tree based data structure to identify a node with nth rank with maximum efficiency .
# Given a string S of alphabets and 2 characters a,b find the minimum distance between instances of them such that position of a <= position of b.
# Given an array of size n with first l positions filled with characters and a string s ,replace all the instances of ’%’ with this string s,given that the length of the array is sufficient to handle these substitutions.
input output
eg: abcdef%ghi%—— and “ppp” abcdefpppghippp
# Given a binary tree verify whether it is a binary search tree or not?
# Write a C code to merge 2 binary search trees and do the same 2 merge linked lists.How is the former different when compared to the later.(Discuss the issues)