|
Title: Microsoft Interview - 3 Post by: Tanya on June 08, 2007, 11:59:57 PM 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. |