## Booking.com Interview Question for Software Engineer / Developers

Country: India
Interview Type: Phone Interview

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

You want to find set intersection. Here is how we do it in ZoomBA.

``````(zoomba)userA = [ 2, 3, 1 ]
@[ 2,3,1 ] // ZArray
(zoomba)userB = [ 2, 5, 3 ]
@[ 2,5,3 ] // ZArray
(zoomba)userC = [ 7, 3, 1 ]
@[ 7,3,1 ] // ZArray
(zoomba)s = set()
{  } // ZSet
(zoomba)s += userA
{ 1,2,3 } // ZSet
(zoomba)s &= userB
{ 2,3 } // ZSet
(zoomba)s &= userC  // &= mutable intersection
{ 3 } // ZSet
(zoomba)``````

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

How do you and two sets without a loop?

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

This problem could be solved with the help of HashMap<Integer, Integer>.

Now suppose we have data from N users given to us. Our aim is to find List of hotels common to all the users.

For the 1st user: {2,3,1}
* Add the hotel-Id directly as key and instance-count as value. At the first iteration the map will look something like this:
2-->1
3-->1
1-->1

For the 2nd user: {2,5,3}
* Now check if the hotel-Id present in the hashMap, if not then ignore the element given, otherwise extract the data from the map and add (user-Id*hotel-Id) to the previous value. After the second iteration the map looks like this:
2-->3 {1 + (2*1)}
3-->3 {1 + (2*1)}
1-->1 {nothing happens to this, since this was absent in the second user list}

For the 3rd user: {7,3,1}
* Similar to the 2nd user we update the values for the common elements between the map keys and given hotel-Id array. After the third iteration the map looks like this:
2-->3 {nothing happens to this since this was absent in the second user list}
3-->6 {3 + (3*1)}
1-->1 {nothing happens to this since this was absent in the second user list}

similarly, iterate till the end of all the user arrays given.

Now at the end, we just need to figure out those keys which have value {n*(n+1)/2}. So for the above case, the result is {3}

RUN TIME: O(N) {where N is the sum of length of all the hotel-Ids}
SPACE: O(length of elements in first hotel-Id array)

Sorry for the lengthy explanation, but I feel I have made the logic clear. Feel free to drop comments in case of doubts.

Thanks

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

Why are you multiplying user id with hotel id ???

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

What if there are multiple hotel ID within on user list

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

``````public static Set<Integer> findCommonVisitedHotels(int[][] visitedHotels, int n) {
Map<Integer, Integer> commonHotelsMap = new HashMap<>();
for(int[] visitedHotel: visitedHotels) {
Arrays.stream(visitedHotel).distinct().forEach(hotel -> {
commonHotelsMap.put(hotel, commonHotelsMap.getOrDefault(hotel, 0) + 1);
});
}
return commonHotelsMap.entrySet().stream().filter(e -> e.getValue() == n).map(e -> e.getKey()).collect(Collectors.toSet());
}``````

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

``````import java.util.Map;
import java.util.HashMap;
import java.util.HashSet;

public class Intersect {

public void lookUpUsers(int[][] users){
// Define a HashMap to store our Hotels ID's and a counter
Map<Integer,Integer> hotels = new HashMap<Integer, Integer>();
// Since we don't know exactly how many arrays we're getting
// we need to iterate among all O(n^2), not the best performance
for( int i = 0; i<users.length; i++){
int[] values = users[i];
// Since a person can visit an hotel more than once,
// create a HashSet, this data structure stores unique keys
HashSet<Integer> uniqueVisitors = new HashSet<Integer>();
for( int j = 0; j < values.length; j++){
}
/**
* DEBUG only
System.out.println("Unique Visitors:");
for( Integer userId : uniqueVisitors ){
System.out.println( userId );
}
*/
// Grab our list of unique visitors
int visitors = 0;
for( Integer hotelId : uniqueVisitors ){
if( hotels.get(hotelId)!=null ){
visitors = hotels.get(hotelId) + 1;
} else {
visitors = 1;
}
hotels.put(hotelId, visitors);
}
}
// Grab our list of hotels
System.out.println("Unique Visitors by Hotel:");
for( int hotelId : hotels.keySet() ){
System.out.println("Hotel ID->" + hotelId + ", real visitors->" + hotels.get(hotelId));
}
// Finally, since we want the hotel that has been visited by all users,
// we need to search for that Hotel ID with unique visitors is equal to the size of Users array
for( int hotelId : hotels.keySet() ){
if( hotels.get(hotelId)==users.length ) {
System.out.println("Common Hotel ID->" + hotelId);
break;
}
}
}
public static void main(String[] args) {
int[][] users = { {2,3,1}, {2,5,3}, {7,3,1} };
Intersect intersect = new Intersect();
intersect.lookUpUsers(users);
}
}``````

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

