What is CAP theorem? Describe how weakening consistency constraints can yield highly available distributed systems (e.g. databases). Give an example.

Describe consistent hashing and the advantages that it has over traditional hashing techniques. How can this technique help while scaling distributed systems, for example, distributed hash tables?

What is load balancing? Describe three different types of load balancing techniques? What problems can load balancing solve? What problems can it introduce?

Contrast and compare the features of Google's BigTable and Amazon's Dynamo databases

Explain the properties, advantages and drawbacks of these different types of NoSQL databases. Give examples of each type of database e.g. CouchDB is an example of a document Oriented Database.

• Document Oriented Database
• Ordered Key/Value Store
• Eventually consistent Key/Value Store
• Graph Database
• Object Database

Describe the congestion avoidance algorithm in the TCP protocol.

Design a system to efficiently calculate the top 1MM Google search queries and create a report of these. Additionally:

• You are given twelve servers
• Each has two processors, 4GB of ram and four 400GB hard drives.
• The machines are networked
• The log data as roughly 100 Billion log lines in it.
• The log data comes in twelve, 320 Gb files.
• Each line of the files has roughly 40 search queries
• You can only use open source software or software that you write.