Booking.com Interview Question for Software Engineers


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

- Anonymous January 30, 2022 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Raj January 30, 2022 | Flag Reply
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]])

- Anonymous February 05, 2022 | Flag Reply
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)

- Anonyomous July 26, 2022 | Flag Reply
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)

- Anonyomous July 26, 2022 | Flag Reply
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]));
            }
        );
    }
}

- Patrick August 06, 2022 | Flag Reply
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]));
            }
        );
    }
}

- Anonymous September 10, 2022 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous December 07, 2022 | Flag Reply
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
    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

- Balaji February 07, 2023 | Flag Reply
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());
        parentNodes.add(parentNode);
      }
      
      while (!parentNodes.isEmpty() && K > 0) {
        Node parentNode = parentNodes.poll();
        System.out.println(parentNode.id + " " + parentNode.score);
        K--;
      }
  }
}

- Anonymous April 28, 2023 | Flag Reply
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
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)

- yasin September 23, 2023 | Flag Reply
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
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)

- yasin September 23, 2023 | Flag Reply
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
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)


}}

- yasin September 23, 2023 | Flag Reply
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
    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)

- Anonymous September 23, 2023 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

k

- tatkaltravels222 October 13, 2023 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More