CareerCup

shoudn't the resul should be [[2, 20], [4, 10]]?

Should the result should be [[2, 20], [4, 10]]

Take first k element from below array
arr.sort((a,b) => (b[2] + b[1]) - (a[2] + a[1])).map(item => [item[1], item[2]])

from collections import defaultdict
import heapq


a = [
    (3, 0, 14),
    (0, None, 10),
    (4, 0, 44),
    (6, None, 7),
    (10, 6, 13),
    (7, 6, 17),
    (2, None, 2),
    (14, 2, 9),
    (25, 14, 10),
    (12, 2, 10),
    (13, 0, 1),
    (14, 2, 9),
]

parent_hotels = dict()
parent_scores = defaultdict(int)

for hotel_id, parent_hotel_id, score in a:
    if parent_hotel_id is None:
        parent_hotels[hotel_id] = hotel_id
        continue
    actual_hotel_parent = parent_hotel_id

    while parent_hotel_id in parent_hotels and parent_hotels[parent_hotel_id] != parent_hotel_id:
        parent_hotel_id = parent_hotels[parent_hotel_id]

    parent_hotels[actual_hotel_parent] = parent_hotel_id
    parent_hotels[hotel_id] = parent_hotel_id

for hotel_id, parent_hotel_id, score in a:
    parent_scores[parent_hotels[hotel_id]] += score

parent_scores = sorted([(-score, parent_id) for parent_id, score in parent_scores.items()])
print(parent_scores)

k = 2
result = []
while k:
    score, parent_id = parent_scores.pop(0)
    if not (parent_scores and parent_scores[0][0] == score):
        k -= 1
    result.append((parent_id, -score))
print(result)

from collections import defaultdict
import heapq


a = [
    (3, 0, 14),
    (0, None, 10),
    (4, 0, 44),
    (6, None, 7),
    (10, 6, 13),
    (7, 6, 17),
    (2, None, 2),
    (14, 2, 9),
    (25, 14, 10),
    (12, 2, 10),
    (13, 0, 1),
    (14, 2, 9),
]

parent_hotels = dict()
parent_scores = defaultdict(int)

for hotel_id, parent_hotel_id, score in a:
    if parent_hotel_id is None:
        parent_hotels[hotel_id] = hotel_id
        continue
    actual_hotel_parent = parent_hotel_id

    while parent_hotel_id in parent_hotels and parent_hotels[parent_hotel_id] != parent_hotel_id:
        parent_hotel_id = parent_hotels[parent_hotel_id]

    parent_hotels[actual_hotel_parent] = parent_hotel_id
    parent_hotels[hotel_id] = parent_hotel_id

for hotel_id, parent_hotel_id, score in a:
    parent_scores[parent_hotels[hotel_id]] += score

parent_scores = sorted([(-score, parent_id) for parent_id, score in parent_scores.items()])
print(parent_scores)

k = 2
result = []
while k:
    score, parent_id = parent_scores.pop(0)
    if not (parent_scores and parent_scores[0][0] == score):
        k -= 1
    result.append((parent_id, -score))
print(result)

import java.util.*;
import java.util.List;

class Hotel {
    Integer hotelId;
    Integer parentHotelId;
    int score;

    public Hotel(Integer hotelId, Integer parentHotelId, int score) {
        this.hotelId = hotelId;
        this.parentHotelId = parentHotelId;
        this.score = score;
    }
}

public class TopKHotel {
    private int[][] getTopKHotel(List<Hotel> hotels, int k) {
        Map<Integer, Integer> curToParent = new HashMap<>();
        Map<Integer, Integer> curToRoot = new HashMap<>();

        for (Hotel h : hotels) {
            curToParent.put(h.hotelId, h.parentHotelId);
        }

        Map<Integer, Integer> scoreMap = new HashMap<>();
        for (Hotel h : hotels) {
            Integer rootId = null;

            if (curToRoot.containsKey(h.hotelId)) {
                rootId = curToRoot.get(h.hotelId);
            } else {
                rootId = findRoot(h.hotelId, curToParent);
                curToRoot.put(h.hotelId, rootId);
            }

            scoreMap.put(rootId, scoreMap.getOrDefault(rootId, 0) + h.score);
        }

        List<Map.Entry<Integer, Integer>> list = new ArrayList<>(scoreMap.entrySet());
        Collections.sort(list, (a, b) -> b.getValue() - a.getValue());

        int[][] ans = new int[k][2];

        for (int i = 0; i < Math.min(k, list.size()); i++) {
            ans[i][0] = list.get(i).getKey();
            ans[i][1] = list.get(i).getValue();
        }
        return ans;
    }

    private int findRoot(int hotelId, Map<Integer, Integer> curToParent) {
        if (curToParent.containsKey(hotelId) && curToParent.get(hotelId) != null) {
          return findRoot(curToParent.get(hotelId), curToParent);
        } else {
          return hotelId;
        }
    }

    public static void main(String[] args) {
        List<Hotel> hotels = List.of(
            new Hotel(3, 0, 14),
            new Hotel(0, null, 10),
            new Hotel(4, 0, 44),
            new Hotel(6, null, 7),
            new Hotel(10, 6, 13),
            new Hotel(7, 6, 17),
            new Hotel(2, null, 2),
            new Hotel(14, 2, 9),
            new Hotel(25, 14, 10),
            new Hotel(12, 2, 10),
            new Hotel(13, 0, 1),
            new Hotel(14, 2, 9)
        );
        TopKHotel solution = new TopKHotel();
        Arrays.asList(solution.getTopKHotel(hotels, 2)).forEach(
            i -> {
                System.out.println(String.format("hotel Id = %d, score = %d" , i[0], i[1]));
            }
        );
    }
}