Java: Collections and Recursion

Description

Almost every Java answer in a coding interview leans on the same few containers: a list to keep things in order, a map to look things up, a set to remember what you've already seen, and a queue to decide what comes next. You've probably used all of them. This lesson is about using them with confidence: picking the right one quickly, and knowing the handful of Java rules that quietly break code that looks perfectly fine.

Here's the kind of bug we mean. You count the words in a document, then check whether two words show up equally often:

Map<String, Integer> counts = new HashMap<>();
for (String w : words) counts.merge(w, 1, Integer::sum);   // add 1 to w's count
boolean same = counts.get(a) == counts.get(b);

Every test you write passes. Then a real document arrives where both words appear 200 times, and same comes back false. The counting is right. What trips it up is a Java rule about how collections store numbers, and by the middle of this lesson you'll know exactly which one.

We'll start simple and get more technical as we go:

1. Which collection to pick, and what each one costs.
2. How a HashMap finds things, and why its order looks random.
3. Why numbers inside collections behave differently (the bug above).
4. Sorting things your own way, and the PriorityQueue.
5. Stacks, queues, and changing a collection while you loop over it.
6. How deep recursion can go before Java runs out of room.

Picking the right collection

Each collection is a different kind of storage, and each one is good at one job:

• A list is a numbered shelf. Things stay in the order you put them, and you can grab item 7 directly.
• A set is a guest list. Each name appears once, and the question it answers fast is "is this person on it?"
• A map is a phone book. You look up a value (a number) by its key (a name).
• A queue is the line at a coffee shop: first in, first out. A stack is a pile of plates: the last one you put on is the first one you take off.
• A priority queue is a hospital triage desk. Whoever is most urgent goes next, no matter when they arrived.

When you're not sure which one you need, walk through these questions:

Interviewers also expect you to know roughly what each operation costs. The notation is simple once you've seen it: O(1) means the time stays the same however big the collection gets, O(log n) means it grows very slowly (about 20 steps for a million items), and O(n) means it may have to walk past every item.

One cost catches people out: list.remove(0) on an ArrayList shifts every other item down a place, so it's O(n). Using an ArrayList as a queue turns a fast algorithm into a slow one. Use an ArrayDeque instead.

How a HashMap finds things

When you call put("austin", 3), the map asks the key for its hashCode(), a number worked out from the key's contents. That number picks a slot in an internal array. The slots are called buckets. Later, get("austin") works out the same number, goes straight to the same bucket, and uses equals() to pick the right entry in case a few keys landed there together. There's no searching through the whole map, which is why lookups are so fast.

Two practical rules follow from this.

A HashMap doesn't keep any order. Looping over it walks the buckets, so the order looks random and can even change as the map grows. It's sneaky with small positive Integer keys: their hash code is the number itself, so they often come out looking sorted, until a negative key shows up and the "sorted" output falls apart. When order matters, say so with the type: LinkedHashMap keeps the order you added things, and TreeMap keeps keys sorted.

Never change a key after you put it in a map. The entry sits in the bucket picked by the key's old hash code. Change a field that the hash code depends on, and the map looks in the wrong bucket: neither the changed key nor a fresh copy of the old one can find the entry again. Use keys that can't change, like String, Integer or a record with final fields.

TreeMap is the one to reach for when you need "nearest" answers. Picture a calendar of booked appointments, where you ask "what's the latest booking at or before 6pm?":

TreeMap<Integer, String> bookings = new TreeMap<>(Map.of(2, "b", 6, "f", 9, "i"));
bookings.floorKey(6);      // 6: the largest key <= 6
bookings.lowerKey(6);      // 2: the largest key < 6
bookings.ceilingKey(7);    // 9: the smallest key >= 7
bookings.higherKey(9);     // null: nothing is bigger than 9

The "or equal" versions are floor and ceiling; the strict ones are lower and higher.

Numbers inside collections

Collections can't hold a plain int, only objects. So Java quietly wraps each int in an Integer object on the way in (autoboxing) and unwraps it on the way out (unboxing). You rarely notice, except in three places.

1. == compares the objects, not the numbers. For objects, == asks "are these the very same object?" Java keeps one shared Integer object for each value from -128 to 127 and reuses it, so small equal numbers happen to be the same object. From 128 up, each boxing makes a new object:

