The Collections framework

The Collections framework is where a Java interview spends the most time after strings and OOP, and where "it depends" is a real answer as long as you can say what it depends on.

The shape of it

              Iterable
                 │
             Collection                          Map  (NOT a Collection)
        ┌────────┼────────┐                       │
      List      Set     Queue              ┌──────┼──────────┐
        │        │        │             HashMap  TreeMap  LinkedHashMap
   ArrayList  HashSet  ArrayDeque          │
   LinkedList TreeSet  PriorityQueue    Hashtable (legacy)
   Vector     LinkedHashSet

Note that Map is not a Collection. It holds pairs, not elements, so it does not implement Iterable and has no iterator(). That is a real interview question, and the answer is: a Map is not a collection of single values, so the Collection contract does not fit. You iterate it via keySet(), values() or entrySet().

List — ordered, duplicates allowed, indexed

List<String> names = new ArrayList<>();
names.add("Raja");
names.add("Anu");
names.add(1, "Vik");              // insert at index
names.get(0);                     // Raja
names.set(0, "Ravi");             // replace
names.remove("Anu");              // by value
names.remove(0);                  // by index — the overload trap for List<Integer>
names.contains("Vik");            // O(n)
names.size();
names.indexOf("Vik");

That remove pair bites for a list of integers, and it is a favourite trick question:

List<Integer> xs = new ArrayList<>(List.of(10, 20, 30));
xs.remove(1);                     // removes INDEX 1 → [10, 30]
xs.remove(Integer.valueOf(20));   // removes the VALUE 20

remove(int) and remove(Object) are two overloads, and an int literal picks the index one.

ArrayList versus LinkedList

The honest answer, which is better than reciting the table: use ArrayList unless you have a specific reason not to. LinkedList's theoretical advantage for middle insertion is usually lost because you have to traverse to the position first, and its poor memory locality makes even iteration slower in practice. Its genuine use is as a deque — and ArrayDeque is better at that too.

"How does ArrayList grow?" — it holds an array with spare capacity. When add finds it full, it allocates a larger array (about 1.5× in current implementations), copies everything across, and continues. Any single add can therefore be O(n), but the cost spread over many adds is O(1) — that is what amortised means, and using the word correctly is worth a mark.

Vector is ArrayList with every method synchronized. It is legacy; the modern equivalent is Collections.synchronizedList(...) or CopyOnWriteArrayList.

Set — no duplicates

Set<String> tags = new HashSet<>();
tags.add("cse");
tags.add("cse");                  // ignored, returns false
System.out.println(tags.size());  // 1

Set<Integer> sorted = new TreeSet<>(List.of(5, 1, 3));
System.out.println(sorted);                 // [1, 3, 5]
System.out.println(((TreeSet<Integer>) sorted).first());   // 1

TreeSet requires its elements to be comparable — either they implement Comparable, or you pass a Comparator to the constructor. Otherwise you get a ClassCastException at run time, not a compile error.

Set membership is O(1) on a HashSet and O(n) on a List. That single fact fixes more timeouts than any other in this lesson:

// O(n²)
for (String x : all) {
    if (blocked.contains(x)) { }        // blocked is a List
}

// O(n)
Set<String> blockedSet = new HashSet<>(blocked);
for (String x : all) {
    if (blockedSet.contains(x)) { }
}

Map — key to value

Map<String, Integer> marks = new HashMap<>();
marks.put("raja", 87);
marks.put("raja", 90);                  // replaces; returns the old value
marks.get("anu");                       // null
marks.getOrDefault("anu", 0);           // 0
marks.containsKey("raja");
marks.putIfAbsent("anu", 70);
marks.merge("raja", 1, Integer::sum);   // 91 — add to the existing value
marks.computeIfAbsent("vik", k -> 0);
marks.remove("raja");

for (Map.Entry<String, Integer> e : marks.entrySet()) {
    System.out.println(e.getKey() + " " + e.getValue());
}

merge and computeIfAbsent are the counting and grouping idioms — worth knowing, because they replace three lines of containsKey each time:

