1. Data Structures and Algorithms

Data structures store essential information in the application. They are organized via lists, sets, queues, and associative maps. In Java, the interfaces and classes around data structures are called Collection-API. Since there are so many types to choose from, the purpose of this chapter is to bring order to the confusion and to illustrate the use of the corresponding collections through the exercises.

Prerequisites

  • be able to distinguish data structures lists, sets, associative memory.

  • know data types List, ArrayList and LinkedList.

  • know data types Set, HashSet and TreeSet.

  • know Map, HashMap and TreeMap data types.

  • know the difference between queue and deque.

  • know how to create an order with Comparator.

  • know how to use and implement iterators.

  • be able to use data structures in a thread-safe way.

  • optional: Interest in the open-source library Guava for further data structures.

Data types used in this chapter:

1.1. The types of the Collection API

The list of user types is long this time. However, the design follows a basic principle, so it is not so complicated after all:

  • Interfaces describe the functionality of a data structure, "what is provided".

  • Classes use different strategies to implement the specification from the interfaces; they represent the "how it is implemented".

As developers, we need to know interfaces and implementations, and to review, let’s look again at the central types we’ll encounter more often in this chapter:

Collection Classes UML
Figure 1. UML diagram of selected data structures and type relationships

To note:

  • Iterable is the most general interface, representing what can be traversed; Iterable provides Iterator instances. Not only data structures are Iterable.

  • Collection is the top interface that really represents data structures. It specifies methods for adding elements to the collection or for deleting them.

  • Under Collection are the actual abstractions, whether it is a list, set, or queue. Below are the implementations.

  • Some operations are not with the data types themselves, but are outsourced to a class Collections. Similar applies to arrays, where there is also a utility class Arrays.

We want to build a decision tree for the classes and interfaces java.util.Set, java.util.List, java.util.Map, java.util.HashSet, java.util.TreeSet, java.util.Hashtable, java.util.HashMap and java.util.TreeMap. The following considerations must be made in the selection process:

  • Access via key

  • duplicates allowed

  • fast access

  • sorted iteration

  • thread safe

If access is from a key to a value, this is generally an associative map, that is, an implementation of the Map interface. Implementations of Map are HashMap, TreeMap, and the outdated class Hashtable. However, lists are also special associative stores, where the index is an integer starting at 0 and ascending. Lists work quite well whenever the key is a small integer and there are few spaces. The association of arbitrary integers to objects does not work well with a list.

Duplicates are allowed in lists, but not in sets and associative stores. There are indeed requirements that a set should note how often an element occurs, but this must be implemented itself with an associative memory that associates the element with a counter.

All data structures allow fast access. The only question is what to ask for. A list cannot quickly answer whether an element is present or not because the list must be traversed from front to back to do so. With an associative store or set, this query is much faster because of the internal organization of the data. This test of existence can be answered even somewhat faster for data structures that use hashing internally than for data structures that keep elements sorted.

Lists can be sorted, and a traversal returns the elements in the sorted order. A TreeSet and a TreeMap are also sorted by criteria. The data structures with the hashing method have no user-defined order of sorting.

Data structures can be divided into three groups: Data structures since Java 1.0, data structures since Java 1.2, and data structures since Java 5. In the first Java versions the data structures Vector, Hashtable, Dictionary and Stack were introduced. These data structures are all thread-safe, but they are no longer used today. In Java 1.2 the Collection API was introduced, all data structures are not thread safe. In Java 5 the new package java.util.concurrent has been introduced, all data structures in it are safe against concurrent changes.

1.2. Lists

For the exercises, let’s start with the simplest data structure, lists. Lists are sequences of information where the order is maintained when appending new elements, and elements can occur multiple times. Even null is allowed as an element.

1.2.1. Singing and cooking: Traverse lists and check properties ⭐

Captain CiaoCiao is putting together a new crew. Everyone in the crew has a name and a profession:

record CrewMember( String name, Profession profession ) {
  enum Profession { CAPTAIN, NAVIGATOR, CARPENTER, COOK, MUSICIAN, DOCTOR }
}

For each crew, Captain CiaoCiao makes sure that there are as many cooks as musicians.

Exercise:

  • Write a method areSameNumberOfCooksAndMusicians(List<CrewMember>) that returns true if there are the same number of cooks as musicians, false otherwise.

Example:

CrewMember captain   = new CrewMember( "CiaoCiao", CrewMember.Profession.CAPTAIN );
CrewMember cook1     = new CrewMember( "Remy", CrewMember.Profession.COOK );
CrewMember cook2     = new CrewMember( "The Witch Cook", CrewMember.Profession.COOK );
CrewMember musician1 = new CrewMember( "Mahna Mahna", CrewMember.Profession.MUSICIAN );
CrewMember musician2 = new CrewMember( "Rowlf", CrewMember.Profession.MUSICIAN );

List<CrewMember> crew1 = List.of( cook1, musician1 );
System.out.println( areSameNumberOfCooksAndMusicians( crew1 ) ); // true

List<CrewMember> crew2 = List.of( cook1, musician1, musician2, captain );
System.out.println( areSameNumberOfCooksAndMusicians( crew2 ) ); // false

List<CrewMember> crew3 = List.of( cook1, musician1, musician2, captain, cook2  );
System.out.println( areSameNumberOfCooksAndMusicians( crew3 ) ); // true

Solution

1.2.2. Filter comments from lists ⭐

Bonny Brain reads an old logbook of Captain Dipturus Dimwit, which repeatedly contains four entries:

  1. Magnetic Compass Course [1].

  2. Speed of water current

  3. Weather

  4. Comments and general observations

The Bonny Brain is searching for a specific comment in a list of strings. To do so, they need to delete the first, second, and third entries so that only the fourth entry, which contains the desired comment, remains.

Exercise:

  • Implement a method void reduceToComments(List<String> lines) that deletes each of the first, second, and third entries in the passed list, keeping only the fourth.

