http://www.mitbbs.com/article_t/JobHunting/33000125.html

Total 4 questions.

--------------------------------------------------------------
Question 1:

1. What is the runtime complexity for the code below?

2. What is the space complexity for the code below?


Queue<TreeNode> queue = new LinkedList<BinaryTree.TreeNode>() ;
public void myMethod(TreeNode root) {
    if (root == null)
        return;
    queue.clear();
    queue.add(root);
    while(!queue.isEmpty()){
        TreeNode node = queue.remove();
        if(node.left != null) queue.add(node.left);
        if(node.right != null) queue.add(node.right);

--------------------------------------------------------------
Question 2:

1. What is the runtime complexity for the code below?

// Precondition: array[] is sorted
int search(int array[], int numberToFind, int min, int max)
{
  while (max >= min)
    {
      int index = midpoint(min, max);
      if(array[index] == numberToFind)
        return index; 
      else if (array[index] < numberToFind)
        min = index + 1;
      else         
        max = index - 1;
    }
    // numberToFind was not found
System.out.println("Not Found");

--------------------------------------------------------------
Question 3:

Amazon is a service oriented company. All services need a Load Balancer to 
distribute load among different servers. The question is to design a data 
structure for developing a Load Balancer. Load Balancer performs following 3
operations.

    boolean addServer(String hostId) - If host is already added to Load 
Balancer return false else add this host and return true.
    boolean deleteServer(String name) - If host is not in Load Balancer 
return false else delete this host and return true.
    String getRandomServer() - return a random host from the lists of hosts 
in Load Balancer. 

All the above operations should be performed in constant time. Please assume
you have a function Random.random(i) which returns a random number from 0 
to i.

  /*
   * Please fill in the methods of this class.
   * Add any class members which you would think is necessary to perform 
these operations
   */
   class LoadBalancer{
      /*
       * Operation should run in O(1) time 
       */
       boolean addServer(String hostId){
           return false;
       }
      /*
       * Operation should run in O(1) time 
       */
       boolean deleteServer(String hostId){
           return false;    
       }
      /*
       * Operation should run in O(1) time 
       */
       String getRandomServer(){
           return null;   
       }
   }

Example Input and Output:

   addServer("host1") -> true
   addServer("host2") -> true
   addServer("host3") -> true
   addServer("host2") -> false //since host2 was already added

   getRandomServer() -> host2 //random host from host1,host2,host3
   getRandomServer() -> host3 //random host from host1,host2,host3

   deleteServer("host1") -> true
   deleteServer("host2") -> true
   deleteServer("host1") -> false //since host1 was already deleted

--------------------------------------------------------------
Question 4:

Amazon needs a simple service to create, read, update and delete customer 
addresses.

1. Write the interface for this service. What methods are needed? What 
parameters would each method require and what data would each method return?

2. Using the following assumptions, describe how you would design your 
system:

You need to store 10 TB of addresses. Your service must support 10,000 
transactions per second. Each of your databases can only handle 1TB of data.
Each of your application servers can only handle 1,000 TPS