Java Toolkit & Collections

9 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

1. ◆what it is

   The Collections Framework = interfaces (List, Deque, Set, Map) + ready-made data structures behind them. Pick by the operation you need most.

   #1
2. ↯use it when

   Stack/queue → ArrayDeque. Seen it? Count? → HashSet/HashMap. Sorted or nearest key → TreeMap. Next smallest → PriorityQueue. Indexed list → ArrayList.

   #2
3. O( )cost

   HashMap O(1) avg · TreeMap O(log n) · PriorityQueue offer/poll O(log n), peek O(1) · ArrayList get O(1), add amortized O(1), remove(0) O(n).

   #3
4. O( )cost

   ArrayList grows by 1.5× (old + (old >> 1)): 10 lakh adds = only 30 grows (the first 10 slots, then 29 × 1.5), ~2.4 copies per add. Rare O(n) copies → amortized O(1).

   #4
5. { }template

   map.merge(w, 1, Integer::sum); counts. map.computeIfAbsent(k, x -> new ArrayList<>()).add(v); groups.

   #5
6. { }template

   Max-heap: new PriorityQueue<>(Collections.reverseOrder()). Pairs: new PriorityQueue<int[]>((a, b) -> Integer.compare(a[0], b[0])).

   #6
7. !trap

   Integer == compares references: true for −128..127 (the cache), false for 128 on a default JVM. Use equals, or unbox to int.

   #7
8. !trap

   int c = map.get(k) on a missing key → NullPointerException. (a, b) -> a - b overflows. Use getOrDefault and Integer.compare.

   #8
9. ✦pro tip

   Declare by interface: Deque<Integer> st = new ArrayDeque<>();. Then say why out loud: "ArrayDeque, O(1) at both ends."

   #9

Shaky on a card? Open the chapter or flip its recall cards.