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)

- NoOne April 26, 2017 | Flag Reply
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++){
				uniqueVisitors.add(values[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);
	}
}

- Julio May 30, 2017 | Flag Reply
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)}

- Anonymous April 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 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

- LightRider April 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- General April 27, 2017 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

What if there are multiple hotel ID within on user list

- aPerson April 27, 2017 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- bitsevn April 08, 2019 | Flag
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)
}

- AnonyMouse April 28, 2017 | Flag Reply
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

- azambhrgn May 17, 2017 | Flag Reply
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));
?>

- Anonymous May 20, 2017 | Flag Reply
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);

- Anonymous May 29, 2017 | Flag Reply
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;
});

- Emmanuel Amodu June 21, 2017 | Flag Reply
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);

- Anonymous June 28, 2017 | Flag Reply
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);

- himanshu June 28, 2017 | Flag Reply
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);

- himanshu June 28, 2017 | Flag Reply
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);

- Anonymous June 28, 2017 | Flag Reply
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

- Acilikola July 20, 2017 | Flag Reply
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.add(1, 2);
		solution.add(1, 3);
		solution.add(1, 1);
		solution.add(2, 2);
		solution.add(2, 5);
		solution.add(2, 3);
		solution.add(3, 7);
		solution.add(3, 3);
		solution.add(3, 1);
		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)) {
			this.hotels.get(hotelId).add(userId);
		}else{
			Set<Integer>set = new HashSet<>();
			set.add(userId);
			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);
			this.queue.add(node);
		}
		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;
		}
	}
}

- w.kinaan July 30, 2017 | Flag Reply
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
    # Start with first user as base condition
    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);
}

- prajilpatil17 August 13, 2017 | Flag Reply
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.

- andreaowu January 01, 2018 | Flag Reply
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 ) );

- marghi January 21, 2018 | Flag Reply
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

- Nitesh May 29, 2018 | Flag Reply
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.

- Aravind Prasad October 28, 2018 | Flag Reply
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.

- Aravind Prasad October 28, 2018 | Flag Reply
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

- Anonymous January 30, 2019 | Flag Reply
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)) {
                    currIntersection.add(num);
                }
            }
            intersection = currIntersection;
        }
        
        return new ArrayList<>(intersection);
    }

- Nitin May 02, 2019 | Flag Reply
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)) {
                    currIntersection.add(num);
                }
            }
            intersection = currIntersection;
        }
        
        return new ArrayList<>(intersection);

}

- Nitin May 02, 2019 | Flag Reply
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++){
         set1.add(userA[i]);
      }

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

      set1.clear();

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

      System.out.println(set1);




      int arrayCount = 3;

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

      }


   }

}

- Aakash Khatri May 11, 2019 | 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