Find The Best Hotel Deal

Problem Statement - Find the Best Hotel Deal

Imagine you’re given a data file containing hotel deals, aggregated from participating hotels. Write an app that will find the best deal given a hotel name, check-in date, and duration of stay. Print the promo_txt value for the best deal, or “no deals available” if none exists. Consider the type and value of the deals, as well as whether they apply. Your solution will be evaluated based on correctness, performance, code design, and maintainability.

Design

• Hotel Object : Created a Hotel Object that stores all the information pertaining the information of each hotel. A different Hotel instance is created for the same hotel with a different deal. Hence, the Hotel object is deal-focused.
• HotelDB : HotelDB holds the information extracted from the input file (./deals.csv). Storing the information from the input file in a HashMap with the (key, value) pair being (String hotel_name, ArrayList of Hotel objects with different deals). Thus, each hotel is mapped with all of its different deals.
• Search for Miminal Cost: Our goal was to find the deal that was valid and would give us the minimize the cost of stay for the customer. The stay range can be within or beyond the deal range. However, the deal is applied for only the applicable days (printed with the promo text). Using the arguments provided by the user, the program looks for the Hotel Objects in the HashMap. Once it gets the ArrayList of all the objects, it iterates through them, and checks if the stay range is within and deal range. If the deal is valid for the whole or part of the stay, then the effective value is calculated and compared to the minimal cost value held from previous calculations.
• NOTE: Since only one search is made for every time the input file is processed, this problem can be solved by simply iterating through input file and looking for the minimal cost deal. It would give the fastest solution in this case (O(N) time). However, this would not be good design, since it would not be reusable. If the input calls were changed to process the input file once, and then make several queries, the design that I have proposed would save a tremenduous amount of computer time.

Efficiency / Run-Time Complexity

Time

• Data Storage : O(N), where N is the number of items in the input file.
• Hotel Search : O(1)
• Minimal Deal : O(n), where n is the number of deals with same hotel name being searched.
• TOTAL RUN TIME : O(N) + O(n)
• Optimization : If for one occurence of data storage, multiple searches are made, store the deals associated with one hotel name in an Interval Tree instead of a list.
• Interval Tree :
  • Creation : O(n log(n))
  • Deletion : O(log(n))
  • Search : O(log(n) + m)

Space

• Since we are storing the entire input file, our space complexity will be O(N), where N is the number of items in the input file.

Usage

• Makefile: Run the Makefile using the 'make' command on the commandline.
• Usage: java BestHotelDeal [input_path] [hotel_name] [check-in_date] [stay_duration]