Balaji
BAN USERimport heapq
from collections import defaultdict, namedtuple
from operator import itemgetter
Hotel = namedtuple(typename='Hotel', field_names=('id', 'parent_id', 'score'))
hotels = (
Hotel(id=0, parent_id=1, score=10),
Hotel(id=1, parent_id=2, score=20),
Hotel(id=3, parent_id=4, score=10),
Hotel(id=7, parent_id=8, score=5)
)
K = 2
id_to_score = defaultdict(int)
parent_to_children = defaultdict(set)
hotels_without_parent = set()
for hotel in hotels:
id_to_score[hotel.id] += hotel.score
hotels_without_parent.discard(hotel.id)
if hotel.parent_id not in parent_to_children:
hotels_without_parent.add(hotel.parent_id)
parent_to_children[hotel.parent_id].add(hotel.id)
def get_score(hotel_id):
return sum(get_score(child) for child in parent_to_children[hotel_id]) + id_to_score[hotel_id]
hotels_without_parent_scores = {hotel_id: get_score(hotel_id) for hotel_id in hotels_without_parent}
top_k = heapq.nlargest(n=K, iterable=hotels_without_parent_scores.items(), key=itemgetter(1))
for hotel_id, score in top_k:
print(f'{hotel_id} = {score}')
Output:
2 = 30
4 = 10
No. 2 is parent of 1. Also, 1 is parent of 0. So, 2 should have a total score of 30.
- Balaji February 07, 2023