{
var str = "Hello, playground"

func intersect( arr1:[Int], arr2:[Int]) ->[Int] {

if arr1.count == 0 {
return arr2
} else if arr2.count == 0 {
return arr1
}

var tempArray = [Int]()

for i in arr1 {
if arr2.contains(i) {
tempArray.append(i)
}
}

return tempArray
}

let a = [1,2,3]
let b = [2,5,3]
let c = [7,3,1]

var d = intersect(arr1: a, arr2: b)

print (d)

var e = intersect(arr1: d, arr2: c)}

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

``````create a hash map with key=hotel id and value=visitor count (let's call this hotelVisitCountMap)
for each user
{
create a hash set to hold the hotel ids (let's call this userHotelIds)
for each hotel visited
{
insert it into userHotelIds
}
iterate over the hash set userHotelIds
{
if the id is found in hotelVisitCountMap
{
increment the count for the id in the map
}
}
}
iterate over hotelVisitCountMap
{
if the count for the current item matches the number of users, output the key (hotel id)
}``````

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

There can be 2 solutions-

1- Sorting and comparing
a- SOrt any two array- O(nlogn)
b- find common of two sorted arrays and insert into the Set O(n)
c- Check for remaing arrays , whther elements of that array is present in the set or not. if yes then it is common element. O(n) for each new array

*set will not be modified after step b.

Time complexity O(nlogn) + O(n) ~= O(nlogn)

2- It can also be dome in O(n) time, by using hashmap and set-
a- Create an hash map of one array and aray element as key of the hashmap - O(n)
b- Traverse second array and check in hashmap for every element, if the key is present in hashmap then insert to the set. O(n)
Now you have set of common elements in 2 arrays.
c- Check for remaing arrays , whther elements of that array is present in the set or not. if yes then it is common element. - O(n) for each new array

*set will not be modified after step b.

Time complexity O(n) or O(k*n) ~= O(n) , where k is number of the arrays

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

``````<?php
\$userA=array(2,3,1);
\$userB=array(2, 5, 3);
\$userC=array(7, 3, 1);

sort(\$userA);
sort(\$userB);
sort(\$userC);

print_r(array_intersect(array_intersect(\$userA, \$userB),\$userC));
?>``````

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

<?php

\$userA = [2, 3, 1];
\$userB = [2, 5, 3];
\$userC = [7, 3, 1];

\$result = array_intersect(\$userA,\$userB,\$userC);

print_r(\$result);

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

``````var userA = [2, 3, 1];
var userB = [2, 5, 3];
var userC = [7, 3, 1];

var allID = userA.concat(userB).concat(userC);
var hash = {};

allID.forEach(d => {
if(hash[d]) hash[d] += 1;
else hash[d] = 1;
});

var arrOfObjKeys = Object.keys(hash);

arrOfObjKeys.reduce((a, b) => {
return hash[a] > hash[b] ? a : b;
});``````

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

var a=[2,3,1];
var b=[2,5,3];
var c=[7,3,1];

var stagingArray=[];

b.forEach(function(rec){
if(a.includes(rec))
{
stagingArray.push(rec);
}
});

console.log(stagingArray);

var finalArray=[];
stagingArray.forEach(function(record){

if(c.includes(record))
{
finalArray.push(record);
}
});
console.log(finalArray);

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

var a=[2,3,1];
var b=[2,5,3];
var c=[7,3,1];

var stagingArray=[];

b.forEach(function(rec){
if(a.includes(rec))
{
stagingArray.push(rec);
}
});

console.log(stagingArray);

var finalArray=[];
stagingArray.forEach(function(record){

if(c.includes(record))
{
finalArray.push(record);
}
});
console.log(finalArray);

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

``````var a=[2,3,1];
var b=[2,5,3];
var c=[7,3,1];

var stagingArray=[];

b.forEach(function(rec){
if(a.includes(rec))
{
stagingArray.push(rec);
}
});

console.log(stagingArray);

var finalArray=[];
stagingArray.forEach(function(record){

if(c.includes(record))
{
finalArray.push(record);
}
});
console.log(finalArray);``````

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

``````var a=[2,3,1];
var b=[2,5,3];
var c=[7,3,1];

var stagingArray=[];

b.forEach(function(rec){
if(a.includes(rec))
{
stagingArray.push(rec);
}
});

console.log(stagingArray);

var finalArray=[];
stagingArray.forEach(function(record){

if(c.includes(record))
{
finalArray.push(record);
}
});
console.log(finalArray);``````

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

In Java you can use Sets to both get rid of duplicates and find unique or common elements in multiple arrays:

``````public static void main(String[] args) {
Set<Integer> set1 = new HashSet<Integer>(Arrays.asList(2, 3, 1));
Set<Integer> set2 = new HashSet<Integer>(Arrays.asList(2, 5, 3));
Set<Integer> set3 = new HashSet<Integer>(Arrays.asList(7, 3, 1));
Set<Integer> commonSet = new HashSet<Integer>(set1);
commonSet.retainAll(set2);
commonSet.retainAll(set3);
System.out.println(commonSet);
}``````

retainAll: check caller Set with param Set and remove any elements not included in both
removeAll: check caller Set with param Set and remove any elements included in both

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

``````import java.util.*;

public class Solution {
public static void main (String args[]) {
Solution solution = new Solution();
solution.solve();
}

private Map<Integer, Set<Integer>> hotels;
private PriorityQueue<Node> queue;
public Solution() {
this.hotels = new HashMap<>();
this.queue = new PriorityQueue<>();
}
public void add(int userId, int hotelId) {
if (this.hotels.containsKey(hotelId)) {
}else{
Set<Integer>set = new HashSet<>();
this.hotels.put(hotelId, set);
}
}
public void solve() {
Iterator<Integer> iterator = hotels.keySet().iterator();
while(iterator.hasNext()) {
int hotelId = iterator.next();
int numberOfUsers = hotels.get(hotelId).size();
Node node = new Node(hotelId, numberOfUsers);
}
Node node = queue.poll();
System.out.println("Hotel "+node.hotelId +", has been visted by: "+node.numberOfUsers+" users");
}
private class Node implements Comparable<Node>{
int hotelId;
int numberOfUsers;
public Node (int hotelId, int numberOfUsers) {
this.hotelId = hotelId;
this.numberOfUsers = numberOfUsers;
}
@Override
public int compareTo(Node node) {
if (hotelId == node.hotelId)
return 0;
if (this.numberOfUsers < node.numberOfUsers)
return 1;
if (this.numberOfUsers > node.numberOfUsers)
return -1;
return 0;
}
}
}``````

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

``````print(getCommonHotel([2, 3, 1, 3], [2, 3, 5, 3, 1], [3, 7, 3, 1]), "\n");

sub getCommonHotel {
my @users_visited_hotels = @_;
my %common_hotels = ();     # This will contain all the hotels common for all users explored so far
my \$first_user_visited_hotels = shift(@users_visited_hotels );
for my \$hotel (@{\$first_user_visited_hotels}) {
\$common_hotels{\$hotel} = 1;
}
# Explore all the other users and
# keep eliminating hotels from first hotel list of user if they are not explored by any of next user.
for my \$user_visited_hotels (@users_visited_hotels) {
my %common_hotels_so_far = %common_hotels;
%common_hotels = ();
for my \$hotel (@{\$user_visited_hotels}){
if(exists \$common_hotels_so_far{\$hotel}){
\$common_hotels{\$hotel} = 1;
}
}
}
return(keys %common_hotels);
}``````

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

1. Make an 'alreadySeen' set and a 'result' set.
2. Iterate through each list. Check if the hotel id is in the 'alreadySeen' set. If it is, add it to the 'result' set, otherwise add the hotel id to 'alreadySeen'.
3. Return 'result' set.

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

``````my \$data = [
[ 2, 3, 1 ],
[ 2, 5, 3 ],
[ 7, 3, 1 ],
];

my %hash = ();
foreach my \$array ( @{ \$data } ) {
my %seen = ();
my @uniq = grep { !\$seen{ \$_ }++ } @{ \$array };

\$hash{ \$_ }++
foreach( @uniq );
}

my @keys = grep { \$hash{ \$_ } == scalar( @{ \$data } ) }
keys( %hash );

use Data::Dumper;
warn( Dumper( \@keys ) );``````

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

Ruby on rails

``````def common_ids(arr, number_of_users)

hotel_id_to_user_id_map = Hash.new { |h, k| h[k] = [] }
result = []

# arr[[2, 3, 1], [2, 5, 3], [7, 3, 1]]
# User1 visits [2, 3, 1], User2 visits [2, 5, 3]
# hotel_id_to_user_id_map[1] = [1, 3]
# hotel_id_to_user_id_map[3] = [1, 2, 3]

arr.each_with_index do |hotel_ids, index|
hotel_ids.each do |hotel_id|
unless hotel_id_to_user_id_map[hotel_id].include?(index+1)
#(index+1) refer user
hotel_id_to_user_id_map[hotel_id].push(index+1)
end
end
end

# store all keys where value contains all users
# keys --> hotel_ids
# value ----> user id
hotel_id_to_user_id_map.each do |key, array|
result.push(key) if array.length == number_of_users
end

result
end``````

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

1) Incase of Hotel IDs being distinct:

2 soltuions:
1) combine all the Hotel IDS in a arraylist and sort it. If any element in it repeats N times, it is common
2) Use HashMap and map counts of Hotel IDs with their count. After mapping, Elements in Hashmap with Hotel-Ids containing N count is the common ID.

