## Booking.com Interview Question for Software Engineers

• 0

Country: Amsterdam
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

No. 2 is parent of 1. Also, 1 is parent of 0. So, 2 should have a total score of 30.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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]])

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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]));
}
);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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]));
}
);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

arr.sort(key=lambda tup: tup[2], reverse=True)

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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
if hotel.parent_id not in parent_to_children:

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``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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());
}

while (!parentNodes.isEmpty() && K > 0) {
Node parentNode = parentNodes.poll();
System.out.println(parentNode.id + " " + parentNode.score);
K--;
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

{{

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

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)

}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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

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)``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.