Examples:

  • "A1", "A2", "A3", "A4", "B1", "B2", "B3", "B4", "C1", "C2", "C3", "C4" → "A4", "B4", "C4"

  • empty list → nothing happens

  • "A1" → exception Illegal size 1 of list, must be divisible by 4

Solution

1.2.3. Shorten lists because there is no downturn ⭐

For Captain CiaoCiao, things should only ever go up; when he reads sequences of numbers, they should only ever go up.

Shorten lists because there is no downturn

Exercise:

  • Write a method trimNonGrowingNumbers(List<Double> numbers) that truncates the list when the next number is no longer greater than or equal to the previous one.

  • Remember: the passed list must be mutable so that elements can be deleted.

Examples:

  • If the list contains the numbers 1, 2, 3, 4, 5, the list stays that way.

  • If the list contains the numbers 1, 2, 3, 2, 1, the sequence is shortened to 1, 2, 3.

Solution

1.2.4. Eating with friends: Compare elements, find commonalities ⭐

Captain CiaoCiao is planning a party on the mainland, and in a large circle, there should always be two guests sitting next to each other who have at least one thing in common. Guests are declared by the following type:

public record Guest(
    boolean likesToShoot,
    boolean likesToGamble,
    boolean likesBlackmail
) { }

Exercise:

  • Write a method int allGuestsHaveSimilarInterests(List<Guest> guests) that returns -1 if all guests have a neighbor that matches in at least one property. Otherwise, the result is >= 0, and the index on exactly the first guest that sits incorrectly, that is, has nothing in common with any of its neighbors.

  • Guest can be extended in any way

Solution

1.2.5. Check lists for same order of elements ⭐

Fat Donny Bone Spurs and Ally Al Lyons sneak into the Anonymous Buccaneers support group and are told to report to Captain CiaoCiao who is sitting to the right of whom in the conversation circle. Both try to remember. They do not necessarily start with the same person in their enumerations.

Task:

  • Write a method boolean isSameCircle(List<String> names1, List<String> names2) that tests whether the names in the two lists immediately follow each other one and the same order. Consider that the people are sitting in a circle, and the last person in the list "sits" next to the first person in the list. Names of individuals may appear more than once.

