Nancy公司的一个员工去微软的面世题（zz）

ganjike

There was first an email test which had to be completed in one hour. If you
failed this there was a second online test (I don't know the details of that :)  
). Then there was a face-to-face interview with 4 different people for 4 more  
tests, where you are expected to solve the problem on the spot (ie oral test,  
not a paper test) and write code on the whiteboard.

  

Here's the email test:

  

1. Write a function in C/C++ that takes in an array of values and returns a
list of all character sequences with more than 2 letters that appear in more
than one array value.  Ex. input of ("a_williams", "will_01", "will_01_iam")
would return ("wil", "will", "ill", "iam").

  

For extra credit:

  

1a. Order the results in descending order based on the number of input values  
each sequence matched.

  

1b. Prune the results by removing all results that are a substring of another  
result that matched the same number of input values.  In the above example
"wil" and "ill" would both be discarded because they are both a substring of
"will" and all 3 values match 3 input strings

  


Here's the interview tests:

  

* you have a scale and 5 marbles, one of which is slightly heavier than the
others. Using the scale, how many comparisons do you need to make to identify
the heavier one? How about if you have 7 marbles? How about 10? What is the
maximum number of marbles that you can deal with in three measurements?
  
* Sort a vector of integers which only contains 0s and 1s (you can give more  
answers but they expect an in-place sorting of O(n) complexity). Code on the
whiteboard.
  
* At a party there are some regular people and a celebrity. Some people know  
each other, others don't. Everybody knows the celebrity, the celebrity doesn't
know anybody. You have a vector of all the persons at the party and a
function knows(A, B) which returns true if person A knows person B. Write a function  
to find the celebrity. Code on the whiteboard. (it's ok to mention O(n*n), I
also found a O(n*log) but they expect a O(n) algorithm)
  
* Make the design diagram for a Tetris game (identify the entities involved
and the responsibilities of each one) Name the design patterns used, if any.
Draw it on the whiteboard.