Problem :
Google runs at scale across the world, and our load balancers have to make sure that requests are routed to the most appropriate nodes to do the processing. In this problem we’ll explore a simplified global load balancing setup. In all cases assume that input will be properly formed.
Input
Your program will be given input provided on stdin. The first line is a list of one or more node descriptions separated by commas. Each node has a space separated name, region, and zone; all of which are strings. Node names are unique, but zones and regions will not be. Regions contain one or more zones, and zones contain one or more nodes. For example:
<name1> <region1> <zone1>, <name2> <region1> <zone2>, ...
The rest of the lines are requests, which take the form:
<id> <type> <region> <zone>
...
<id>: An int that is a unique identifier for that request
<type>:The string GET or POST, indicating what kind of request it is
<region> <zone>: Strings representing the source region and zone of the request.
Output
Your program should generate a line of output for each request in the input (in any order) of the form:
<id> <name1> <name2> <name3> …
The id is the associated request, and the list of names are the query plan of nodes that request should be sent to in preference order. Typically a request will only be sent to the first node, but if that request fails it might be retried against further nodes in the list.
Your load balancer should aim for the following properties:
Requests must be evenly balanced between nodes within zones, for example if there are two nodes in a given zone, they should each appear first in the response lists for roughly 50% of the requests from that zone.
Query idempotence must be taken into account; POSTS are not retriable.
Requests should go to local zone nodes first, followed by local regions, followed by nodes not in the same region. The preference order is important, but do not worry about the order of nodes for requests that must leave the local zone; you may choose to balance them evenly as well but it is not a requirement. There may be some requests in zones and regions that have no nodes!
Google handles billions of requests per day, so your algorithm should be able to handle very large inputs.
Building
If possible your solution should contain a single executable solution which can be executed directly, but if you require a more sophisticated build system please include a Makefile or build.gradle file with a solution target that generates the executable.
Example
An example input might look like:
node1 region1 zone1,node2 region1 zone1,node3 region2 zone1,node4 region2 zone2
1 GET region1 zone1
2 POST region1 zone1
3 GET region2 zone3
4 GET region1 zone1
5 GET region2 zone1
6 POST region1 zone1
One valid solution is:
1 node1 node2 node4 node3
2 node2
3 node4 node3 node1 node2
4 node1 node2 node4 node3
5 node3 node4 node2 node1
6 node2
Another valid solution is:
1 node1 node2 node4 node3
4 node2 node1 node3 node4
3 node4 node3 node1 node2
5 node3 node4 node2 node1
2 node1
6 node2