Interview round-up

Before a driving test, a good instructor does not teach you new roads. They drill the same short list again and again: mirrors, signals, the junction everyone gets wrong. The test is mostly those few moments.

Java Collections interviews work the same way. You already know the collections. What is left is a short list of questions that keep coming up, and a handful of traps that catch people who know the material but never saw the trap. This lesson is that list.

There are three parts to it.

• Fail-fast and fail-safe. What happens when a collection changes while you are looping over it, and which collections cope.
• A look at the concurrent collections. The ones built for several threads (separate strands of work running at the same time) sharing one collection.
• The traps. Small, specific, and each one has been asked in a real interview.

You will not meet much that is new. The point is to see it all together, and to be able to say it out loud.

Remember: an interview answer is usually one idea, one example, and one cost. Practise saying them in that order.

Lesson 5 showed that an ArrayList iterator stops with a ConcurrentModificationException if the list changes behind its back. Interviewers have a name for that behaviour: fail-fast. The iterator fails the moment it notices a problem, instead of carrying on with wrong data.

The opposite is fail-safe. A fail-safe iterator never complains, because it does not read the live collection at all. It reads a private snapshot (a frozen copy of how things were), so changes made while looping simply do not affect it. The right-hand side of the picture shows it: CopyOnWriteArrayList copies its array on every change, and the loop carries on with the old one.

Neither is better. They are a trade. Fail-fast costs nothing extra and shouts about bugs. Fail-safe never complains, but you pay for the copies, and your loop may be looking at old data.

Two notes to keep you accurate. Fail-fast is a best effort: Java does not promise to catch every change, so use it as a bug detector, not a feature. And "fail-safe" is the common interview word, not an official Java term. The Java documents describe these as iterators over a "snapshot".

Every block below can be pasted into jshell. First, a fail-safe loop.

List<String> names = new CopyOnWriteArrayList<>(List.of("Asha", "Ravi", "Meera"));
for (String name : names) {
    if (name.equals("Asha")) {
        names.add("Kiran"); // would throw on an ArrayList; here it is allowed
    }
    System.out.println("saw " + name);
}
System.out.println(names); // the new name is in the list, but the loop never saw it

saw Asha
saw Ravi
saw Meera
[Asha, Ravi, Meera, Kiran]

Adding "Kiran" inside the loop would crash an ArrayList. Here it is fine. The list has the new name, and the loop never saw it, because it was reading the older array. Use this for lists that are read all the time and changed rarely, such as a list of listeners that get notified. Writing is slow, because each change copies the whole array.

Now the second concurrent collection. When many threads change one ordinary HashMap at once, the result is unpredictable: updates get lost, and in the worst case the map is damaged. A ConcurrentHashMap is built for it.

Map<String, Integer> visits = new ConcurrentHashMap<>();
Thread[] workers = new Thread[4];
for (int i = 0; i < workers.length; i++) {
    workers[i] = new Thread(() -> {
        for (int n = 0; n < 1000; n++) {
            visits.merge("home", 1, Integer::sum); // one step that cannot be interrupted halfway
        }
    });
    workers[i].start();
}
for (Thread worker : workers) {
    worker.join(); // wait for everyone to finish before reading
}
System.out.println(visits.get("home"));

4000

Four threads each added 1 to the same key a thousand times, and none was lost. The key is merge: it reads, combines and stores as one step that cannot be cut in half by another thread. A line like map.put(key, map.get(key) + 1) is three steps, and another thread can sneak in between them even on a ConcurrentHashMap. When you need an update to be safe, use merge, compute or computeIfAbsent.

You do not need more than this for a first interview. Here is the short map of the rest:

• Collections.synchronizedList(list) wraps any list so each call takes a lock (a "one at a time" gate). It is simple and slow under heavy use, and looping over it still needs you to hold the lock yourself.
• ConcurrentLinkedQueue is a queue for many threads.
• BlockingQueue (such as LinkedBlockingQueue) makes a thread wait when the queue is empty or full. It is the standard tool for handing work from one thread to another.
• Vector, Hashtable and Stack are old, locked classes from before the collections framework. Don't use them in new code.

The traps

Now the junctions everyone gets wrong. First, nulls. Collections disagree about whether null (the "no object" value) is allowed.