Integer a = 127, b = 127, c = 128, d = 128;
a == b;          // true: both point at the one shared 127
c == d;          // false: two different objects that both hold 128
c.equals(d);     // true: same number

That's the bug from the start of the lesson. With counts below 128, counts.get(a) == counts.get(b) compared two shared objects and worked. At 200 it compared two different objects. The fix is counts.get(a).equals(counts.get(b)), or storing the counts in int variables before comparing them.

2. A missing key gives you null. get returns null when a key isn't in the map, and unboxing null throws a NullPointerException:

counts.put(w, counts.get(w) + 1);            // NullPointerException the first time w appears
counts.merge(w, 1, Integer::sum);            // works: starts at 1, then adds 1 each time
counts.put(w, counts.getOrDefault(w, 0) + 1);   // also works

3. remove(1) on a list of numbers removes position 1. A List has two remove methods, one taking a position and one taking an object. A plain 1 is an int, so Java picks the position:

List<Integer> ids = new ArrayList<>(List.of(10, 20, 30));
ids.remove(1);                   // removes the item at index 1, so ids is [10, 30]
ids.remove(Integer.valueOf(10)); // removes the value 10, so ids is [30]

Sorting your own way: comparators

A comparator answers one question about two items: which one comes first? It returns a negative number if the first item goes first, a positive number if the second does, and zero for a tie. Only the sign matters, not the size.

That makes subtraction tempting, and it's a trap:

(x, y) -> x[1] - y[1]                       // looks neat, breaks on big numbers
(x, y) -> Integer.compare(x[1], y[1])       // always right

An int can only hold values up to about 2.1 billion. Past that, the result wraps around to a negative number, which is called overflow. So 2147483647 - (-2147483647) doesn't give a big positive number; it wraps to -2, and the sort puts those two items the wrong way round. Small test data never hits this, which is exactly why it slips into interviews. Integer.compare never overflows.

For anything with more than one sort key, build the comparator from pieces:

record Task(int priority, String name) {}

Comparator.comparingInt(Task::priority).thenComparing(Task::name)
// priority low to high, then name A to Z

Comparator.comparingInt(Task::priority).reversed().thenComparing(Task::name)
// priority high to low, then name A to Z: [2a, 2c, 1a, 1b]

Comparator.comparingInt(Task::priority).thenComparing(Task::name).reversed()
// reverses BOTH: [2c, 2a, 1b, 1a]

reversed() flips everything built before it, so put it right after the key you want reversed.

One limit: comparators only work on objects. Arrays.sort(scores, Collections.reverseOrder()) doesn't compile when scores is an int[]. Sort it normally and read it from the end, or copy it into an Integer[] first.

PriorityQueue: the most urgent item first

A PriorityQueue always hands you its smallest item: peek() looks at it and poll() takes it out. For "largest first", give it a reversed comparator: new PriorityQueue<>(Comparator.reverseOrder()).

Inside, it's a heap: an array kept just organized enough that the smallest item is always at the front. Everything behind the front is only partly ordered, which leads to three surprises:

• Printing it doesn't show sorted order. new PriorityQueue<>(List.of(5, 1, 4, 2, 3)) prints [1, 2, 4, 5, 3]. Only the first item is guaranteed. To see everything in order, poll() until it's empty.
• Ties come out in no particular order. If two tasks have the same priority and their order matters, add a tie-breaker, such as the order they arrived in.
• You can't update an item's priority in place. Changing a field of an item already inside breaks the heap, and remove(item) is slow (O(n)).

The standard workaround shows up in Dijkstra's shortest-path algorithm. When a node gets a better distance, push a new entry and ignore the old one when it comes out:

while (!pq.isEmpty()) {
    int[] top = pq.poll();                    // {node, distance}
    if (top[1] > dist[top[0]]) continue;      // an outdated entry: skip it
    // ... visit top[0] ...
}

Stacks and queues: use ArrayDeque

ArrayDeque is both your stack and your queue. As a stack, use push, pop and peek. As a queue, use offer to add at the back and poll to take from the front.

You'll see java.util.Stack in older code, but skip it. It's built on the old Vector class, it locks on every single call, and it lets you reach into the middle with get(i), which a stack shouldn't allow. Even its own documentation recommends Deque instead.

One difference worth remembering: on an empty deque, pop() throws an exception while poll() returns null.

