15-111/200 Mastery Exam: Removing Lots of Trees

Logistics

You have 40 minutes to complete this exam. All exams must be completely submitted by the end of this 50 minute period.

Exam Overview

A farm and retail outlet is using a LinkedList-based TreeInventory to keep track of their Trees.

They have several lots of Trees. The inventory of each is kept in a different datafile. You do not need to know the format of this file, because it is parsed and read for you. But, because it might be helpful for debugging, we have included a description below in the Datafiles section of this document.

The owner of the tree farm and retail outlet keeps a sorted list of Trees by height for each lot, from the smallest to the largest. This helps him to locate trees that are the right size for his customers.

He wants to cull some trees from one of his lots and has chosen to remove those that can be found on another lot. The trees in each lot have heights that are unique (i.e., there are no duplicate elements in any list).

Fortunately, the TreeInventory program does exactly this. It reads the two specified sorted datafiles, one for each lot, and produces a list of the Trees sorted from the shortest to the tallest. Instructions for its use are provided in the running the program section below.

This feature of the TreeInventory program relies on the following unimplemented method of the LinkedList class:

void removeItems(LinkedList otherList)

It is your job to implement this method. This is the only method you are required to implement. Its behavior is described in the removeItems(LinkedList otherList) section below. You may implement private helper methods within the LinkedList class, if you choose.

You may not otherwise alter any of the files you have been provided.

removeItems(LinkedList otherList)

This method of the LinkedList class is unimplemented. You should implement it.

It should remove the Nodes in the LinkedList that have data items matching the ones in otherList using the compareTo() method of its data items. When finished, the remaining items in the original list must remain in order sorted from smallest value to largest. Also, the items in otherList must be unchanged. We have already implemented compareTo() for you. It will properly compare two Trees based on their heightInInches.

No list contains any duplicate items.

Running The Program

To run the program, execute the TreeInventory class, providing the two datafiles as parameters, including the path, if necessary.

For example 

  java TreeInventory ../datafiles/lot3.dat ../datafiles/lot2.dat

will use your removeItems(LinkedList otherList) method to produce a listing of all Trees contained in "lot3.dat" that are not in "lot2.dat", in sorted order by their heightInInches.

The Datafiles

Sample datafiles are contained within the "datafiles" subdirectory. Each data file contains one line per Tree. Each Tree is described by its heightInFeet, its priceInDollarsAndCents, and its qualityFrom1Through10.

So, each line of the datafile contains three numbers, as shown below: 

  heightInFeet priceInDollarsAndCents qualityFrom1Through10

  • heightInFeet is an int
  • priceInDollarsAndCents is a double
  • qualityFrom1Through10 is an int

For example, the datafile, "lot3.dat" reads as follows: 

  20 5000.00 8
  6 75.00 10
  3 10.00 1

You might be surprised that the datafile is sorted in the opposite order -- from tallest to shortest. Please don't worry about this, when the LinkedList is created, the order is reversed.

Download This: Everythng You Need

Exam.zip contains everything you need: