2
\$\begingroup\$

Got a mission to implement an Hotel Manager interface. I will post the interface and the attached class Reservation, and will add my code. What I am asking you is basically tell me if my choice of using a TreeMap seems right for you or you could improved the run time of this.

The class Reservation:

package test;

import java.time.LocalDate;

public class Reservation {

    private final int id;
    private final LocalDate fromDate;
    private final LocalDate toDate;
    private final int price;

    public Reservation(LocalDate fromDate, LocalDate toDate, int price) {
        this.id = generateRandomId();
        this.fromDate = fromDate;
        this.toDate = toDate;
        this.price = price;
    }

    public int getId() {
        return id;
    }

    public LocalDate getFromDate() {
        return fromDate;
    }

    public LocalDate getToDate() {
        return toDate;
    }

    public int getPrice() {
        return price;
    }

    private int generateRandomId() {
        return (int) (Math.random() * 10000000);
    }

    public String toString() {
        return "id: " + id + ", from: " + fromDate + ", to: " + toDate + ", price: " + price; 
    }
}

The interface:

package test;

import java.time.LocalDate;
import java.util.List;

public interface HotelManager {

    /**
     * Sets the number of rooms in the hotel.
     */
    void setNumberOfRooms(int numRooms);

    /**
     * Tries to add a reservation to the system.
     * Reservation will be added successfully only if during the whole time frame from its fromDate to its toDate there is
     * a free room in the hotel.
     * @param reservation reservation to add
     * @return true if added reservation successfully. False otherwise.
     */
    boolean makeReservation(Reservation reservation);

    /**
     * Cancels the reservation with the given id.
     * @param reservationId id of reservation to cancel
     */
    void cancelReservation(int reservationId);

    /**
     * Get the reservation with the given id.
     * @param reservationId id of reservation to fetch.
     * @return Reservation with the given id or null if no reservation with that id exists.
     */
    Reservation getReservation(int reservationId);

    /**
     * Return the number of available rooms on the given date.
     * @param dateToCheck date to check number of available rooms
     * @return number of available rooms on the given date.
     */
    int getNumberAvailableRooms(LocalDate dateToCheck);

    /**
     * Get the price of all reservations that start on or after the given from date AND end on or before the given to date
     * (if a reservation starts before the given from date or ends after the given to date don't count it)
     * @return the sum of prices of all reservations that start and end during the given timeframe
     */
    int getPriceOfReservations(LocalDate from, LocalDate to);

    /**
     * Gets all the reservations that start on or after the given from date AND end on or before the given to date
     * sorted by price in an ASCENDING order.
     */
    List<Reservation> getAllReservationsSortedByPrice(LocalDate from, LocalDate to);

    /**
     * Gets all the reservations that start on or after the given from date AND end on or before the given to date
     * sorted by date in an ASCENDING order.
     */
    List<Reservation> getAllReservationsSortedByDate(LocalDate from, LocalDate to);

}

And my implementation:

package test;

import java.time.LocalDate;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map.Entry;
import java.util.TreeMap;

public class Hotel implements HotelManager {

    private TreeMap<Integer, Reservation> reservations;
    private int numberOfRooms;

    public Hotel() {
        reservations = new TreeMap<Integer, Reservation>();
        numberOfRooms = 0;
    }

    public void setNumberOfRooms(int numRooms) {
        this.numberOfRooms = numRooms;
    }

    public boolean makeReservation(Reservation reservation) {

        int numOfNonAvailableRooms = 0;

        for (Entry<Integer, Reservation> entry : reservations.entrySet()) {
            if (reservationsAreOverlapping(reservation, entry.getValue())) {
                numOfNonAvailableRooms++;
            }
        }

        if (numOfNonAvailableRooms == this.numberOfRooms) {
            return false;
        } else {
            reservations.put(reservation.getId(), reservation);
            return true;
        }
    }

    public void cancelReservation(int reservationId) {
        reservations.remove(reservationId);

    }

    public Reservation getReservation(int reservationId) {
        return reservations.get(reservationId);
    }

    public int getNumberAvailableRooms(LocalDate dateToCheck) {

        int numberOfNonAvailableRooms = 0;
        for (Entry<Integer, Reservation> entry : reservations.entrySet()) {
            Reservation existingReservation = entry.getValue();
            if (existingReservation.getFromDate().isBefore(dateToCheck)
                    && existingReservation.getToDate().isAfter(dateToCheck)) {
                numberOfNonAvailableRooms++;
            }

        }
        return this.numberOfRooms - numberOfNonAvailableRooms;
    }

    public int getPriceOfReservations(LocalDate from, LocalDate to) {

        int sumOfPrices = 0;

        for (Entry<Integer, Reservation> entry : reservations.entrySet()) {
            Reservation existingReservation = entry.getValue();
            // if the following conditions are met, the reservation date is between from
            // LocalDate and to LocalDate
            if (existingReservation.getFromDate().isEqual(from)
                    || existingReservation.getFromDate().isAfter(from) && existingReservation.getToDate().isEqual(to)
                    || existingReservation.getToDate().isBefore(to)) {
                sumOfPrices += existingReservation.getPrice();
            }
        }

        return sumOfPrices;
    }

