 Introduction
 Problem 1: Flight
 Comparators & Lambdas
 Your Task
 Problem 2: RabinKarp Algorithm (Extra)
 Your Task
 Submission
Introduction
In this lab, you’ll be working with heaps and hashing. You will only need to complete the first problem to get credit, but we added the second question to give you some practice with using APIs and help you see practical applications of hashing!
Problem 1: Flight
Imagine that we have a list of every commercial airline flight that has ever been taken, stored as an ArrayList
Each flight’s start time and end time represents the number of minutes that have elapsed in the Pacific Time Zone since midnight on January 1st, 1914, which was the first day of commercial air travel.
For example, a flight taking off at 2:02 PM on March 6th, 1917 and landing at 3:03 PM the same day carrying 30 passengers would have takeoff time 1,671,243, landing time 1,671,304, and number of passengers 30.
Implement an algorithm for finding the largest number of people that have ever been in flight at once.
Your algorithm must run in \(\theta(N\log N)\) time, where \(N\) is the number of total commercial flights ever taken. Your algorithm must not have a runtime that is explicitly dependent on the number of minutes since January 1st, 1914, i.e. you can’t just consider each minute since that day and count the number of passengers from each minute and return the max.
Your algorithm may use any data structure that we’ve covered thus far, though we recommend doing it with a java.util.PriorityQueue
.
Comparators & Lambdas
You may need to use comparators in your solution for comparing objects. You can construct a concrete class (which can be somewhat verbose) or use lambda functions instead. The syntax for declaring a lambda for a comparator is:
Comparator<Type> function = (Type arg1, Type arg2) > (...);
Comparator<Type> functionEquivalent = (arg1, arg2) > (...);
where (…)
is your desired return value that can use arguments arg1
and arg2
.
Examples:
Comparator<Integer> intComparator = (i, j) > i  j;
Comparator<Integer> intComparatorEquivalent = (i, j) > {
int diff = i  j;
return diff;
};
You may also want to look into the function Integer.compare
. Note: lambdas will not be in scope for this course (i.e. not tested).
Your Task
Write the class FlightSolver
that has the following methods:
FlightSolver(ArrayList<Flight> …)
: Constructor that takes in an ArrayList of Flight objects as described above.public int solve()
: Returns the solution to the problem described above.
Problem 2: RabinKarp Algorithm (Extra)
The RabinKarp algorithm is a stringsearching algorithm that “uses hashing to find any one of a set of pattern strings in a text”. One practical application is detecting plagiarism. The algorithm takes \(\theta(n+m)\) time, for text of length \(n\) and a pattern string of length \(m\).
Your Task

Use the provided RollingString methods to implement the RabinKarp algorithm in the RabinKarpAlgorithm class. Check out the Wikipedia article for more information (i.e. psuedocode). Note that the staff implementation is casesensitive.
 Some Tips
 Make sure to actually use the provided methods.
 Be careful about the indices!
 If the user inputs are invalid (i.e. the pattern length to match is longer than the string itself), return 1.
 Your solution won’t work before you implement the RollingString class.
 Then, finish implement the RollingString class according to the descriptions above each method. Make sure to implement all the necessary functions. Do not change the
UNIQUECHARS
andPRIMEBASE
attributes, and make sure to use them in your solution. Convertchar
s to integers by casting them toint
s. Let \(c_i\) denote the \(i\)th character from the right (0indexed) and \(n\) be the length of the string. The hashcode should be: \(h = (\sum_{i=0}^{n1} c_i * \text{UNIQUECHARS}^i) \mod \text{PRIMEBASE}\).
 It is up to you to figure out how to compute the hashcode in constant time as we add characters to the String.
 Some Tips
Submission
Submit your solution to part 1 (and optionally part 2) to Gradescope.