Map<String, String> hash = new HashMap<>();
hash.put(null, "allowed"); // a HashMap accepts one null key
System.out.println(hash.get(null));
try {
    new TreeMap<String, String>().put(null, "x"); // a sorted map cannot compare null
} catch (NullPointerException e) {
    System.out.println("TreeMap refuses a null key");
}
try {
    new ArrayDeque<String>().offer(null); // null is how a deque says "empty"
} catch (NullPointerException e) {
    System.out.println("ArrayDeque refuses null");
}
try {
    new ConcurrentHashMap<String, String>().put("k", null);
} catch (NullPointerException e) {
    System.out.println("ConcurrentHashMap refuses null");
}

allowed
TreeMap refuses a null key
ArrayDeque refuses null
ConcurrentHashMap refuses null

A HashMap takes one null key. A TreeMap can't compare null with anything. ArrayDeque reserves null to mean "empty". ConcurrentHashMap refuses it because get returning null would not tell you whether the key was missing or held null, and with several threads there is no safe way to check. List.of, Set.of and Map.of refuse too, as lesson 10 showed.

Second, the remove trap from lesson 3, which interviewers love because the code looks innocent.

List<Integer> numbers = new ArrayList<>(List.of(10, 20, 30));
numbers.remove(1); // an int, so this means "remove the item at index 1"
System.out.println(numbers);
numbers.remove(Integer.valueOf(10)); // an Integer object, so "remove the value 10"
System.out.println(numbers);

[10, 30]
[30]

remove(1) removed the item at index 1, which was 20. To remove the value 10, you must pass an Integer object, here made by Integer.valueOf(10). A list of numbers has two remove methods, and an int argument picks the wrong one.

Third, comparing boxed numbers, from lesson 2.

Integer a = 1000;
Integer b = 1000;
// == asks "the same object?", and the answer for boxed numbers is not
// something to rely on. equals asks "the same number?", every time.
System.out.println(a.equals(b));

true

== asks "are these the very same object?". For boxed numbers like Integer, whether two equal numbers are the same object depends on how Java handles small values, so == can give you true in one test and false in another. Do not rely on it. equals asks "do they hold the same number?" and always answers correctly. Use equals for every object, including Integer, String and your own classes.

Fourth, a comparator that goes wrong. It looks natural to write a - b in a compare method, and it fails on large numbers.

int big = Integer.MAX_VALUE;
int small = -1;
// Subtracting can overflow and wrap round to a negative number...
System.out.println(big - small < 0); // "big is less than small": wrong
// ...so compare with Integer.compare, which never overflows.
System.out.println(Integer.compare(big, small) > 0);

true
true

The first line says "Integer.MAX_VALUE minus -1 is negative", so a - b reports that the biggest int is less than -1. The sum is too big for an int, so it wraps round to a large negative number. This is called overflow. Integer.compare(a, b) never overflows, which the second line shows. Always use it.

Last, a quiet one: subList.

List<Integer> numbers = new ArrayList<>(List.of(0, 1, 2, 3, 4, 5));
List<Integer> middle = numbers.subList(1, 3); // a window onto items 1 and 2, not a copy
System.out.println(middle);
middle.clear(); // clearing the window removes them from the real list
System.out.println(numbers);

[1, 2]
[0, 3, 4, 5]

subList(1, 3) is not a copy. It is a window onto the original list, so clearing the window removed those items from the real list. The same is true of Arrays.asList, keySet() and values() on a map. If you want an independent copy, wrap it: new ArrayList<>(list.subList(1, 3)).

Remember: remove(int) takes an index. == is for identity, equals is for content. a - b can overflow. Windows write through to the original.

The idea behind CopyOnWriteArrayList is small enough to write in a few lines.

static class TinyCopyOnWriteList<T> implements Iterable<T> {
    private Object[] items = new Object[0];

    int size() {
        return items.length;
    }

    void add(T value) {
        // Never change the array in use: build a new one and swap it in.
        Object[] bigger = Arrays.copyOf(items, items.length + 1);
        bigger[items.length] = value;
        items = bigger;
    }

    @Override
    public java.util.Iterator<T> iterator() {
        Object[] snapshot = items; // the iterator keeps the array as it is right now
        return new java.util.Iterator<>() {
            private int position = 0;

            @Override
            public boolean hasNext() {
                return position < snapshot.length;
            }

            @Override
            @SuppressWarnings("unchecked")
            public T next() {
                if (position >= snapshot.length) {
                    throw new java.util.NoSuchElementException();
                }
                return (T) snapshot[position++];
            }
        };
    }
}

