Booking.com Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
class HotelAvailabilityCalculator
attr_accessor :hotels_file_name, :bookings_file_name, :hotel_availability_hash
def initialize(hotels_file_name, bookings_file_name)
self.hotels_file_name = hotels_file_name
self.bookings_file_name = bookings_file_name
build_availability_hash
end
def build_availability_hash
self.hotel_availability_hash = {}
CSV.foreach(hotels_file_name, "rb") do |row|
hotel_availability_hash[row[0]] = Hash.new(row[1].to_i)
end
CSV.foreach(bookings_file_name, "rb") do |row|
(row[1].to_date...row[2].to_date).each do |stay_date|
hotel_availability_hash[row[0]][stay_date] -= 1
end
end
puts hotel_availability_hash.inspect
end
def available_hotels(checkin_date, checkout_date)
available_hotels_list = []
hotel_availability_hash.each do |hotel_name, availability_hash|
available_hotels_list << hotel_name if hotel_available?(hotel_name, checkin_date, checkout_date)
end
available_hotels_list
end
def hotel_available?(hotel_name, checkin_date, checkout_date)
(checkin_date...checkout_date).each do |stay_date|
return false unless hotel_availability_hash[hotel_name][stay_date] > 0
end
true
end
end
hac = HotelAvailabilityCalculator.new('hotels.csv', 'bookings.csv')
hac.available_hotels("2015-04-02".to_date, "2015-04-05".to_date)
I got a solution - in java
make two hashmaps
Map<String,Integer> hotels = new HashMap();
//read data from hotels.csv and save in this hashmap.
Map<String,Map<Date,Integer>> bookings = new HashMap();
// in this hash map read data from bookings.csv and fill data if inner hashmap don't exist for a date read data from hotels hashmap and fill in bookings hashmap, during search if bookings hashmap has that date data then print it else all rooms are available read from hotels hash map and show.
/**
* Complexity: O(n^2) where n reservations and n hotel
* @author Omid Ghiasi Tarzi
*/
static Set<String> getAvailableHotels(
Map<String, Integer> hotelSizes,
List<String> reservations,
String fromDate,
String toDate
) {
Set<String> result = new HashSet<>();
Map<String, List<String>> map = reservations.stream().collect(Collectors.groupingBy(check -> check.split(" ")[0]));
for (String hotel : map.keySet()) {
List<String> list = map.get(hotel);
if (isHotelAvailable(list, hotelSizes.get(hotel), fromDate, toDate)) {
result.add(hotel);
}
}
return result;
}
static boolean isHotelAvailable(List<String> reservations, int size, String fromDate, String toDate) {
List<String> ins = new ArrayList<>();
List<String> outs = new ArrayList<>();
for (String reservation : reservations) {
ins.add(reservation.split(" ")[1]);
outs.add(reservation.split(" ")[2]);
}
int space = size;
int i = 0;
int j = 0;
while (i < ins.size()) {
if (ins.get(i).compareTo(outs.get(j)) < 0) {
space--;
if (space <= 0 && ins.get(i).compareTo(toDate) <= 0 && ins.get(i).compareTo(fromDate) >= 0) {
return false;
}
i++;
} else {
space++;
j++;
}
}
return true;
}
// group reservations by hotel name
// sort reservations by start + end
// if one of reservations start > available.end then filter it
// if one of reservations end < available.start then filter it
// loop in hotels.reservations
// for the first record, reduce 1 of the available room for current hotel // do while's first iteration
// if iterating reservation has next
// iterating.start < prev.end
// reduce 1 of the available room for current hotel
// show hotels which has available room size > 0
{{
void test() {
Hotel hilton = new Hotel("Hilton", 3);
Hotel stRegis = new Hotel("Saint Regis", 1);
Hotel fourSeasons = new Hotel("Four Seasons", 4);
List<Reservation> bookedReservations = new ArrayList<>(List.of(
new Reservation(hilton, setDate("2020-01-04"), setDate("2020-12-31")), // filtered
new Reservation(hilton, setDate("2021-01-04"), setDate("2021-01-13")), // uses room 101
new Reservation(hilton, setDate("2021-02-01"), setDate("2021-02-03")), // filtered
new Reservation(hilton, setDate("2021-01-02"), setDate("2021-01-03")), // uses room 101
new Reservation(hilton, setDate("2021-01-01"), setDate("2021-01-10")), // uses room 102
new Reservation(hilton, setDate("2021-01-01"), setDate("2021-01-10")), // uses room 103
new Reservation(stRegis, setDate("2021-01-01"), setDate("2021-01-03")),
new Reservation(fourSeasons, setDate("2021-01-01"), setDate("2021-01-03"))
));
bookedReservations = bookedReservations.stream()
.sorted(Comparator.comparing(Reservation::getCheckIn)
.thenComparing(Reservation::getCheckOut))
.collect(Collectors.toList());
List<Hotel> availableHotels = checkAvailability(bookedReservations, setDate("2021-01-01"), setDate("2021-01-10"));
assertEquals(1, availableHotels.size());
}
private List<Hotel> checkAvailability(List<Reservation> reservations, LocalDate checkIn, LocalDate checkOut) {
Map<Hotel, List<Reservation>> hotelReservationMap = reservations.stream()
.collect(Collectors.groupingBy(Reservation::getHotel));
for (Map.Entry<Hotel, List<Reservation>> hotelReservations : hotelReservationMap.entrySet()) {
List<Reservation> filteredReservations = hotelReservations.getValue().stream()
.filter(reservation -> !(reservation.getCheckIn().isAfter(checkOut) || reservation.getCheckOut().isBefore(checkIn)))
.collect(Collectors.toList());
for (int i = 0; i < filteredReservations.size(); i++) {
Integer availableRooms = hotelReservations.getKey().getAvailableRooms();
if (i == 0) {
hotelReservations.getKey().setAvailableRooms(availableRooms - 1);
} else {
boolean useOneMoreRoom = filteredReservations.get(i).getCheckIn().isBefore(filteredReservations.get(i - 1).getCheckOut());
if (useOneMoreRoom) {
hotelReservations.getKey().setAvailableRooms(availableRooms - 1);
}
}
}
}
return hotelReservationMap.keySet().stream().filter(hotel -> hotel.availableRooms > 0).collect(Collectors.toList());
}
}}
{{
public class HotelAvailibility {
public static void main(String args[]) {
Map<String, Integer> hotelAvailibility = new HashMap<>();
hotelAvailibility.put("Hilton", 2);
hotelAvailibility.put("Ramada", 1);
List<Reservation> reservations = new ArrayList<>();
reservations.add(new Reservation("Hilton", 1, 2));
reservations.add(new Reservation("Hilton", 3, 6));
reservations.add(new Reservation("Ramada", 8, 10));
solve(hotelAvailibility, reservations, 1, 9);
}
private static void solve(Map<String, Integer> hotelAvailibility, List<Reservation> reservations, int checkIn, int checkOut) {
for (Reservation reservation : reservations) {
if (checkIn < reservation.checkout && checkOut > reservation.checkin) {
hotelAvailibility.compute(reservation.hotel, (k, v) -> v - 1);
}
}
List<String> list = hotelAvailibility.entrySet().stream().filter((v) -> v.getValue() > 0).map(Map.Entry::getKey).toList();
System.out.println(list);
}
record Reservation(String hotel, int checkin, int checkout) {
}
}
}}
{{
public class HotelAvailibility {
public static void main(String args[]) {
Map<String, Integer> hotelAvailibility = new HashMap<>();
hotelAvailibility.put("Hilton", 2);
hotelAvailibility.put("Ramada", 1);
List<Reservation> reservations = new ArrayList<>();
reservations.add(new Reservation("Hilton", 1, 2));
reservations.add(new Reservation("Hilton", 3, 6));
reservations.add(new Reservation("Ramada", 8, 10));
solve(hotelAvailibility, reservations, 1, 9);
}
private static void solve(Map<String, Integer> hotelAvailibility, List<Reservation> reservations, int checkIn, int checkOut) {
for (Reservation reservation : reservations) {
if (checkIn < reservation.checkout && checkOut > reservation.checkin) {
hotelAvailibility.compute(reservation.hotel, (k, v) -> v - 1);
}
}
List<String> list = hotelAvailibility.entrySet().stream().filter((v) -> v.getValue() > 0).map(Map.Entry::getKey).toList();
System.out.println(list);
}
record Reservation(String hotel, int checkin, int checkout) {
}
}
}}
- w.kinaan September 03, 2017