Changing a collection while you loop over it

Say an app in Austin sends order updates to a list of listeners, and a listener unsubscribes itself as soon as it gets a message:

for (Listener l : listeners) {
    l.onEvent(e);           // this listener removes itself from listeners...
}                           // ...and the loop throws ConcurrentModificationException

A for-each loop runs on an iterator, and the iterator notices the list changed behind its back. Here are three safe ways to do it:

for (Listener l : new ArrayList<>(listeners)) l.onEvent(e);   // loop over a copy

listeners.removeIf(Listener::isClosed);                       // let the list do the removing

Iterator<Listener> it = listeners.iterator();                 // remove through the iterator
while (it.hasNext()) if (it.next().isClosed()) it.remove();

Don't count on the exception, though. If you remove the second-to-last item, the loop simply ends early, skipping the last item without any error. The check is a best effort.

A related surprise: Arrays.asList(1, 2, 3) gives you a fixed-size list. You can set items, but add and remove throw UnsupportedOperationException. Wrap it in new ArrayList<>(...) when you need to grow it. List.of(...) is stricter still: you can't change it at all.

An LRU cache in six lines

An LRU cache (least recently used) has a fixed size. When it's full, it throws out the item nobody has touched for the longest. It's a classic interview question, and Java's LinkedHashMap can almost do it for you:

class Lru<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    Lru(int capacity) { super(16, 0.75f, true); this.capacity = capacity; }    // true: order by last access
    @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;                                               // checked after every put
    }
}

The true makes every get move that entry to the end, so the front is always the least recently used. Without it, the map keeps insertion order and you get a FIFO cache instead. Most interviewers want you to build the hash map and linked list by hand, but saying "this is exactly what LinkedHashMap does" shows you know the library.

One trap: in an access-ordered LinkedHashMap, get changes the map (it moves the entry), so for (K k : map.keySet()) map.get(k) throws ConcurrentModificationException. Loop over entrySet() instead.

How deep can recursion go?

Each method call gets a small block of memory, called a frame, for its parameters and local variables. Frames sit on the thread's stack, which has a fixed size: typically 1 to 2 MB, depending on the platform. When recursion goes too deep, the stack fills up and Java throws StackOverflowError.

For a small method that's usually somewhere in the tens of thousands of calls. In this course's sandbox, a one-line recursive method got about 35,000 calls deep. So a depth-first search over a graph shaped like a long chain of 100,000 nodes will crash, even though the algorithm is correct.

Java also never turns tail calls into loops. Rewriting sum(n) as sum(n - 1, total + n) doesn't save any stack, unlike in some other languages.

The fix that works everywhere is to keep your own stack in an ArrayDeque:

Deque<Integer> stack = new ArrayDeque<>();
boolean[] seen = new boolean[n];
stack.push(start);
while (!stack.isEmpty()) {
    int node = stack.pop();
    if (seen[node]) continue;
    seen[node] = true;
    for (int next : graph.get(node)) if (!seen[next]) stack.push(next);
}

Competitive programmers sometimes run the recursion on a new thread created with a bigger stack instead: new Thread(null, task, "solver", 1L << 29) asks for 512 MB. That works, but in production code and in interviews, the loop is the answer people want to hear. And catching StackOverflowError is never a fix: the work is lost, and your data may be half updated.

Common mistakes

Check yourself

Try to answer before opening each one. Recalling beats re-reading.

1. Why does counts.get(a) == counts.get(b) work for counts of 127 but fail for 128?

2. You need the first booking at or after 3pm, from bookings stored by time. Which collection and method?

3. In Dijkstra's algorithm, a node already in the PriorityQueue gets a shorter distance. What do you do?

4. Which LinkedHashMap setting turns it into an LRU cache, and what else do you need?

Key takeaways

• Pick the collection by the job: HashMap to look up, TreeMap for sorted or nearest keys, ArrayDeque for stacks and queues, PriorityQueue for smallest first.
• A HashMap has no order. Ask for one with LinkedHashMap or TreeMap.
• Numbers in collections are objects: compare with equals, count with merge, and remove values with Integer.valueOf.
• Comparators use Integer.compare, never subtraction, and reversed() goes right after the key it's meant for.
• A PriorityQueue only promises its first item.
• Don't change a collection inside its own for-each loop.
• Deep recursion needs a loop with your own stack.