Map<Character, Integer> freq = new HashMap<>();
for (char c : "placement".toCharArray()) {
    freq.merge(c, 1, Integer::sum);
}

Map<String, List<String>> byBranch = new HashMap<>();
byBranch.computeIfAbsent("CSE", k -> new ArrayList<>()).add("raja");

HashMap allows one null key and many null values; Hashtable and ConcurrentHashMap allow neither. That comparison is asked directly.

How HashMap works internally

This is the deep question in this lesson, and a clear answer is memorable:

1. hashCode() is called on the key to get an int.
2. The hash is spread — h ^ (h >>> 16) — so that high bits influence the low ones, because the next step only uses the low bits.
3. The bucket index is computed as hash & (capacity - 1). Capacity is always a power of two, which makes this a bitmask instead of a modulo.
4. If that bucket is empty, the entry goes in.
5. If it is not, that is a collision. The entry joins the bucket's chain, comparing with equals() against each existing key — an equal key means replace the value, otherwise append.
6. When the map is more than 0.75 full (the default load factor) it resizes: capacity doubles and every entry is rehashed into the new table.
7. Since Java 8, a bucket whose chain exceeds 8 entries converts to a red-black tree, so the worst case degrades to O(log n) rather than O(n).

Default capacity is 16, default load factor 0.75, so the first resize happens at the 13th entry.

The consequence you must be able to state: lookup is O(1) on average and O(log n) in the worst case since Java 8 (it was O(n) before). And if hashCode() returns the same value for every key, every entry lands in one bucket and the map degenerates — which is why the next lesson on equals/hashCode matters so much.

Queue and Deque

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);  stack.push(2);
stack.pop();                         // 2 — LIFO

Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1); queue.offer(2);
queue.poll();                        // 1 — FIFO

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.addAll(List.of(5, 1, 3));
minHeap.poll();                      // 1 — always the smallest

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

Use ArrayDeque for both stacks and queues. The legacy Stack class extends Vector, is synchronised, and iterates in the wrong order — every style guide says avoid it.

PriorityQueue is a binary min-heap: offer and poll are O(log n), peek is O(1). It is not sorted when you iterate it — only poll order is meaningful. Printing a PriorityQueue and expecting sorted output is a common mistake.

Fail-fast iterators

Modifying a collection while iterating it throws:

List<String> names = new ArrayList<>(List.of("a", "b", "c"));
for (String n : names) {
    if (n.equals("b")) names.remove(n);      // ConcurrentModificationException
}

The collection keeps a modification counter; the iterator remembers its value and checks it on every next(). A mismatch means someone changed the structure behind the iterator's back, and it fails immediately rather than producing quietly wrong results. That is what fail-fast means, and the name is worth using.

Three correct ways:

names.removeIf(n -> n.equals("b"));                 // best — Java 8+

Iterator<String> it = names.iterator();
while (it.hasNext()) {
    if (it.next().equals("b")) it.remove();         // the iterator's own remove is allowed
}

for (String n : new ArrayList<>(names)) {           // iterate a copy
    if (n.equals("b")) names.remove(n);
}

CopyOnWriteArrayList is fail-safe instead: it iterates a snapshot, so it never throws — at the cost of copying the array on every write.

Choosing, in one table

What to take into an interview

• Map is not a Collection; iterate it through entrySet().
• ArrayList for almost everything. LinkedList only for front-end operations, and ArrayDeque is usually better.
• ArrayList grows by allocating a bigger array and copying — amortised O(1).
• remove(int) is by index, remove(Object) by value.
• HashMap: hash, spread, mask to a bucket, chain on collision, resize at 0.75 load factor, treeify a bucket past 8 entries. O(1) average, O(log n) worst case since Java 8.
• HashMap allows one null key; Hashtable and ConcurrentHashMap allow none.
• HashSet membership is O(1); List membership is O(n).
• Structural modification during iteration is fail-fast with ConcurrentModificationException; use removeIf or Iterator.remove.
• PriorityQueue is a heap, not a sorted list.