    public List<Reservation> getAllReservationsSortedByPrice(LocalDate from, LocalDate to) {

        Comperators comperators = new Comperators();
        List<Reservation> reservationsSortedByPrice = new ArrayList<Reservation>();

        for (Entry<Integer, Reservation> entry : reservations.entrySet()) {

            Reservation existingReservation = entry.getValue();
            // if the following conditions are met, the reservation date is between from
            // LocalDate and to LocalDate
            if (existingReservation.getFromDate().isEqual(from)
                    || existingReservation.getFromDate().isAfter(from) && existingReservation.getToDate().isEqual(to)
                    || existingReservation.getToDate().isBefore(to)) {
                reservationsSortedByPrice.add(existingReservation);
            }
        }

        Collections.sort(reservationsSortedByPrice, comperators.getComperatorByPrice());
        return reservationsSortedByPrice;
    }

    public List<Reservation> getAllReservationsSortedByDate(LocalDate from, LocalDate to) {

        Comperators comperators = new Comperators();
        List<Reservation> reservationsSortedByDate = new ArrayList<Reservation>();

        for (Entry<Integer, Reservation> entry : reservations.entrySet()) {

            Reservation existingReservation = entry.getValue();
            // if the following conditions are met, the reservation date is between from
            // LocalDate and to LocalDate
            if (existingReservation.getFromDate().isEqual(from)
                    || existingReservation.getFromDate().isAfter(from) && existingReservation.getToDate().isEqual(to)
                    || existingReservation.getToDate().isBefore(to)) {
                reservationsSortedByDate.add(existingReservation);
            }
        }

        Collections.sort(reservationsSortedByDate, comperators.getComperatorByDate());
        return reservationsSortedByDate;
    }

    private boolean reservationsAreOverlapping(Reservation r1, Reservation r2) {
        return ((r1.getFromDate().isAfter(r2.getFromDate()) || r1.getFromDate().isEqual(r2.getFromDate()))
                && (r1.getFromDate().isBefore(r2.getToDate()) || r1.getFromDate().isEqual(r2.getToDate())))

                ||

                ((r2.getFromDate().isAfter(r1.getFromDate()) || r2.getFromDate().isEqual(r1.getFromDate()))
                        && (r2.getFromDate().isBefore(r1.getToDate()) || r2.getFromDate().isEqual(r1.getToDate())));

    }

}

The comperators class is basiclly a class with two comperators, just by price and by date.

Do you think this implementation is fine ? Would you use a different collection than a TreeSet in here?

\$\endgroup\$
  • \$\begingroup\$ In a similar vein: finding the cheapest hotel can be a fun challenge =) \$\endgroup\$ – Mathieu Guindon Sep 25 '17 at 20:50
  • \$\begingroup\$ For something this complicated, I think you would benefit from using an SQL database instead of in memory data structures. \$\endgroup\$ – tinstaafl Sep 26 '17 at 3:32
  • \$\begingroup\$ It's just an assignment I've got as part of an interview. I received the Hotel Manager interface and Reservation class and had to implement the interface. No real use in this. \$\endgroup\$ – NotSure Sep 26 '17 at 7:15
3
\$\begingroup\$

Benefits of a TreeMap

The TreeMap is not useful at all in this implementation.

Roughly speaking, these are the operations and their performance in which the TreeMap is involved:

  • Cancel reservation, get reservation: \$O(\log n)\$
  • Methods that sort reservations: \$O(n \log n)\$
  • Other methods (make reservation): \$O(n)\$, because they iterate over all reservations

How could it be better?

  • Cancel reservation, get reservation could be \$O(1)\$ using a HashMap
  • Make reservation should not have to check all reservations if they are sorted by start and end date, then you could use binary search to check at most \$\log n\$ entries
  • Further optimizations are possible if you know something about the usage patterns. For example, if the sorting methods are called more often than the other methods, then it could make sense to keep sorted lists, so that they can be returned immediately. This will be at the expense of using extra memory.

A logical problem

What if there are two rooms with the following reservations:

  • Room 1: January to March, and May to July
  • Room 2: not booked :-)

That is, there are two rooms, two reservations, but one of the rooms is unused. Now, if you call makeReservation to book from February to June, it will count 2 overlaps, equal to the number of rooms, and reject the reservation.

Assigning unique ids

Reservation instances should have unique ids, to prevent accidental overwriting of data in the HotelManager implementation. Generating random numbers even in a very wide range is not a solid solution, because even if the probability of collisions is small, they can happen, and when they will, data can be lost. Such program cannot be trusted.

A better solution would be to use an auto-incrementing id. This could be as simple as an AtomicInteger instance in a static field. But preferably not in the same class that already has the responsibility of storing some data, such as the Reservation class. It would be better to have a dedicated class, a factory, that is in charge of creating objects with appropriate unique ids.

Input validation

The constructor of Reservation doesn't validate its parameters. You could create a Reservation where the start date comes after the end date.

The factory I mentioned in the previous section could be a good place for this validation too. It could effectively prevent the creation of invalid Reservation instances.

Unnecessary object creation

I assume that the comparator classes inside Comperators don't have a state. Hopefully. And in that case you don't need to create a new instance every time you want to sort records. You could create static final comparator instances, they should be safe to reuse.

Duplicated code

The methods that sort reservations by price and date have most of their code duplicated. The common code should be in a private helper method.

\$\endgroup\$
  • \$\begingroup\$ Great answer, learned a lot from it. Thanks. At first I've used HashMap because the get and remove methods scream for it. But than in make reservation I knew I need to use some kind of ordering on a reservation so maybe HashMap is not the way to go here. I thought I will probably suffer in the time complexity of get and remove but can't ignore the fact that reservations needs some ordering, a thing that HashMap is not providing. \$\endgroup\$ – NotSure Sep 25 '17 at 20:19
  • \$\begingroup\$ Generating unique id is should not be the responsibility of the Reservation class, also it makes it difficult to test. \$\endgroup\$ – CodeYogi Sep 25 '17 at 20:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.