2) Duplicate Hotel IDs:
Use HashMap. Map the Hotel ID of a user only once in Map, ie, count of Hotel ID can be max of 1 for an user. Hence, for a common Hotel ID for all N users, the count will be max of N and is the answer.

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

1) Incase of Hotel IDs being distinct:

2 soltuions:
1) combine all the Hotel IDS in a arraylist and sort it. If any element in it repeats N times, it is common
2) Use HashMap and map counts of Hotel IDs with their count. After mapping, Elements in Hashmap with Hotel-Ids containing N count is the common ID.

2) Duplicate Hotel IDs:
Use HashMap. Map the Hotel ID of a user only once in Map, ie, count of Hotel ID can be max of 1 for an user. Hence, for a common Hotel ID for all N users, the count will be max of N and is the answer.

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

use stack
push all hotel id for the first user.
pop ids if they do not exist in other users.
The stack will remain with ids common to all users

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

``````public List<Integer> common(List<List<Integer>> lists) {
if (lists.size() < 2) {
throw new IllegalArgumentException("input should have at least 2 lists");
}

HashSet<Integer> intersection = new HashSet<>(lists.get(0));

for (int i = 1; i < lists.size() && intersection.size() > 0; i++) {
List<Integer> currList = lists.get(i);
HashSet<Integer> currIntersection = new HashSet<>();
for (Integer num : currList) {
if (intersection.contains(num)) {
}
}
intersection = currIntersection;
}

return new ArrayList<>(intersection);
}``````

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

