Review Exercise, Part 1

The goal of this lab is to apply some of the techniques and structures we've studied this semester to solve several design challenges. Read the problem descriptions, determine appropriate collection types, and implement efficient solutions. Work in groups.

Do not implement your own data structures. Instead, use existing implementations from the Java standard library. These include the following:

You might also find useful PriorityQueue, which doesn't fit the pattern of this table.

Duplicate Tracker

Create a new package review and paste in DuplicateTracker.java and DuplicateTrackerTest.java.

Complete the methods of the DuplicateTracker class so that all operations are as efficient as possible. The purpose of this class is to process a sequence of user IDs such that duplicate IDs are identified and efficiently retrieved as a sorted List. You should assume that both the addId and the getDuplicates methods may be called arbitrarily many times and in any order. In other words, efficiency matters for both.

Here is a code snippet that illustrates the desired behavior:

tracker.addId(5);
tracker.addId(2);
tracker.addId(1);
tracker.addId(2);
tracker.addId(5);
tracker.addId(5);
System.out.println(tracker.getDuplicates()); // Prints "[2, 5]"

tracker.addId(1);
System.out.println(tracker.getDuplicates()); // Prints "[1, 2, 5]"

Test your implementation by executing the JUnit tests. These will test correctness and timing. Your goal is to pass all correctness tests with an overall execution time that is as small as possible.

Job Sequencer

Paste in JobSequencer.java and JobSequencerTest.java.

Complete the methods of JobSequencer so that all operations are as efficient as possible. The purpose of this class is to process jobs of different types in the order that they are added to the system. Because there are a limited number of job handlers and they are specialized for a particular job type, you must make sure that the nextJob method only returns jobs of the requested type. You must also ensure that jobs of a particular type are processed in the order in which they arrived. You should assume that both addJob and nextJob may be called arbitrarily many times and in any order: efficiency matters for both.

Here is a code snippet that illustrates the desired behavior:

JobSequencer sequencer = new JobSequencer();

sequencer.addJob("A", 101);
sequencer.addJob("B", 105);
sequencer.addJob("A", 93);
sequencer.addJob("B", 202);

System.out.println(sequencer.nextJob("A")); // Prints "101"
System.out.println(sequencer.nextJob("B")); // Prints "105"
System.out.println(sequencer.nextJob("B")); // Prints "202"
System.out.println(sequencer.nextJob("A")); // Prints "93"