Examples:

  • List 1: Alexandre, Charles, Anne, Henry. List 2: Alexandre, Charles, Anne, Henry` → same

  • List 1: Anne, Henry, Alexandre, Charles, List 2: Alexandre, Charles, Anne, Henry → same

  • List 1: Alexandre, Charles, Anne, Henry. List 2: Alexandre, Charles, Henry, Anne → not the same

  • List 1: Anne, Henry, Alexandre, Charles, List 2: Alexandre, William, Anne, Henry → not the same

Solution

1.2.6. And now the weather: Find repeated elements ⭐

Napoleon Nose chats with Bonny Brain about the weather, "We’ve had so many rainy days for the last few months, it’s been bad for capering." Bonny Brain replies, "We haven’t had that many rainy days in a row!". Who is right?

Given a list of weather data:

Rain, sun, rain, rain, hail, snow, storm, sun, sun, rain, rain, sun.

In the list, sun occurs three times in a row. That is what we want to know. Although rain occurs more often in the list overall, that is not relevant to the solution.

And now the weather Find repeated elements

Task:

  • Create a new record WeatherOccurrence for weather information:

    record WeatherOccurrence( String weather, int occurrences, int startIndex ) { }

  • Implement a method WeatherOccurrence longestSequenceOfSameWeather(List<String> weather) that reveals,

    • what weather

    • how many times it appears in the list directly after each other and

    • where the longest list starts.

      If weather occurs the same number of times in a row, the method is free to decide what it returns. Elements may be null.

Solution

1.2.7. Generate receipt output ⭐

A receipt contains entries and information such as quantity, product name, price, total.

Program a receipt in this task.

Task:

  • Create a new class Receipt for the receipt.

  • A receipt consists of items of type Item. Create the class Item as a nested type in Receipt.

  • Each Item has a name and a (gross) price stored in cents.

  • Receipt should override toString() and return a formatted receipt:

    • Output all products and the total.

    • Entries can appear more than once on the receipt and should be summarized. For example, there are not nuts, nuts in the list, but 2x nuts. The entries must have the same name and price for equivalence.

    • Use a Locale you like in NumberFormat.getCurrencyInstance(locale) to format the currency.

Example:

  • With the structure

    Receipt receipt = new Receipt();
receipt.addItem( new Receipt.Item( "Peanuts", 222 ) );
receipt.addItem( new Receipt.Item( "Lightsaber", 19999 ) );
receipt.addItem( new Receipt.Item( "Peanuts", 222 ) );
receipt.addItem( new Receipt.Item( "Log book", 1000 ) );
receipt.addItem( new Receipt.Item( "Peanuts", 222 ) );
System.out.println( receipt );

    is the output (the comma is used as a decimal separator):

    3x  Peanuts                 2,22 €    6,66 €
1x  Lightsaber            199,99 €  199,99 €
1x  Logbook                10,00 €   10,00 €

Sum: 216,65 €

Solution

1.2.8. Everything tastes better with cheese: Insert elements into lists ⭐

Captain CiaoCiao likes veggies, but when he does, he has to add lots of cheese.

Everything tastes better with cheese Insert elements into lists

Task:

  • Write a method insertCheeseAroundVegetable(List) that gets a list of recipe ingredients and whenever vegetables appear in the list, adds the ingredient "cheese" right before or after it.

  • The list must be modifiable.

Examples:

  • gnocchi, zucchini, peppers, cream, broth, milk, butter, onion, tomato, salt, bell pepper → gnocchi, zucchini, cheese, peppers, cheese, cream, broth, milk, butter, onion, cheese, tomato, cheese, salt, bell pepper.

  • Cheese → Cheese

Use a fixed set of vegetables.

Solution

1.2.9. Search elements with the iterator and find Covid Cough ⭐⭐

Bonny Brain runs to the port and looks for Covid Cough, who is stashing disinfectant in his ship. Each ship contains a list of passenger names. Ships are declared by the following small class:

class Ship {
  private List<String> persons = new ArrayList<>();
  void addName( String name ) { persons.add( name ); }
  boolean contains( String name ) { return persons.contains( name ); }
  @Override public String toString() {
    return "" + persons;
  }
}

There are 100 ships at the port, stored in a LinkedList<Ship>. Covid Cough is hiding in an unknown ship, let’s simulate that: 

final int NUMBER_OF_SHIPS = 100;

List<Ship> ships = new LinkedList<>();
for ( int i = 0; i < NUMBER_OF_SHIPS; i++ )
  ships.add( new Ship() );

ships.get( new Random().nextInt( ships.size() ) ).addName( "Covid Cough" );

Bonny Brain arrives at one of the many entrances to the harbor, and there are ships to her right and left:

int index = new Random().nextInt( ships.size() );
ListIterator<Ship> iterator = ships.listIterator( index );

The only access to the ships is given by the ListIterator. Keep in mind that the ListIterator can only be used to go forward and backward, there is no random access!

Search elements with iterator find Covid Cough

Task:

  • Visit the ships with the ListIterator, and find Covid Cough.

  • Is there a strategy how to find the person most efficiently? It is known how many ships there are in total, 100. Since the index is known where Bonny Brain enters the harbor, we also know how many ships are to the left and right of the entrance.

Solution

1.2.10. Move elements, play musical chairs ⭐

At a birthday party, the guests are playing musical chairs. People sit on chairs, and when the music starts playing, they get up and walk around the chairs. The names of the guests are in a list.

Task A:

  • Create a new class MusicalChairs.

  • Create a constructor MusicalChairs(String... names) that stores the names internally.

  • Implement the method toString() which returns the names comma separated.

  • Write a method rotate(int distance) that shifts the names in the list by the position distance to the right. The elements falling out to the right are pushed back into the left. The operation is in place, so the (internal) list itself is changed, and the method does not return anything.

Use a suitable method from Collections for the task.

Example:

MusicalChairs musicalChairs =
    new MusicalChairs( "Laser", "Milka", "Popo", "Despot" );
musicalChairs.rotate( 2 );
System.out.println( musicalChairs ); // Popo, Despot, Laser, Milka

Task B:

  • Write another method void rotateAndRemoveLast(int distance), which first moves the list by distance positions to the right and then deletes the last element.

  • Add a method String play() that calls rotateAndRemoveLast(…​) in a loop until there is only one element left in the list; then the winner is determined, and it is returned as a string. The distance is random on each pass.

Consider the case where the list might be empty in the solution.

Solution

1.2.11. Programming a question game with planets ⭐⭐

Captain CiaoCiao is accepting recruits, and to test their knowledge, he asks them the diameter of the planets in the solar system. He wants an interactive application for this, where a planet is randomly selected, and the recruits must know the diameter.

The planets are predefined as an enumeration type:

com/tutego/exercise/util/PlanetQuiz.java
enum Planet {

  JUPITER( "Jupiter", 139_822 ), SATURN( "Saturn", 116_464 ),
  URANUS( "Uranus", 50_724 ), NEPTUNE( "Neptune", 49_248 ),
  EARTH( "Earth", 12_756 ), VENUS( "Venus,", 12_104 ),
  MARS( "Mars", 6_780 ), MERCURY( "Mercury", 4_780 ),
  PLUTO( "Pluto", 2_400 );

  public final String name;
  public final int    diameter; // km

  Planet( String name, int diameter ) {
    this.name     = name;
    this.diameter = diameter;
  }
}
Programming a question game with planets

Task:

  • Program a console application that builds a random sequence of all planets in the first step. Consider how we can use the shuffle(…​) method from java.util.Collections for this.

  • Iterate over this random sequence of planets, and generate a console output that asks for the diameter of those planets. As a choice, the recruit should be shown four diameters in kilometers, where one diameter is the correct one and three diameters are from different planets.

  • If the recruit enters the correct diameter, a message appears on the screen; if the wrong diameter is entered, the console output reports the correct diameter.

Example:

What is the diameter of planet Uranus (in km)?
49248 km
50724 km
12756 km
139822 km
50724
Correct!

What is the diameter of planet Pluto (in km)?
12104 km
4780 km
2400 km
12756 km
11111
Wrong! The diameter of Pluto is 2400 km.

What is the diameter of planet Jupiter (in km)?
139822 km
6780 km
2400 km
49248 km
…

Solution

1.2.12. Understanding the implementation of the class java.util.ArrayList ⭐⭐

A java.util.ArrayList is an important data structure. It is in competing with an array. Two questions come to mind: how is the ArrayList actually implemented, and how big might the speed difference be?

  • See https://github.com/AdoptOpenJDK/openjdk-jdk11/blob/master/src/java.base/share/classes/java/util/ArrayList.java for implementation sources. Get an overview.

  • Internally, the implementation uses the array elementData for the data. How does the implementation of get(int) and set(…​) work? What are the `costs?

  • Where is the array object elementData created?

  • An ArrayList is usually always a bit larger than the number of current elements, as a kind of buffer. The size is called capacity. If you build an ArrayList object with the standard constructor, how many elements is there room for in the array?

  • If on insertion, the array is too small, ensureCapacity(…​) will increase the size of the array. How does this method work? What is the strategy behind it?

  • Build an ArrayList with the standard constructor and append 1,000 elements. How many copy operations are necessary?

1.3. Sets

Sets contain their elements only once. They can be unsorted or sorted. Java provides the Set interface for abstraction, two important implementations are HashSet and TreeSet.

A whole series of questions arise with sets:

  1. Is the set empty?

  2. Which elements are in the set?

  3. Is an asked element in the set, yes or no?

  4. Given two sets, do they both contain the same elements?

  5. What does a new set look like when two sets are united?

  6. Does the set completely contain another set, so is one set a subset of another?

  7. What is the intersection of two sets, that is, what are the elements that occur in both sets?

  8. What is the difference set, that is, if you delete elements from one set that are present in another set?

