3. What methods of Map can be implemented in O(1) time with a good hash function and a properly-sized hash table? Consider Map methods size, isEmpty, containsKey,get,put,remove,clear,keySet, and values.What methods of Set? Use the methods listed in the Collection API slide.

4. (a) Find a method of ArrayList that is not in the List interface, specifically a method that trims the internal array down to fit exactly. A Google search for this did work, but the JDK API of course is the definitive source. For the homework answer, give the method header for the method.

(b) Add a call to this method to TestArrayList.java (which is available online), and see that it compiles and runs fine. Now change the line creating the ArrayList to use type Listfor its variable(Listarray = ...), and add the needed import for List. What happens when you try to compile this new version? For the homework answer, give the output.

(c) Explain why the compilation failed in this case. Note that this method is hardly ever used, and shows an example of a technical method related to the implementation that is excluded from the more abstract interface.

(d) Now remove the extra method, and see that the program compiles and runs with a variable of List type, object of type ArrayList (which ISA List), given that the methods in use in the program a reall in the List interface. For the homework answer, just put Done.

(e) Finally, change the ArrayList to LinkedList, and see it work again. Explain why we are confident that this switch from ArrayList to LinkedList will work, given that the methods in use in the program are all in the List interface.5. Given below are descriptions of some computer programs. Each of them reads a text file from standard input. For each of them, specify:Which APIs would you use. Choose from APIs discussed in class: List/Map/SetWhich implementations of the APIs would you use, e.g. LinkedList / HashSet / Tree ...Describe how you would use the API to implement the program. Give pseudo code or describe step by step how your program would work. No need to write an actual program.Give the time complexity of your program in terms of the number of words or lines read (which ever is appropriate). Try to make your programs as simple and efficient as possible. What the programs should do:

(a) Print lines of the file in reverse order.

(b) Print all different words in the file, each word printed exactly once (order not important).

(c) Print all different words in the file, with each word print how many times it occurs in the file(order not important).