MICROSOFT 2007

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.

Q12. 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


Q13. 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.


Q14. 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


Q15. 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.

Q16.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.

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

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

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