Some of these operations can be answered directly using the Set data type. For example, there are the methods isEmpty() or contains(…​). Set operations, in particular, are not very well-supported, and programmers sometimes have to take workarounds for them. For subsets, for example, there is the Collections method disjoint(Collection<?>, Collection<?>), but it returns a boolean that says whether the two collections have no common element.

Let’s answer some questions with tasks.

1.3.1. Form subsets, find common elements ⭐

Bonny Brain’s daughter is dating Cora Corona, and they want to find out if they are compatible. So, they both write down what they like. It looks like this:

Set<String> hobbies1 = Set.of(
    "Candy making", "Camping", "Billiards", "Fishkeeping", "Eating",
    "Action figures", "Birdwatching", "Axe throwing" );
Set<String> hobbies2 = Set.of( "Axe throwing", "Candy making", "Camping",
  "Action figures", "Case modding", "Skiing", "Satellite watching" );
Form subsets find common elements

Task:

  • What is the percentage of similarity between the two? Also, what are some methods we could use to answer this question?

Look up methods in Set to see if they can be used to form subsets or intersections.

Solution

1.3.2. Get all words contained in a word ⭐⭐

Captain CiaoCiao intercepts a secret message, and the text consists of seemingly unrelated words. After some pondering, it occurs to him that there are other words in the words.

A program is to find out what valid words a given word contains. To find out what is a valid word, you can use a word list from the Internet:

Task:

  • Write a program with a static method Collection<String> wordList(String string, Collection<String> words) that generates all substring contained in string and returns exactly those words in a Collection that are valid words in the dictionary words and are at least three characters long.

Example for the English dictionary:

  • wordList( "wristwatches", words ) → [wrist, wristwatch, wristwatches, rist, is, twa, twat, wat, watch, watches, tch, tche, che, hes]

  • abibliophobia → [abib, bib, bibl, bibliophobia, pho, phobia, hob, obi, obia]

A file with words can be transformed into a data structure like this:

private static final String WORD_LIST_URL =
    // "https://raw.githubusercontent.com/creativecouple/all-the-german-words/master/corpus/de.txt";
    "https://raw.githubusercontent.com/ullenboom/english-words/master/words_alpha.txt";

private static Collection<String> readWords() throws IOException {
  URL url = URI.create( WORD_LIST_URL ).toURL(); //    370.000 words
  Collection<String> words = HashSet.newHashSet( 400_000 );
  try ( InputStream is = url.openStream() ) {
    new Scanner( is ).forEachRemaining( s -> words.add( s.toLowerCase() ) );
  }
  return words;
}

Solution

1.3.3. Exclude duplicate elements with a UniqueIterator ⭐⭐

In other data structures, for example, lists, elements can occur more than once. Write a UniqueIterator that returns elements of a Collection only once. null never occurs as an element.

The generic types are declared as follows:

public class UniqueIterator<E> implements Iterator<E> {

  public UniqueIterator( Iterator<? extends E> iterator ) {
    // …
  }

  // etc.
}

The constructor indicates that the new iterator gets an existing iterator as a parameter. So, a call could look like this:

List<String> names = …;
Iterator<String> UniqueIterator = new UniqueIterator( names.iterator( ) );

Solution

1.4. Map keys to values

A hash table associates keys with values. In other programming languages, they are also called dictionaries. Java uses the Map interface to specify the operations for all implementations. Two important implementations are HashMap and TreeMap.

1.4.1. Convert two-dimensional arrays to map ⭐

Data types that inherit from Collection are relatively flexible in accepting data; for example, the elements of a List can be copied into a Set via addAll(Collection). Arrays can also be used directly as Collection with Arrays.asList(…​).

The Map data type is less flexible, it is not possible to simply transfer arrays or other Collection collections into a Map.

Task:

  • Write a method Map<String, String> convertToMap(String[][]) that converts a two-dimensional array into a java.util.Map.

  • The first entry in the array should be the key, the second the value.

  • The keys correctly implement hashCode() and equals(…​).

  • If later in the array the same key occurs again, the method will overwrite the earlier pair.

  • Keys and values must not be null and must lead to an exception.

Example:

String[][] array = {
    { "red",   "#FF0000" },
    { "green", "#00FF00" },
    { "blue",  "#0000FF" }
};
Map<String, String> colorMap = convertToMap( array );
System.out.println( colorMap ); // {red=#FF0000, green=#00FF00, blue=#0000FF}

Solution

1.4.2. Convert text to Morse code and vice versa ⭐

Captain CiaoCiao needs to send a message to a distant island using Morse code. A Morse code message consists of short and long symbols, indicated by the characters . and -.

Copy the following definition into a new class Morse:

// A .-      N -.      0 -----
// B -...    O ---     1 .----
// C -.-.    P .--.    2 ..---
// D -..     Q --.-    3 ...--
// E .       R .-.     4 ....-
// F ..-.    S ...     5 .....
// G --.     T -       6 -....
// H ....    U ..-     7 --...
// I ..      V ...-    8 ---..
// J .---    W .--     9 ----.
// K -.-     X -..-
// L .-..    Y -.--
// M --      Z --..

Task:

  • Create a new class Morse.

  • Write two methods:

    • String encode(String string). It accepts a string and converts it to Morse code. Each character of the string is to be output in the corresponding Morse code. Each block is to be separated by a space in the output. Unknown characters are skipped. Lowercase letters shall be evaluated like uppercase letters. There are two spaces between words.

    • String decode(String string). Turns Morse code back into the original strings. The two spaces for word separators become single spaces again.

Solution

1.4.3. Remember word frequency with associative memory ⭐⭐

Girly Gossip listens in on the deck of a group, so she can tell Captain CiaoCiao later what is being discussed. What is important is what is often mentioned as a word or phrase.

Task:

  • Write a method List<String> importantGossip(String... words) that returns, from a vararg of strings, exactly the five strings in a list that occur most frequently in the array passed.

