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.