You are given Racks holding N number of servers and each server has one service (app) running on it.
Given a service and number of hosts to replace, write a function to replace the hosts in such a way that maximum number of racks would be emptied
Racks:
rack aaa with timelines service
aaa-01.prod.twttr.net timelines
aaa-02.prod.twttr.net empty
aaa-03.prod.twttr.net empty
rack aab with timeslines service
aab-01.prod.twttr.net timelines
aab-02.prod.twttr.net timelines
aab-03.prod.twttr.net empty
rack aac with timelines and tweet service
aac-01.prod.twttr.net timelines
aac-02.prod.twttr.net empty
aac-03.prod.twttr.net tweets
Input
timelines
2
12
aaa-01.prod.twttr.net timelines
aaa-02.prod.twttr.net empty
aaa-03.prod.twttr.net empty
aab-01.prod.twttr.net timelines
aab-02.prod.twttr.net timelines
aab-03.prod.twttr.net empty
aac-01.prod.twttr.net timelines
aac-02.prod.twttr.net empty
aac-03.prod.twttr.net tweets
aad-01.prod.twttr.net timelines
aad-02.prod.twttr.net empty
aad-03.prod.twttr.net empty
First line is the service selected for hosts to replace, second line is max number of hosts to replace, third line total number of hosts in all racks, all subsequent lines are the entrees in following form
<rack-id>-<host_id>.prod.twttr.net <service_name> . String empty means no service running on the host
For the above input the right answer is [aaa-01.prod.twttr.net, aad-01.prod.twttr.net]
Explanation: We have to replace 2 hosts running the service timelines in a way that it would also make the rack empty. The hosts selected for replacement/retirement would cause rack aaa and aad to be empty as well
I was trying to identify the pattern for the above Question. Is there a pattern or we have to come up with own algorithm? Maybe Knapsack?
My Solution (not 100 percent right though)
"""
build rack_map dictionary
"<rack_id>": {
"services" = set('timelines', 'tweets') # services in the rack
"total_hosts": 3 # total hosts in a rack
"service_host_count": 2 # host count for selected service
"service_hosts": [] # list of hosts for selected service
}
"""
def vacate(service, replacement_count, hostname_service_list):
# Write your code here
#service_rack_map = {} #map which has only service count
rack_map = {} # service and other services
service_racks = []
for item in hostname_service_list:
splitted = item.split()
rack = splitted.split('-')[0]
app = splitted[-1]
hostname = splitted[0]
if rack in rack_map:
rack_map[rack]['services'].add(app)
rack_map[rack]["total_hosts"] += 1
if app == service:
rack_map[rack]['service_host_count'] += 1
rack_map[rack]['service_hosts'].append(hostname)
else:
if app == service:
rack_map[rack] = {"services":{app}, "total_hosts": 1, "service_host_count": 1, 'service_hosts': [hostname]}
else:
rack_map[rack] = {"services":{app}, "total_hosts": 1, "service_host_count": 0, 'service_hosts': []}
service_ordered_rack = sorted(rack_map.items(), key=lambda x: len(x[1]['service_hosts']))
ans = []
c = 0
for item in service_ordered_rack:
if item[1]['service_host_count'] == 0:
continue
if len(rack_map[rack]['services']) == 1 and service in rack_map[rack]['services']:
while c < replacement_count and item[1]['service_hosts']:
host = item[1]['service_hosts'].pop()
ans.append(host)
item[1]['service_host_count'] -= 1
c += 1
if not item[1]['service_hosts']:
rack_map[rack]['services'].remove(service)
if c >= replacement_count:
break
if c >= replacement_count:
return ans
else:
for item in service_ordered_rack:
if service in item[1]['services']:
while c < replacement_count and item[1]['service_hosts']:
host = item[1]['service_hosts'].pop()
ans.append(host)
item[1]['service_host_count'] -= 1
c += 1
if not item[1]['service_hosts']:
rack_map[rack]['services'].remove(service)
if c >= replacement_count:
break
return ans
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
service = input()
replacement_count = int(input().strip())
hostname_service_list_count = int(input().strip())
hostname_service_list = []
for _ in range(hostname_service_list_count):
hostname_service_list_item = input()
hostname_service_list.append(hostname_service_list_item)
result = vacate(service, replacement_count, hostname_service_list)
fptr.write('\n'.join(result))
fptr.write('\n')
fptr.close()