Microsoft

  www.microsoft.com
  www.microsoft.com

Interview Question

Engineer Interview(Student Candidate) Beijing, Beijing (China)

The student cards are 7 digit numbers, from 0000000 to

  9999999. If they are not in order and I would like to make it in-order. I will give you 6 helpers, how will you help me to solve this problem and the complexity of solving this problem.
Answer

Interview Answer

2 Answers

0

Assuming you have to sort all the cards - there are 10 millions!
Assuming eacg card is 0.1 mm tick - they'll stack in a pile of 1Km!

A good way to solve the problem is to send the 6 herpers to the college/university - to learn, and work to make some money. Then - with that money - make make them build a huge machine for sorting those cards...

No really: split the pile in 6 (or seven including your self) then again and again until you get to a smaller pile you may sort yourself easily - you get something like 50000 piles of 200 cards to start with! You'll have to use your 6-member team about 8000 time to sort those piles, and this is only the first level! And in the 200-card pile each member is on his/her own!

TH on Jun 11, 2010
0

For me "how will you help me to solve this problem and the complexity of solving this problem." is the key.

Assume we're at MS, why should I waste time with "the complexity of solving this problem."
I can contact some really smart people.

I'd define the data set better. How many cards total, currently random order or not, limited to some or all digits 1 to <10^8, etc

Then I'd call an analytics guy and ask if there is an algorithm to do this and can it parallelize into 7 threads.

Look up the algorithm in Bing.
Ask a coder how to implement it with 7 threads in pseudo code

Convert coder's pseudo code into instructions for the team.
Start sorting.

DBols on Sep 10, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.