Example:

String[] words = {
    "Baby Shark", "Corona", "Baby Yoda", "Corona", "Baby Yoda", "Tiger King",
    "David Bowie", "Kylie Jenner", "Kardashian", "Love Island", "Bachelorette",
    "Baby Yoda", "Tiger King", "Billie Eilish", "Corona"
};
System.out.println( importantGossip( words ) );

outputs

[Baby Yoda, Corona, Tiger King, Baby Shark, Bachelorette.]

Keep in mind that it is not about the individual words like Baby or Yoda, but always about the whole string, for example, Baby Yoda or Baby Shark.

Solution

1.4.4. Read in and read out colors ⭐⭐

Bonny Brain gets a new design for their flags, but the designers only speak gibberish:

For the background, let's use #89cff0 or #bcd4e6, and for the text, maybe #fffaf0 or #f8f8ff.

She finds out that a specification like #RRGGBB stands for the red, green, blue part of a color, coded in hexadecimal. Fortunately, there are "translation tables" like https://tutego.de/download/colors.csv, which contains lines like

amber,"Amber",#ffbf00,255,191,0
aqua,"Aqua",#0ff,0,255,255
blush,"Blush",#de5d83,222,93,131
wine,"Wine",#722f37,114,47,55

Occasionally, the file contains the color values only with three symbols, like in the example aqua with 0ff. In this case, the individual color values are doubled, so #RGB then becomes #RRGGBB.

Task:

  1. Create a new class Color for the representation of colors. Each color has a name ( String name) and an RGB value (int rgb). Write — or generate via the IDE — the method toString(). Add further methods if that is useful.

  2. Create a new class ColorNames.

    • Give the class an instance variable HashMap<Integer, Color> colorMap, so that ColorNames can internally remember all Color objects in a Map; the keys of the Map are the RGB values as integer, and the associated value is the corresponding Color object.

    • Copy the file https://tutego.de/download/colors.csv locally to disk.

    • Create a constructor that reads the file. We can use Scanner for this, or read the file completely with Files.readAllLines(Paths.get("colors.csv")), which returns a List<String>.

    • Split each line of the CSV source, extract the color name (2nd column) and RGB value (3rd column). Tip: The color value can be converted to an integer using a Java method: Integer.decode("#722f37") returns 7483191. Remember that color names can be in the form #RGB and #RRGGBB.

    • Transfer the color name and integer value to Color objects, and place them in the Map.

    • Add a method decode(int rgb) that returns the associated Color object for an RGB value.

Example:

  • mapper.decode( 7483191 ) → Optional['Wine' is RGB #722F37]

  • mapper.decode( 7 ) → Optional.empty

Solution

1.4.5. Read in names and manage lengths ⭐

Bonny Brain likes to play name crossword puzzles where each entry is a name. Often she can’t think of a name with a certain length — software should help!

Task:

  1. The file http://tutego.de/download/family-names.txt contains last names. Save the file on your file system.

  2. To read the file, we can utilize either the Scanner class or the Files method readAllLines(Path).

  3. Sort the names into a TreeMap<Integer, List<String>>: The key is the length of the name, the list contains all names with the same length.

  4. On the command line, list all names in ascending order of length.

  5. Ask from the command line for a length and output all names of that length as long as the length is not 0 or negative.

Solution

1.4.6. Find missing characters ⭐⭐

Captain CiaoCiao has scammed the Dead Sea Scrolls (Cumexhopp scrolls) and no one has been able to decipher the text yet. He wants to make it! However, many characters are unreadable, while other characters are easily readable. It is also easy to see how many characters the word has.

Task:

  • Create a new class with the main(…​) method and copy the two lists into the program:

    List<String> words = Arrays.asList( "house", "mouse", "horn", "cannon" );
List<String> missingLettersWords = Arrays.asList( "_ouse", "ho__", "ca__on", "gun", "__e__", "_____" );

  • Match each word from missingLettersWords with all possible words from the dictionary words where the underscore symbolizes unknown characters.

  • The length of the suggested words from the dictionary must be equal to the word length of the unreadable word.

  • At least one character must be given.

Example:

  • Possible screen output from the given lists:

    _ouse -> [mouse, house]
ho__ -> [horn]
ca__on -> [cannon]
gun -> No results
__e__ -> No results
_____ -> No results

Solution

1.4.7. Calculate number of paths to the three-headed monkey ⭐⭐

After a night of drinking in Manhattan, Captain CiaoCiao misses his three-headed monkey. He must have lost the stuffed animal somewhere along the way! But where could it be? His team has to walk all the streets from start to finish. The only thing Captain CiaoCiao can remember is that he didn’t get across the diagonal.

Catalan number 4x4 grid example
Figure 2. Possible routes from the start to the finish (source: Wikipedia)

The image shows 4 × 4 street blocks and there are 14 possibilities. After some time of looking for, the crew finds the stuffed animal, they are lucky!

Captain CiaoCiao ponders: What if there were 5 or 10 blocks — wouldn’t the number of paths then be much too large to search?

The answer to the question is provided by mathematics. What is being searched for here is a monotonic path for a square with n × n cells. The number of possible paths provides the Catalan number, which is calculated as follows:

Cn = (2n)! / (n+1)! n!

Task:

  • Convert the formula by the method BigInteger catalan(BigInteger n). Use your own internal method BigInteger factorial(BigInteger n) for the factorial calculation.

  • Three factorials must be calculated in the formula: n!, (n+1)! and (2n)!. It is (n+1)! nothing else than n! × (n+1) is, so n! has to be calculated twice; also on the way to the calculation of (2n)! the intermediate result (n+1)! arises. So many multiplications have to be done twice, so the products should be cached: resort to the data type WeakHashMap for this.

  • Compare the times when we call the catalan(…​) method twice with the same parameters. Use the following code as a template:

    long start = System.nanoTime();
BigInteger catalan1000 = catalan( BigInteger.valueOf( 1000 ) );
long end = System.nanoTime();
System.out.println( catalan1000 );
System.out.println( TimeUnit.NANOSECONDS.toMillis( end - start ) );

Solution

1.4.8. Manage holidays in a sorted associative store ⭐

Elements in a TreeMap are automatically sorted. TreeMap implements java.util.NavigableMap, which HashMap does not. The order is either determined by an external Comparator, or the elements have a natural order.

From the API documentation, we see that firstEntry() and lastEntry() return the smallest and largest element, respectively. The return type is Map.Entry<K,V>.

Given a key key, the following methods return relative to that key:

  • ceiling*(K key): Returns a result that is greater than or equal to this key.

  • floor*(K key): Returns a result that is less than or equal to the given key.

  • lower*(K key): Returns a result that is strictly less than the given key.

  • higher*(K key): Returns a result that is strictly greater than the given key..

All methods return null if there is no answer to the question.

For subsets, the following methods are useful:

  • SortedMap<K,V> subMap(K fromKey, K toKey)

  • NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)

