Booking.com Interview Question Software Engineers
Country: 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]));
}
);
}
}
import java.util.*;
import java.util.List;
public class HotelComparator implements Comparator<Hotel> {
public int compare(Hotel a, Hotel b)
{
return a.score- b.score;
}
}
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) {
Collections.sort(hotels, new HotelComparator());
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;
}
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]));
}
);
}
}
import 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
import java.util.*;
public class Main {
static class Node {
int id;
int score;
Node(int id, int score) {
this.id = id;
this.score = score;
}
}
static class NodeComparator implements Comparator<Node> {
public int compare(Node n1, Node n2) {
return n2.score - n1.score;
}
}
static Node getParentScore(int childId,
HashMap<Integer, Node> childParentMap,
HashMap<Integer, Node> dp) {
if (!childParentMap.containsKey(childId)) {
return null;
}
if (dp.containsKey(childId)) {
return dp.get(childId);
}
Node parent = childParentMap.get(childId);
Node grandParent = getParentScore(parent.id, childParentMap, dp);
if (grandParent != null) {
Node newParent = new Node(grandParent.id, grandParent.score + parent.score);
dp.put(childId, newParent);
return newParent;
}
dp.put(childId, parent);
return parent;
}
public static void main(String[] args) {
// [{0, 1, 10}, {1, 2, 20}, {3, 4, 10}, {7, 8, 5}] K = 2
int[][] hotels = new int[4][3];
hotels[0][0] = 0;
hotels[0][1] = 1;
hotels[0][2] = 10;
hotels[1][0] = 1;
hotels[1][1] = 2;
hotels[1][2] = 20;
hotels[2][0] = 3;
hotels[2][1] = 4;
hotels[2][2] = 10;
hotels[3][0] = 7;
hotels[3][1] = 8;
hotels[3][2] = 5;
int K = 2;
// loop over hotels and create child-(parent, score) mapping
HashMap<Integer, Node> childParentMap = new HashMap<>();
int rows = hotels.length;
int cols = hotels[0].length;
// O(N), N = number of hotels
for (int i = 0; i < rows; i++) {
Node parentScore = new Node(hotels[i][1], hotels[i][2]);
childParentMap.put(hotels[i][0], parentScore);
}
// O(N), O(N)
// hashmap will be from childid to Node
HashMap<Integer, Node> dp = new HashMap<>();
HashMap<Integer, Integer> parentScores = new HashMap<>();
for (int i = 0; i < rows; i++) {
Node parent = getParentScore(hotels[i][0], childParentMap, dp);
if (parentScores.containsKey(parent.id)) {
int prevScore = parentScores.get(parent.id);
if (prevScore < parent.score) {
parentScores.replace(parent.id, parent.score);
}
} else {
parentScores.put(parent.id, parent.score);
}
}
// O(N * log(N))
PriorityQueue<Node> parentNodes = new PriorityQueue<Node>(new NodeComparator());
for (Map.Entry<Integer, Integer> parentScoreEntry: parentScores.entrySet()) {
Node parentNode = new Node(parentScoreEntry.getKey(), parentScoreEntry.getValue());
parentNodes.add(parentNode);
}
while (!parentNodes.isEmpty() && K > 0) {
Node parentNode = parentNodes.poll();
System.out.println(parentNode.id + " " + parentNode.score);
K--;
}
}
}
import collections
import heapq
# print(id_score)
from collections import defaultdict, namedtuple
from operator import itemgetter
Hotel = namedtuple(typename='Hotel', field_names=('id', 'parent_id', 'score'))
# id_score = {0: 10, 1: 20, 3: 10, 7: 5, 8: 0, 2: 0, 4: 0}
# paert_to_child = {1: {0}, 2: {1}, 4: {3}, 8: {7}, 7: set(), 0: set(), 3: set()}
# without_parents = {8,2,4}
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)
)
id_score = defaultdict(int)
parent_to_child = defaultdict(set)
without_parents = set()
for hotel in hotels:
id_score[hotel.id] += hotel.score
without_parents.discard(hotel.id)
without_parents.add(hotel.parent_id)
parent_to_child[hotel.parent_id].add(hotel.id)
id_score2 = defaultdict(int)
for p in without_parents:
q = collections.deque()
q.append(p)
while q:
p1 = q.popleft()
for hotel in parent_to_child[p1]:
id_score2[p] += id_score[hotel] # Add child's score to parent's score
q.append(hotel)
items = [(-value, key) for key, value in id_score2.items()]
# Create a min heap
heapq.heapify(items)
# Extract the top k items from the min heap
k = 2 # Change this to the number of top items you want
top_k_items = []
for _ in range(k):
if items:
value, key = heapq.heappop(items)
top_k_items.append((key, -value))
print(top_k_items)
import collections
import heapq
# print(id_score)
from collections import defaultdict, namedtuple
from operator import itemgetter
Hotel = namedtuple(typename='Hotel', field_names=('id', 'parent_id', 'score'))
# id_score = {0: 10, 1: 20, 3: 10, 7: 5, 8: 0, 2: 0, 4: 0}
# paert_to_child = {1: {0}, 2: {1}, 4: {3}, 8: {7}, 7: set(), 0: set(), 3: set()}
# without_parents = {8,2,4}
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)
)
id_score = defaultdict(int)
parent_to_child = defaultdict(set)
without_parents = set()
for hotel in hotels:
id_score[hotel.id] += hotel.score
without_parents.discard(hotel.id)
without_parents.add(hotel.parent_id)
parent_to_child[hotel.parent_id].add(hotel.id)
id_score2 = defaultdict(int)
for p in without_parents:
q = collections.deque()
q.append(p)
while q:
p1 = q.popleft()
for hotel in parent_to_child[p1]:
id_score2[p] += id_score[hotel] # Add child's score to parent's score
q.append(hotel)
items = [(-value, key) for key, value in id_score2.items()]
# Create a min heap
heapq.heapify(items)
# Extract the top k items from the min heap
k = 2 # Change this to the number of top items you want
top_k_items = []
for _ in range(k):
if items:
value, key = heapq.heappop(items)
top_k_items.append((key, -value))
print(top_k_items)
{{
import collections
import heapq
# print(id_score)
from collections import defaultdict, namedtuple
from operator import itemgetter
Hotel = namedtuple(typename='Hotel', field_names=('id', 'parent_id', 'score'))
# id_score = {0: 10, 1: 20, 3: 10, 7: 5, 8: 0, 2: 0, 4: 0}
# paert_to_child = {1: {0}, 2: {1}, 4: {3}, 8: {7}, 7: set(), 0: set(), 3: set()}
# without_parents = {8,2,4}
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)
)
id_score = defaultdict(int)
parent_to_child = defaultdict(set)
without_parents = set()
for hotel in hotels:
id_score[hotel.id] += hotel.score
without_parents.discard(hotel.id)
without_parents.add(hotel.parent_id)
parent_to_child[hotel.parent_id].add(hotel.id)
id_score2 = defaultdict(int)
for p in without_parents:
q = collections.deque()
q.append(p)
while q:
p1 = q.popleft()
for hotel in parent_to_child[p1]:
id_score2[p] += id_score[hotel] # Add child's score to parent's score
q.append(hotel)
items = [(-value, key) for key, value in id_score2.items()]
# Create a min heap
heapq.heapify(items)
# Extract the top k items from the min heap
k = 2 # Change this to the number of top items you want
top_k_items = []
for _ in range(k):
if items:
value, key = heapq.heappop(items)
top_k_items.append((key, -value))
print(top_k_items)
}}
import collections
import heapq
# print(id_score)
from collections import defaultdict, namedtuple
from operator import itemgetter
Hotel = namedtuple(typename='Hotel', field_names=('id', 'parent_id', 'score'))
# id_score = {0: 10, 1: 20, 3: 10, 7: 5, 8: 0, 2: 0, 4: 0}
# paert_to_child = {1: {0}, 2: {1}, 4: {3}, 8: {7}, 7: set(), 0: set(), 3: set()}
# without_parents = {8,2,4}
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)
)
id_score = defaultdict(int)
parent_to_child = defaultdict(set)
without_parents = set()
for hotel in hotels:
id_score[hotel.id] += hotel.score
without_parents.discard(hotel.id)
without_parents.add(hotel.parent_id)
parent_to_child[hotel.parent_id].add(hotel.id)
id_score2 = defaultdict(int)
for p in without_parents:
q = collections.deque()
q.append(p)
while q:
p1 = q.popleft()
for hotel in parent_to_child[p1]:
id_score2[p] += id_score[hotel] # Add child's score to parent's score
q.append(hotel)
items = [(-value, key) for key, value in id_score2.items()]
# Create a min heap
heapq.heapify(items)
# Extract the top k items from the min heap
k = 2 # Change this to the number of top items you want
top_k_items = []
for _ in range(k):
if items:
value, key = heapq.heappop(items)
top_k_items.append((key, -value))
print(top_k_items)
shoudn't the resul should be [[2, 20], [4, 10]]?
- Anonymous January 30, 2022