# Placement Papers: Microsoft Interview Questions

Glide to success with Doorsteptutor material for competitive exams : get questions, notes, tests, video lectures and more- for all subjects of your exam.

These Are one of the Microsoft Interview Questions

Round 1:

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?

one. He said suggest a better one and then gave me one

Tree sort of DS and then asked me to compare the two.

Find if there is a loop in a linked List?

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?

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.

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.

In the same Question (q1) why will u o/p “abc” for the i/p “abc” instead of “a1b1c1”

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:

Some Questions on the projects listed on your resume?

For me some Qs on DB Lock Manager?

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)

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

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

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.