``````public List<Integer> common(List<List<Integer>> lists) {
if (lists.size() < 2) {
throw new IllegalArgumentException("input should have at least 2 lists");
}

HashSet<Integer> intersection = new HashSet<>(lists.get(0));

for (int i = 1; i < lists.size() && intersection.size() > 0; i++) {
List<Integer> currList = lists.get(i);
HashSet<Integer> currIntersection = new HashSet<>();
for (Integer num : currList) {
if (intersection.contains(num)) {
}
}
intersection = currIntersection;
}

return new ArrayList<>(intersection);``````

}

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

``````package com.practice.book;

/*Find out the common hotel id visited by all the users.
Arrays are un-sorted.
Case-1 - Unique hotel ids in one array
Case-2 - Duplicate hotel ids in one array*/

import java.util.HashSet;
import java.util.Set;

public class CommonVisitedHotel {

public static void main(String... args){

int[] userA = {2,3,1};
int[] userB = {2,5,3};
int[] userC = {1,3,1};

Set<Integer> set1 = new HashSet<Integer>();
Set<Integer> set2 = new HashSet<Integer>();

for(int i = 0; i<userA.length;i++){
}

for(int i = 0; i<userB.length;i++){
boolean contains = set1.contains(userB[i]);
if(contains){
}
}

set1.clear();

for(int i = 0; i<userC.length;i++){
boolean contains = set2.contains(userC[i]);
if(contains){
}
}

System.out.println(set1);

int arrayCount = 3;

for(int i = 0;i<arrayCount;i++){

}

}

}``````

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

``````/**
* complexity is O(n) while n is total count of numbers
*
* @author Omid Ghiasi Tarzi
*/
static Set<Integer> getCommons(Set<Set<Integer>> sets) {
Set<Integer> result = new HashSet<>();
for (Set<Integer> set : sets) {
result.retainAll(set);
}
return result;
}``````

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

Same with ArrayList is O(n^2)

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

``````from collections import defaultdict

def find_common_hotels(users):
no = len(users.keys())
d = defaultdict(set)
for user in users:
for hotel_id in users[user]:
ans = list(filter(lambda hid:len(d[hid])==no, d.keys()))
return ans

if __name__ == "__main__":
data = [
[
{'userA': [2, 3, 1], 'userB': [2, 5, 3], 'userC': [7, 3, 1]},
[3]
]
]

print('find common hotel ids:')
for d in data:
print('users log', d[0], 'result', find_common_hotels(d[0]), 'expected', d[1])``````

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

``````import java.util.*;

public class Main {

public static void main(String[] args) {
int[][] users = {{2, 3, 1}, {2, 5, 3}, {7, 3, 1}};
lookUpUsers(users);
}

private static void lookUpUsers(int[][] users) {
Map<Integer, Integer> map = new HashMap<>();

for (int i = 0; i < users.length; i++) {
int[] user = users[i];
HashSet<Integer> set = new HashSet<>();
for (Integer visitedHotelId : user) {
}
for (Integer visitedId : set) {
if (map.get(visitedId) != null) {
map.put(visitedId, map.get(visitedId) + 1);
} else {
map.put(visitedId, 1);
}
}
}
for( int hotelId : map.keySet() ){
if (map.get(hotelId).equals(users.length)) {
System.out.println(hotelId);
}
}
}
}``````

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.

### 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.

### 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.