Booking.com Interview Question
Software EngineersCountry: Amsterdam
Interview Type: Phone Interview
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]));
}
);
}
}
shoudn't the resul should be [[2, 20], [4, 10]]?
- Anonymous January 30, 2022