Go through it in order.

• The array in items is never changed once built. Every change makes a new one.
• add copies the old array into one slot bigger, puts the new item in the extra slot, and then swaps items to point at the new array. The old array is left exactly as it was.
• iterator takes snapshot = items right away. That one line is the whole trick: the iterator keeps the array that existed when it was created, and nothing can ever change that array afterwards.
• So the iterator needs no version number and no check. It cannot be surprised.

TinyCopyOnWriteList<String> names = new TinyCopyOnWriteList<>();
names.add("Asha");
names.add("Ravi");
for (String name : names) {
    names.add(name + "!"); // safe: the loop is reading an older array
}
System.out.println(names.size());

4

The loop added a name for each name it read, and it didn't loop forever, because it only walked the two names that were there when it started.

The real ConcurrentHashMap takes a different route. It does not copy anything. It splits its buckets into small groups, locks only the group an update touches, and uses special instructions for the simplest changes, so different threads working on different keys rarely wait for one another.

The trade in one sentence: the copy-on-write list makes reading free and writing expensive, so it is for data that is read much more than it is written. A ConcurrentHashMap is the general choice when many threads share a map.

static void removeAllOf(List<Integer> numbers, int value) {
    throw new UnsupportedOperationException("remove every item equal to value, not the item at index value");
}

static void removeAllOf(List<Integer> numbers, int value) {
    // removeIf compares values. numbers.remove(value) would treat an int as an index.
    numbers.removeIf(n -> n == value);
}

static List<Integer> sortedDescending(List<Integer> numbers) {
    throw new UnsupportedOperationException("a new list, biggest first, safe for huge numbers");
}

static List<Integer> sortedDescending(List<Integer> numbers) {
    List<Integer> copy = new ArrayList<>(numbers); // leave the caller's list alone
    // Integer.compare(b, a), not b - a, which can overflow.
    Comparator<Integer> biggestFirst = (a, b) -> Integer.compare(b, a);
    copy.sort(biggestFirst);
    return copy;
}

static Map<String, Integer> countInThreads(List<List<String>> batches) {
    throw new UnsupportedOperationException("one thread per batch, one shared map, wait for all");
}

static Map<String, Integer> countInThreads(List<List<String>> batches) {
    Map<String, Integer> counts = new ConcurrentHashMap<>(); // safe for many threads at once
    List<Thread> threads = new ArrayList<>();
    for (List<String> batch : batches) {
        Thread thread = new Thread(() -> {
            for (String word : batch) {
                counts.merge(word, 1, Integer::sum);
            }
        });
        threads.add(thread);
        thread.start();
    }
    for (Thread thread : threads) {
        try {
            thread.join(); // do not read the map until every thread is done
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
            throw new IllegalStateException("interrupted while waiting", e);
        }
    }
    return counts;
}

• "Fail-fast versus fail-safe?" Fail-fast iterators (ArrayList, HashMap) throw ConcurrentModificationException if the collection changes during the loop. Fail-safe ones (CopyOnWriteArrayList, ConcurrentHashMap) never throw, because they read a snapshot or tolerate change. Add that fail-fast is best effort.
• "How does fail-fast work?" The collection counts its changes, and the iterator remembers the count it started with and compares it on each step. That was lesson 5's tiny list.
• "When would you use CopyOnWriteArrayList?" A list read very often and changed rarely, shared between threads. Writes copy the array, so they are O(n).
• "HashMap versus ConcurrentHashMap, and Hashtable?" HashMap is not safe for threads. ConcurrentHashMap is, and it is fast because it locks only part of the table. Hashtable is the old locked version: don't use it.
• "Why does ConcurrentHashMap refuse null?" A get that returns null could mean "no such key" or "the value is null", and with several threads you cannot check safely afterwards.
• "What is wrong with list.remove(i) on a List<Integer>?" An int picks the index version of remove. For the value, pass Integer.valueOf(x), or use removeIf.
• "== or equals for Integer?" equals. == compares identity and gives inconsistent answers for boxed numbers.
• "Why not a - b in a comparator?" It can overflow. Use Integer.compare.
• "Is subList a copy?" No. It is a window onto the original, so changes write through. Copy it if you need independence.
• Say the cost. "Fail-fast costs nothing but throws. Copy-on-write makes reads free and writes O(n). A concurrent hash map keeps lookups O(1) on average and lets many threads work at once."

Made by VeraStack Labs