In the first case, fromKey is inclusive and toKey is exclusive; this corresponds to the usual convention of Java. The second method allows more precise control over whether the start or end element belongs.

Task:

  • Build a sorted associative memory:

    NavigableMap<LocalDate, String> dates = new TreeMap<>( Map.of(
  LocalDate.of( 2024, Month.JANUARY, 1 ), "New Year's Day",
  …
) );

    The type <LocalDate, String> means that a temporal type LocalDate should be associated with a string.

  • The class LocalDate implements Comparable, which means that the elements have a natural order.

  • Fill the data structure with some pairs for real or fictitious holidays.

  • Answer the following questions using the appropriate methods of NavigableMap:

    • According to the data structure, what is the earliest and last holiday?

    • The Christmas vacation end on the 6th of January. What is the first holiday after the Christmas vacation?

    • Which date values are in the Christmas vacation from December 23 – January 6 (date values inclusive)?

    • Delete all registered holidays that fall within the Christmas vacations from the data structure.

Solution

1.4.9. Determine commonality: Party set and souvenir ⭐

Bonny Brain plans a party, and all families contribute:

Set<String> gombonoGifts = new HashSet<>();
Collections.addAll( gombonoGifts, "Vodka", "BBQ Grill", "kneading soap" );

Set<String> banannaGifts = new HashSet<>();
Collections.addAll( banannaGifts, "Vodka", "drinking helmet" );

Set<String> cilimbiGifts = new HashSet<>();
Collections.addAll( cilimbiGifts,
                    "drinking helmet", "Money box", "Vodka", "water pistol" );

List<Set<String>> families =
    Arrays.asList( gombonoGifts, banannaGifts, cilimbiGifts );

Since Bonny Brain is a perfection strategist, she wants to know if things are brought multiple times.

Task:

  • Write a method printMultipleGifts(List<Set<String>> families) that outputs which things are brought how many times.

  • What was brought more than once?

Example:

  • Possible output for the upper assignments:

    {drinking helmet=2, kneading soap=1, water pistol=1, Money box=1, BBQ Grill=1, Vodka=3}
drinking helmet
Vodka

Solution

1.5. Properties

The class Properties is a special associative memory that associates only string with strings. The class not only represents a data structure, but can also read and write files called property files. These are text files that are usually used for configuration. Key-value pairs are separated in the file by =. It is also possible to read and write the values in an XML format, but this is uncommon.

1.5.1. Develop convenient properties decorator ⭐⭐

The Properties class contains key-value pairs, where the keys are always just strings. Possible conversions have to be done by developers themselves, which is inconvenient.

Task:

Write a class PropertiesConfiguration that decorates a Properties object. The most general method returns an Optional that is either filled or empty if the key does not exist:

  • Optional<String> getString(String key).

The advantage with the Optional is that alternatives for default values can easily be determined: conf.getProperty("rank").orElse("Captain").

Other methods of PropertiesConfiguration are to perform conversions:

  • Optional<Boolean> getBoolean(String key)

  • OptionalLong getLong(String key)

  • OptionalDouble getDouble(String key)

  • Optional<BigInteger> getBigInteger(String key)

If there was no associated value to the key, the container is empty. If the conversion to an error fails, that also results in an empty container.

Example for the API:

Properties root = new Properties();
root.setProperty( "likes-rum", "true" );
root.setProperty( "age", "55" );
root.setProperty( "income", "123456789012" );
root.setProperty( "hobbies", "drinking, gambling\\, games, swearing competitions" );
root.setProperty( "weakness_of_character", "" );
PropertiesConfiguration conf = new PropertiesConfiguration( root );
Optional<Boolean> maybeLikesRum = conf.getBoolean( "likes-rum" );
OptionalLong maybeAge = conf.getLong( "age" );
Optional<BigInteger> maybeIncome = conf.getBigInteger( "income" );

System.out.println( maybeLikesRum );       // Optional[true]
System.out.println( maybeAge );            // OptionalLong[55]
System.out.println( maybeIncome );         // Optional[123456789012]

Optional addition: query lists.

Advanced developers can implement the following method:

  • List<String> getList(String key). Returns a list of comma-separated strings. The comma itself can be masked out by \,.

Example:

List<String> hobbies = conf.getList( "hobbies" );
List<String> weaknessOfCharacter = conf.getList( "weakness_of_character" );

System.out.println( hobbies );             // [drinking, gambling, games, swearing competitions]
System.out.println( hobbies.size() );      // 3
System.out.println( weaknessOfCharacter ); // []

*Optional addition: store binary values

A java.util.HashMap can associate arbitrary types, for a Properties only strings can be associated with strings. If other data types, such as byte arrays, are to be stored, they must be converted to a string. A byte[] can be converted to an ASCII string in various ways, such as using BASE64 encoding; Java can do this using the class Base64.

Since Properties are read rather than written, the get*(…​) methods were sufficient for us so far. With the following addition, two new methods are to be written, one for setting and one for querying:

  • void putBinary(String key, byte[] bytes)

  • Optional<byte[]> getBinary(String key)

