m******n
发帖数: 51 | 1 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 queue = new LinkedList() ;
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 | u***n
发帖数: 21026 | | S**********5
发帖数: 896 | | p*********g
发帖数: 2998 | 4 Q1, TIME 是o(n) space是o(n/2)
Q2 TIME是O(LOGN)
Q3 constant time-> HASHSET
Q4 interface addresses{
void create(int customerid, String addressID, String addressName)
String read(int customerid, String addressID)
void update(int customerid, String addressID,String addressName)
void delete(int customerid, String addressID)
}
2. 10 databases. 100 servers. 10 servers as one group. One group link to one
database. | z*u
发帖数: 329 | | j******g
发帖数: 1428 | |
|
