You have been given the following code:
HW2.java
Input files: imdb.txt / sight_and_sound.txt / 3_lists.txt
Sample output: output_intersection.txt / output_frequent.txt / output_groupByNumChars.txt
Three of the methods in HW2.java are incomplete. Write the code so it works correctly. You should submit one file, HW2.java.
Do not change the method headers. Each method should print the output to the console. They should not return anything.
The purpose of this assignment is to learn how to use the JCF classes (HashSet, HashMap, TreeSet, TreeMap). You do not need to implement these classes.
public static List< String > getList(String filename)
This method has been done for you. It takes a filename as a parameter and returns a List of movies.
Each file contains one movie per line. 3_lists.txt has duplicates because it contains 3 lists (the other files do not have duplicates).
public static void intersection(List< String> list1, List< String> list2)
Print all movies that occur in both lists. The order is not important.
The expected runtime must be O(n) where n is the total number of movies in the lists. Do not sort the movies because it is too slow. Use a HashSet to store one of the lists, so you can search the HashSet efficiently.
You may assume that the expected runtime of searching or inserting into a hash table is O(1).
Do not call the list's contains method, because it is too slow.
public static void frequent(List< String> list, int k)
Print all movies in the list that occur at least k times. The order is not important. Print the movie followed by the number of occurrences in parentheses, as in the sample output.
The expected runtime must be O(n) where n is the total number of movies in the list. Do not sort the movies. Use a HashMap to count occurrences (the key is the movie, the value is the number of occurrences).
For each movie, check if it's a key in the map. If it is, update its value. Otherwise add a new entry to the map.
Then iterate through the map and print the frequent movies. See UsingSetsMaps for an example of how use a for-each loop with a map.
public static void groupByNumChars(List< String> list)
Print all movies in the list, grouped by number of characters.
All movies with the same number of characters should be printed on the same line, and movies with fewer characters should be printed first.
The runtime must be O(nlogn) where n is the number of movies in the list.
There is more than one way to solve this problem, but one way is to use a map. The key is the number of characters, and the value is a list of movies with that number of characters. You can declare it like this:
Map< Integer, List< String> > map = new ... // Choose the appropriate map class
For each movie, you can use the String class's length function to get the number of characters.
If the map doesn't already have an entry for this length, create a new entry (use the map's put method).
If the map already has an entry for this length, first call the map's get method (which returns a reference to a list), then add the movie to the list.
Do not use a single String to store more than one movie, because it will slow down the runtime (but a StringBuilder is ok).
import java.io.*;
import java.util.*;
public class HW2 {
// Prints all movies that occur in both lists.
public static void intersection(List< String> list1, List< String> list2) {
}
// Prints all movies in the list that occur at least k times
// (print the movie followed by the number of occurrences in parentheses).
public static void frequent(List< String> list, int k) {
}
// Prints all movies in the list, grouped by number of characters.
// All movies with the same number of characters are printed on the same line.
// Movies with fewer characters are listed first.
public static void groupByNumChars(List< String> list) {
}
// Returns a List of all movies in the specified file (assume there is one movie per line).
public static List< String> getList(String filename) {
}
public static void main(String[] args) {
List< String> list1 = getList("imdb.txt");
List< String> list2 = getList("sight_and_sound.txt");
List< String> list3 = getList("3_lists.txt");
System.out.println("***intersection***");
intersection(list1, list2);
System.out.println("***frequent***");
frequent(list3, 3);
System.out.println("***groupByNumChars***");
groupByNumChars(list1);
}
}