An example of use:

conf.putBinary( "binary", new byte[]{ 0, 1, 127, (byte) 254, (byte) 255 } );
System.out.println( conf.getString( "binary" ) ); // Optional[AAF//v8=]
conf.getBinary( "binary" ).ifPresent( binary ->
  System.out.printf( "%d %d %d %d %d",
                     binary[0], binary[1], binary[2], binary[3], binary[4] )
);

Solution

1.6. Stack and queues

A general list in Java lets us access the elements by an index, we call such access also random access because we have the choice to ask for an element at any position. There are data structures that are much more restricted and can, for example, only insert or delete elements at the beginning or end. These include:

  • stack

  • queues

With a stack, you can only insert elements at one end and must remove the elements again at this end. The principle is also called LIFO: last in, first out. In contrast to this is the queue. With it, that is read out first, which was added also as first. The principle is called FIFO: first in, first out.

Pure stacks and queues do not exist in Java, only interfaces implemented by lists.

1.6.1. Program RPN pocket calculator ⭐

We usually write mathematical expressions in infix notation, where the operators are placed between the operands, such as 47 + 11. In principle, however, the operator can also stand in front of the operands, as in + 47 11, or behind them, as in 47 11 +.

The Hewlett-Packard pocket calculators had established a special input in the 1980s, the Reverse Polish Notation (RPN). This is a postfix notation where the operators are placed after the values. The advantage for computers is that the precedence — point before line calculation — has already been resolved by users, simplifying program logic in the calculator. PostScript also uses this representation because mathematical expressions can be easily evaluated via a stack.[2]

We want to program a RPN calculator.

Task:

  1. Write a program that first tokenizes a string like "12 34 23 + *". Hint: For splitting, you can use split(…​) of String or a Scanner.

  2. After splitting, the result is to be evaluated. Start with a fixed string for testing.

  3. Read in a string from the command line so that we have a real RPN calculator.

  4. What errors and problems need to be handled and caught? How should we handle errors?

Solution

1.7. BitSet

The class BitSet is a space-saving and performant alternative to boolean arrays. The data structure is useful when you need a mapping of an integer to a truth value. The data structure can quickly answer whether an index (a positive integer) is associated with true or false. If the number of bits becomes too large, or if there are large gaps, https://github.com/brettwooldridge/SparseBitSet is a good alternative.

1.7.1. Forget no ship ⭐

Once a year there is an exercise where 13 ships have to be boarded. Each of the ship is uniquely identified by a number from 10 to 22. Once the adventure be over, our trusty Bonny Brain receives a list of the ships that their crew boarded. It could be something like this:

  • {10, 20, 21, 15, 16, 17, 18, 19, 11, 12, 13, 14, 22 }

Sometimes she gets lists where numbers are missing or appear twice:

  • {10, 20, 21, 15, 16, 17, 18, 22 }

  • {10, 20, 21, 10, 15, 16, 10 }

Such lists show Bonny Brain that ships were forgotten or repeatedly raided during the exercise. Since manual checking is inconvenient, software should do the job.

Forget no ship

Task:

  • Create a new class with a new static method checkForCompletedCompetition(int... shipIds). Pass the IDs of the ships.

  • Report which ships were raided multiple times. The amount is not significant.

  • Report if a ship was not raided and which one it was.

  • Write the program in such a way that no two nested loops are used. In other words, the runtime should not be quadratic.

Solution

1.7.2. Find duplicate entries, and solve the animal chaos ⭐

Captain CiaoCiao feeds the animals of his private zoo before going to bed. But being a bit tipsy from the rum, he forgets to close the gate. The next morning, Finian Fishbone and Fred Fritte notice that animals are missing. They quickly run to Captain CiaoCiao: "Some animals have escaped!" — "Scurvy baboon! Which ones?" asks the captain. The two ponder and record (writing is not their strong suit):

  • 🐩🐏🐴🦋🐙

  • 🐴🐏🐧🐸🦋🐌

Captain CiaoCiao notes that both have poor memories, and only wants to have animals searched for that are named by both.

Task:

  • Write a method String sameSymbols(String, String) that returns a string containing the common symbols. The order is not significant, all Unicode characters are possible.

  • Since we have to iterate over all characters of the string and it contains "higher" Unicode characters, which are moved out by two char, the solution is to use string.codePoints().forEach(consumer). This statement iterates over all characters of the String string and calls the passed IntConsumer for each character. This is an application of the Stream API, which we will look at in more detail in the next chapter.

Examples:

  • sameSymbols("🐩🐏🐴🦋🐙", "🐴🐏🐧🐸🦋🐌") → "🐏🐴🦋"

  • sameSymbols("abcy", "bcd") → "bc"

  • sameSymbols("abc", "def") → ""

Since the result is urgent, implement the method so that the runtime is linear with the length of the strings, in computer science jargon: O(N+M) if N and M are the lengths of the strings. All Unicode characters are allowed.

Solution

1.8. Thread-safe data structures

For the previous tasks around the data structures ArrayList, LinkedList, HashSet, TreeSet etc. we never needed more than the main thread. In the following tasks, more threads and concurrent accesses come into play, and then we need to use thread-safe data structures. For the solutions, we want to use the data types from the package java.util.concurrent. The package contains different thread-safe data structures, which work correctly even with an arbitrary number of parallel accesses and have an excellent performance.

1.8.1. Understanding the difference between HashMap, Synchronized-Wrapper, ConcurrentHashMap.

The data structures from the Collection API are not thread-safe. In the package java.util.concurrent there are data structures that can be accessed by many threads.

  • Create a HashMap and write with many threads concurrently into the data structure; it will break, how can you notice that?

  • Use the synchronized wrapper Collections.synchronizedMap() and try again. What is the result?

  • Use a ConcurrentHashMap. What happens here when you access it with multiple threads? What advantage does it have over the synchronized wrapper?

  • There is also Hashtable, where does this class come from and, do we still use it?

Solution

