wayne
BAN USER- 0of 0 votes
AnswersSuppose the sub-requests can be queued at each server, and the servers are running all the time. Discuss feasible on-line algorithms that can achieve sub-optimal solutions with N ~ 10000.
- wayne in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - -1of 1 vote
AnswersA service system has n DIFFERENT servers; each one provides one unique service to the clients. Clients submit requests to the service system, each request may have multiple sub-requests; each sub-request is to a DIFFERENT server. A request can have at most n sub-requests. Each sub-request takes 1 time unit to finish at any server. The finish time of a request is the finish time of its LAST finished sub-request. The notation "total request finish time" is the sum of all requests' finish time.
- wayne in United States
1. Design an off-line algorithm to reorder the execution order of sub-requests on the servers, so that "total request finish time" can be minimized (if multiple solutions exist, only one solution is enough). Discuss the complexity of the algorithm.
Input format:
Line 1: number of requests.
Line 2: number of servers in the system, n.
Line 3 to (n+2): sub-requests (denoted with their parent requests’ IDs) at each server, the i’th line represents the sub-requests to be served at server ID = (i-2).
Output format:
Line 1 to (n-1): the execution order of sub-requests, so that “total request finish time” can be minimized.
Sample input 1:
4
4
1 2 3 4
3 2 1 4
4 2 1 3
2 3 4 1
Sample output 1:
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
(The “total request finish time” of input is 14; and output is 10).
Sample Input 2:
6
6
1 6 2
4 3 5 1
1 2
1 2 4 6
3
5 6
Sample Output 2:
6 1 2
3 1 4 5
1 2
6 1 4 2
3
6 5
(The “total request finish time” of input is 19; and output is 15).
2. Discuss feasible algorithms that can achieve sub-optimal solutions with N ~ 10000.
3. Suppose the sub-requests can be queued at each server, and the servers are running all the time. Discuss feasible on-line algorithms that can achieve sub-optimal solutions with N ~ 10000.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm
If he's asking you to do this:
input: a->b->c->d->e
output: e->d->c->b->a
do the following:
1. Get the length of the list: n.
2. swap the value in index 0 and index n-1:
e->b->d->d->a
swap the value in index 1 and index n-2:
e->d->c->b->a
...
(swap the value in ith and n-1-ith places until i == n/2)
the swap function is perfectly defined by Abhijit.
Time complexity: O(n^2).
A is the correct answer.
B: greater<>() takes 0 arguments. It has a member function operator() that takes two arguments, which returns true if its first argument compares greater than the second one using operator>, and false otherwise. The greater class does not have a constructor taking one argument.
D: remove_if is not a member function of vector class.
E: remove_if_greater does not exist in vector class.
Why choose A not C:
bind2nd(greater<int>(),50) and bind1st(less_equal<int>(), 50) are the unary function objects constructed from the binary function objects greater<int>() and less_equal<int>() by binding its 2nd/1st parameters to 50. So the above function objects can be considered as:
bind2nd(greater<int>(),50) "greater than 50?" (true if > 50)
bind1st(less_equal<int>(), 50) "greater than or equal to 50?" (true if 50<=)
Function
ForwardIterator remove_if(ForwardIterator first, ForwardIterator last, Predicate pred):
Applies pred to the elements in the range [first,last), and removes those for which it does not return false from the resulting range. The resulting range consists of the elements between first and the iterator returned by the function, which points to the new end of the range. So the elements between the new end and the old end should not be valid.
So,
std::remove_if(items.begin(), items.end(), std::bind2nd(std::greater<int>(), 50)) will remove the elements >50 in items, and return a new end of items. And erase() will remove the elements between the new end and the old end.
Think in these ways:
- wayne September 26, 20121. Large data storage with reliability
Use cloud service such as Azure as a reliable storage service provider
2. High speed access
Load balancing and caching, locality-based data storage if SkyDrive uses multiple data centers.
3. Security and access control
User access through login account, consider encryption on local copy of data.
4. Data consistency management logic
When multiple people are working on the same files, provide a locking mechanism to preserve data consistency.
5. Ease of use
Support of multiple running platforms, including operating systems, file systems, etc.