Bridgewater Associates, Inc. interview Questions (software developer).

I recently had a phone interview with Bridgewater Associates, Inc.

They called me at 4:00pm. There are three interviewers. The interview includes 10 minutes on my previous projects, 20 minutes on standard interview questions, 20 minutes about the job position and their team. When asking questions, they like to ask a simple question first, then trace down to the detail untill your head began to spin. They will give hints and lead you to the answer ... then... you know what? they ask a harder aditional question.

The followings are some of the interview questions:
1. If I dip a 10x10x10 Rubik's Cube into red int, how many of the 1000 cells will have red faces.
2. a bad king has a cellar of 1000 bottles of delightful and very expensive wine. a neighbouring queen plots to kill the bad king and sends a servant to poison the wine. (un)fortunately the bad king's guards catch the servant after he has only poisoned one bottle. alas, the guards don't know which bottle but know that the poison is so strong that even if diluted 1,000,000 times it would still kill the king. furthermore, it takes one month to have an effect. the bad king decides he will get some of the prisoners in his vast dungeons to drink the wine. being a clever bad king he knows he needs to murder no more than 10 prisoners - believing he can fob off such a low death rate - and will still be able to drink the rest of the wine at his anniversary party in 5 weeks time.
3. additional question: to increase your chance of living, which prisoner would you want to be?
4. What's the difference between Java and C#?
5. additional question: Why C++ have multi inheritance but Java don't have?
6. What's the difference between interface and abstract methods?
7. additional question: In what conditions you prefer abstract methods instead of interface?
8. additional question: What can interface do but abstract methods can't?
9. Given two arrays A and B. Array A is sorted with n empty elements at the end; while array B has total n unsorted elements. How can you merge A and B into a sorted array.
10. additional question: What's the Big Os of Selection sort, insertion sort, bucket sort?
11. A linked list has a loop in it, how can you find it?
12. additional question: suppose the linked list is super long, how can you find it the loop quickly?
13. Explain left join in sql.
14. Additional question: What's the difference between left join, right join, inner join, outer join and full join?
14. Additional question: How can join effect the query performance?