Booking.com Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
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
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());
}
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);
}
}
{
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)}
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)
}
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
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;
});
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);
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);
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);
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);
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
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;
}
}
}
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);
}
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 ) );
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
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.
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.
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);
}
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);
}
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++){
}
}
}
/**
* 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<>();
result.addAll(sets.iterator().next());
for (Set<Integer> set : sets) {
result.retainAll(set);
}
return result;
}
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]:
d[hotel_id].add(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])
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) {
set.add(visitedHotelId);
}
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);
}
}
}
}
List<Integer> getCommonId(List<List<Integer>> userVisits) {
Map<Integer, Integer> map = new HashMap<>();
List<Integer> commonId = new ArrayList<>();
for (List<Integer> visits : userVisits) {
Set<Integer> set = new HashSet<>();
for (int hotelId : visits) {
if(!set.contains(hotelId)) {
map.put(hotelId, map.getOrDefault(hotelId, 0) + 1);
}
set.add(hotelId);
}
}
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue() == userVisits.size()) {
commonId.add(entry.getKey());
}
}
return commonId;
}
List<Integer> getCommonId(List<List<Integer>> userVisits) {
Map<Integer, Integer> map = new HashMap<>();
List<Integer> commonId = new ArrayList<>();
for (List<Integer> visits : userVisits) {
Set<Integer> set = new HashSet<>();
for (int hotelId : visits) {
if(!set.contains(hotelId)) {
map.put(hotelId, map.getOrDefault(hotelId, 0) + 1);
}
set.add(hotelId);
}
}
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue() == userVisits.size()) {
commonId.add(entry.getKey());
}
}
return commonId;
}
import java.util.*;
import java.util.stream.Collectors;
public class CommonHotelID {
public static List<Integer> findCommonHotelIds(int[][] users) {
Map<Integer, Integer> hotelUsersCount = new HashMap<>();
for (int[] user : users) {
Arrays.stream(user).distinct().forEach(
hotel -> {
hotelUsersCount.put(hotel, hotelUsersCount.getOrDefault(hotel, 0) + 1);
});
}
return hotelUsersCount.entrySet().stream()
.filter(entry -> entry.getValue() == users.length)
.map(entry -> entry.getKey())
.collect(Collectors.toList());
}
public static void main(String[] args) {
int[][] users = {
{4, 6, 8, 1, 1, 4, 5},
{4, 5, 9, 12, 11},
{4, 5, 5, 9, 10},
{5, 4, 4, 12, 8, 6}
};
System.out.println(findCommonHotelIds(users));
}
}
You want to find set intersection. Here is how we do it in ZoomBA.
- NoOne April 26, 2017