1.8.2. Loading ship ⭐⭐

Captain CiaoCiao and the crew are getting ready for the next big adventure on Gazorpazorp Island. 5 employees put crates and barrels on the loading ramp, and 10 employees stow the goods in the ship. There can be no more than 5 objects on the loading dock at a time.

Loading ship

Task:

  • Create an ArrayBlockingQueue<String> of capacity 5 for the ramp.

  • Create two different Runnable implementations Loader and Unloader which get a reference to the ArrayBlockingQueue.

    • The Loader puts strings on the ramp (random strings from a set of product names).

    • The Unloader shall take strings from the ramp and output them to the screen.

      It takes Loader and Unloader randomly between 1 and 2 seconds for their work.

  • 5 threads shall be Unloader and 10 threads Loader.

There are different methods for adding and removing. The difference is important. Otherwise, program errors may occur:

Table 1. BlockingQueue methods for adding and removing elements.
operationexceptionnull returnblocked

insert

add(e)

offer(e)

put(e)

Remove

remove()

poll()

take()

You can’t deduce the semantics from the method names, you have to learn the difference. For our task, only one column, and these methods come into question.

Solution

1.8.3. Handle important messages first ⭐⭐

A PriorityQueue has an internal sorting so that the items with a higher priority move to the front. The priority comes from either the natural ordering of the elements implementing Comparable or an external Comparator. "Small" elements have a higher priority and move to the front of the PriorityQueue. At the end of the queue are the elements with the lowest priority. (This is the same as with vaccinations: Prioritization group 1 gets the stuff first).

Captain CiaoCiao gets work orders from various parties, but everything from Bonny Brain has top priority. Each work order from Bonny Brain contains the coseword "Little Canon," which lets the captain know that it is time to spring into action immediately.

Task:

  • Put the following record into the project:

    record Message( String message, LocalDateTime timestamp ) {
  Message( String message ) {
    this( Objects.requireNonNull( message ), LocalDateTime.now() );
  }
  @Override public String toString() {
    return "'%s', %s".formatted(
      message, timestamp.format( DateTimeFormatter.ofPattern("mm:ss.SSSSSSS") )
    );
  }
}

    toString() encloses the message in single quotes and displays only the minutes and seconds of the timestamp, because that is enough for a quick visual comparison of which message is younger or older.

  • For Message implement a Comparator which creates an order so that messages with the term of endearment are »smaller« than messages without the coseword, so that this can be evaluated as a higher priority later. If both messages contain a term of endearment or both messages do not contain a term of endearment, they are equally important.

  • Extend the Comparator by another comparison logic, so that the timestamp is considered, and an earlier message is also processed earlier.

  • Initialize the PriorityQueue with messages, and watch how messages with the term of endearment move forward in the queue.

Example:

Assuming that PriorityQueue<Message> tasks is a correctly initialized data structure, the following program will produce the output shown:

tasks.add( new Message( "Treasure Hunt" ) );
System.out.println( "= " + tasks );

tasks.add( new Message( "Little Canon, Family Movie Night!" ) );
System.out.println( "= " + tasks );

tasks.add( new Message( "Build a pirate ship" ) );
System.out.println( "= " + tasks );

System.out.println( tasks.remove() + "\n" + "= " + tasks );
System.out.println( tasks.remove() + "\n" + "= " + tasks );

tasks.add( new Message( "Capture the Flag" ) );
System.out.println( "= " + tasks );

tasks.add( new Message( "Bury the treasure, Little Canon" ) );
System.out.println( "= " + tasks );

tasks.add( new Message( "Little Canon, make a treasure map" ) );
System.out.println( "= " + tasks );

for ( int i = 0; i < 4; i++ )
  System.out.println( tasks.remove() + "\n" + "= " + tasks );

The output is:

= ['Treasure Hunt', 44:20.8500129]
= ['Little Canon, Family Movie Night!', 44:20.8580242, 'Treasure Hunt', 44:20.8500129]
= ['Little Canon, Family Movie Night!', 44:20.8580242, 'Treasure Hunt', 44:20.8500129, 'Build a pirate ship', 44:20.8590231]
'Little Canon, Family Movie Night!', 44:20.8580242
= ['Treasure Hunt', 44:20.8500129, 'Build a pirate ship', 44:20.8590231]
'Treasure Hunt', 44:20.8500129
= ['Build a pirate ship', 44:20.8590231]
= ['Build a pirate ship', 44:20.8590231, 'Capture the Flag', 44:20.8665477]
= ['Bury the treasure, Little Canon', 44:20.8665477, 'Capture the Flag', 44:20.8665477, 'Build a pirate ship', 44:20.8590231]
= ['Bury the treasure, Little Canon', 44:20.8665477, 'Little Canon, make a treasure map', 44:20.8665477, 'Build a pirate ship', 44:20.8590231, 'Capture the Flag', 44:20.8665477]
'Bury the treasure, Little Canon', 44:20.8665477
= ['Little Canon, make a treasure map', 44:20.8665477, 'Capture the Flag', 44:20.8665477, 'Build a pirate ship', 44:20.8590231]
'Little Canon, make a treasure map', 44:20.8665477
= ['Build a pirate ship', 44:20.8590231, 'Capture the Flag', 44:20.8665477]
'Build a pirate ship', 44:20.8590231
= ['Capture the Flag', 44:20.8665477]
'Capture the Flag', 44:20.8665477
= []

Solution

1.8.4. If used up, create a new one ⭐⭐⭐

The expression new BigInteger(1024, new SecureRandom()) generates a large random number of type BigInteger.

Task:

  • Write a custom class SecureRandomBigIntegerIterator that implements Iterator and can return an infinite number of BigIntegers.

  • Whenever the number is queried and used up, a background thread should automatically compute a new random number.

Solution

1. The Compass Course (CC) is the angle between a ship’s path and compass north
2. Linux users usually have dc installed and can play a bit with the RPN, a brief introduction is provided by https://de.wikipedia.org/wiki/Dc_(Unix).