Description
This assignment is about using the Java Collections Framework to accomplish some basic text-processing
tasks. These questions involve choosing the right abstraction (Collection, Set, List, Queue, Deque,
SortedSet, Map, or SortedMap) to efficiently accomplish the task at hand.
The best way to do these is to
read the question and then think about what type of Collection is best to use to solve it. There are only a
few lines of code you need to write to solve each of them.
The file Part0.java in the zip file actually does something. You can use its doIt() method as a
starting point for your solutions. Compile it. Run it. Test out the various ways of inputting and outputting
data. You should not need to modify Part0.java, it is a template.
You can download some sample input and output files for each question as a zip file (a1-io.zip). If
you find that a particular question is unclear, you can probably clarify it by looking at the sample files for
that question.
Once you get a sense for how to test your code with these input files, write your own
tests that test your program more thoroughly (the provided tests are not exhaustive!)
Unless specified otherwise, “sorted order” refers to the natural sorted order on Strings, as defined by
String.compareTo(s).
Caution: It is always better to use c.isEmpty() than c.size()==0 to check if a collection is
empty. In some cases (and one that you may encounter in this assignment) c.size() is slow but
c.isEmpty() is always fast.
1. [10 marks] Read the input one line at a time until you have read all lines. Now output these lines
in the opposite order from which they were read, but with consecutive duplicates removed.
2. [10 marks] Read the input one line at a time and output the current line if and only if it is strictly
larger than all other lines read so far or strictly smaller than the previously outputted line. If this
is the first nonempty line you read, it is considered larger than anything you’ve read so far.
(Here, larger is with respect to the usual order on Strings, as defined by String.compareTo()).
3. [10 marks] Read the input one line at a time. If you read less than 1000 lines, then do not output
anything. If you read less than 2402 lines, then output the 1000th line in sorted order of the
input lines. If you read 2402 or more lines, then consider only the last 2402 lines, and output the
1000th line in sorted order from the last 2402 lines. For full marks, your code should be fast and
should never store more than 2403 lines.
4. [10 marks] Read the input one line at a time and output the current line ℓ if and only if none of
the previous lines starts with ℓ.
5. [10 marks] Read the input one line at a time until you have read all lines. Output all the lines in
sorted order (as defined by String.compareTo(s)).
6. [10 marks] For this question, you may assume that every input line is distinct. Read the entire
input one line at time. If the input has less than 901 lines, then do not output anything.
Otherwise, output the line ℓ that has exactly 900 lines greater than ℓ. (Again, greater than and
less than are with respect to the ordering defined by String.compareTo()). For full marks, you
should do this without ever storing more than 901 lines.
7. [10 marks] The input contains special lines: “***reset***”. Read the entire input and break it
into blocks of consecutive lines 𝐵1, … , 𝐵𝑘, where 𝐵1 is a block that contains one line, 𝐵2 – two
lines, 𝐵3 – three lines, … 𝐵𝑘 contains 𝑘 lines (or less). When you read the “reset” line, you add it
to the current block and reset the size of the next block to 1.
So that following strings are
broken into blocks of size 1, 2, 3, … lines, until you read another “reset” string and reset the size
again. And so on. When you are done reading all the strings, output the blocks in reverse order
𝐵𝑘,𝐵𝑘−1, … , 𝐵3, 𝐵2,𝐵1 but preserving the order of the lines within each block.
8. [10 marks] Assume your input consists of 𝑛 lines. Read the input one line at a time until you
have read all lines. Treat the lines as if they are numbered 0, … , 𝑛 − 1. Note, there can be
duplicates. Output a permutation 𝜋0, 𝜋1, … , 𝜋𝑛−1 of {0, … , 𝑛 − 1} so that 𝜋0 is the number of
the smallest line, 𝜋1 is the number of the second smallest line, … , and 𝜋𝑛−1 is the number of
the largest line. (Again, smaller, and larger refer to the natural ordering on strings).
Your output
should consist of 𝑛 lines, where line 𝑖 contains (the string representation of) 𝜋𝑖
, for each 𝑖 ∈
{0, … , 𝑛 − 1}. The numbers for duplicates should be outputted in the same order in which the
lines were read.
9. [10 marks] Read the input one line at a time and output the current line if and only it has
appeared at least 3 times before.
10. [10 marks] For this problem you may assume that every input line is distinct. Read the input one
line at a time and assume that the lines are numbered 0, … , 𝑛 − 1. Your output should begin
with the largest line in the input. Assume its number is 𝑖. Next, output the largest line among the
lines numbered 𝑖 + 1, … , 𝑛 − 1. Assume its number is 𝑗, where 𝑗 > 𝑖. Next, output the largest
line among the lines numbered 𝑗 + 1, … , 𝑛 − 1. And so on.
The last line of your output will be
the last line of the input. (Here, largest is with respect to the usual order on Strings, as defined
by String.compareTo()). (Hint: Do not store all the lines. This problem can be solved very
efficiently with an ArrayList. Think about your solution before you start coding.)
Tips, Tricks, and FAQs
How should I approach each problem?
• Make sure you understand it. Construct small examples, and compute (by hand) the expected
output. If you aren’t sure what the output should be, go no further until you get clarification.
• Now that you understand what you are supposed to output, and you’ve been able to solve it by
hand, think about how you solved it and whether you could explain it to someone. How about
explaining it to a computer?
• If it still seems challenging, what about a simpler case? Can you solve a similar or simplified
problem? Maybe a special case? If you were allowed to make certain assumptions, could you do
it then? Try constructing your code incrementally, solving the smaller or simpler problems, then,
only expanding scope once you’re sure your simplified problems are solved.
How should I test my code?
• You should be testing your code as you go along.
• Use small tests first so that you can compute the correct solution by hand.
• For testing, replace big numbers (like 1000 or 2402 lines in Part 3) with small (3 or 5). Don’t
forget to change them back before submitting to the server.
• Think about edge cases, e.g. empty lists, lists of different lengths, duplicates, etc.
• Think about large inputs, random inputs.
• Test for speed.
