Java Interview Cheat Sheet — Collections, Streams, and the Gotchas That Bite Candidates

Bookmark this page. This is the Java equivalent of the Python interview cheat sheet — the Collections framework, Streams idioms, and language gotchas (HashMap's tree-bucket fallback, LinkedList's O(n) get, StringBuilder over String +=) that show up in coding interviews. Complements the Big-O cheat sheet; this one is about how to write it in Java, not how fast it runs.

Collections at a glance

Interface	Concrete class	Ordered?	Nulls allowed?	Notes
`List<E>`	`ArrayList<E>`	Insertion	✓	The default. O(1) access.
`List<E>`	`LinkedList<E>`	Insertion	✓	O(n) access — almost never worth it
`Set<E>`	`HashSet<E>`	No	✓ (one)	O(1)* ops
`Set<E>`	`LinkedHashSet<E>`	Insertion	✓ (one)	O(1)* ops, retains order
`Set<E>`	`TreeSet<E>`	Sorted	✗	O(log n) ops, in-order iteration
`Map<K,V>`	`HashMap<K,V>`	No	✓ (one key, many values)	O(1)* ops
`Map<K,V>`	`LinkedHashMap<K,V>`	Insertion or access	✓	LRU cache with `accessOrder=true`
`Map<K,V>`	`TreeMap<K,V>`	Sorted by key	✗ (key)	O(log n) ops, `floorKey`, `ceilingKey`
`Deque<E>`	`ArrayDeque<E>`	Insertion	✗	O(1) both ends. Use for stack + queue.
`Queue<E>`	`PriorityQueue<E>`	Priority	✗	O(log n) add/poll, O(1) peek

*Amortised — see the worst-case caveats in the time-complexity-of-common-operations post.

`HashMap` — the interview power tool

Map<String, Integer> map = new HashMap<>();

map.put("a", 1);                     // O(1)*
map.get("a");                        // O(1)*   returns null if absent
map.getOrDefault("z", 0);            // O(1)*   idiomatic for "0 if missing"
map.putIfAbsent("b", 2);             // O(1)*
map.remove("a");                     // O(1)*
map.containsKey("a");                // O(1)*
map.size();                          // O(1)
map.isEmpty();                       // O(1)

// Iteration
for (Map.Entry<String, Integer> e : map.entrySet()) {
    e.getKey(); e.getValue();
}
for (String k : map.keySet()) { ... }
for (Integer v : map.values()) { ... }

Post-Java-8 tree-bucket fallback. When a single bucket exceeds TREEIFY_THRESHOLD = 8 entries (and the map has ≥ 64 buckets), the bucket converts from a linked list to a red-black tree. Worst-case per bucket becomes O(log n) instead of O(n). Interviewers rarely test this directly, but naming it earns credit when they push on hash-map worst cases.

merge and compute for frequency counts.

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

Same result as putIfAbsent + put, in one call. merge(key, initialValue, remappingFunction) sets the value to initialValue if the key is absent, otherwise runs the function.

computeIfAbsent for grouped collections.

Map<String, List<Integer>> groups = new HashMap<>();
groups.computeIfAbsent(key, k -> new ArrayList<>()).add(value);

Idiomatic replacement for the if (!map.containsKey(k)) map.put(k, ...); map.get(k).add(...) verbosity.

`ArrayList` — the default list

List<Integer> list = new ArrayList<>();
list.add(1);              // O(1)*
list.add(0, 42);          // O(n) — inserting at start
list.get(i);              // O(1)
list.set(i, 99);          // O(1)
list.remove(i);           // O(n) — everything after shifts
list.contains(x);         // O(n)
list.indexOf(x);          // O(n)
list.size();              // O(1)

// Iteration
for (int x : list) { ... }

// Sort
Collections.sort(list);                              // Timsort, O(n log n)
Collections.sort(list, Comparator.reverseOrder());   // Descending
list.sort(Comparator.comparingInt(x -> x % 10));     // Custom key

// Convert to array
int[] arr = list.stream().mapToInt(Integer::intValue).toArray();

Prefer ArrayList over LinkedList except when the problem hands you a linked list or specifically needs O(1) mid-list splicing with many operations. See the array vs linked list post.

`ArrayDeque` — stack and queue

Modern Java's answer to both Stack (which is synchronised and slow) and LinkedList (which is cache-hostile).

Deque<Integer> stack = new ArrayDeque<>();
stack.push(x);      // add to head — O(1)
stack.pop();        // remove from head — O(1)
stack.peek();       // look at head — O(1)

Deque<Integer> queue = new ArrayDeque<>();
queue.offer(x);     // add to tail — O(1)
queue.poll();       // remove from head — O(1)
queue.peek();       // look at head — O(1)

Same underlying data structure, different methods to reveal the intended semantics. See the stack vs queue post for when each shape wins.

`PriorityQueue` — the heap

Min-heap by default. For max-heap, pass a reversed comparator.

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(3);         // O(log n)
minHeap.poll();           // O(log n)  returns smallest
minHeap.peek();           // O(1)      look at smallest

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

// Custom comparator — heap by string length
PriorityQueue<String> pq = new PriorityQueue<>(Comparator.comparingInt(String::length));

// Heap of tuples via custom comparator or record
record Node(int priority, int id) {}
PriorityQueue<Node> pq2 = new PriorityQueue<>(Comparator.comparingInt(Node::priority));

Java's PriorityQueue does not support decrease-key in O(log n). For Dijkstra, push a new entry with the improved priority and skip stale entries on poll — the standard interview implementation.

`TreeMap` and `TreeSet` — sorted structures

Red-black trees. All ops O(log n).

TreeMap<Integer, String> tm = new TreeMap<>();
tm.put(3, "c");                    // O(log n)
tm.firstKey();                     // O(log n)
tm.lastKey();                      // O(log n)
tm.floorKey(5);                    // greatest key ≤ 5
tm.ceilingKey(5);                  // least key ≥ 5
tm.higherKey(5);                   // strictly greater
tm.lowerKey(5);                    // strictly smaller
tm.subMap(2, 7);                   // view of keys in [2, 7)

Interview uses: sliding window with nearest-neighbour queries (LC 220), interval scheduling with active-set tracking, running median (though two PriorityQueues are cleaner for that).

`String` and `StringBuilder`

String s = "Hello";
s.length();                        // O(1)
s.charAt(i);                       // O(1)
s.substring(a, b);                 // O(b - a) — post-Java-7 copies
s.indexOf("x");                    // O(n · m)
s.toCharArray();                   // O(n) — often the fastest way to iterate chars
Character.isDigit(c);              // O(1)
Character.isLetterOrDigit(c);      // O(1)
Character.toLowerCase(c);          // O(1)

The building rule. String is immutable. Never build a string by repeated +=:

// DON'T — O(n²)
String result = "";
for (String s : chunks) result += s;

// DO — O(n) via StringBuilder
StringBuilder sb = new StringBuilder();
for (String s : chunks) sb.append(s);
String result = sb.toString();

StringBuilder.append is amortised O(1). Every interview involving string building should reach for it.

`Streams` — quick reference

List<Integer> nums = List.of(1, 2, 3, 4, 5);

int sum = nums.stream().mapToInt(Integer::intValue).sum();
int max = nums.stream().mapToInt(Integer::intValue).max().getAsInt();
List<Integer> doubled = nums.stream().map(x -> x * 2).toList();
List<Integer> evens = nums.stream().filter(x -> x % 2 == 0).toList();
long count = nums.stream().filter(x -> x > 2).count();

// Sort
List<Integer> sorted = nums.stream().sorted().toList();
List<Integer> desc = nums.stream().sorted(Comparator.reverseOrder()).toList();

// Group by
Map<Integer, List<String>> byLen = words.stream()
    .collect(Collectors.groupingBy(String::length));

// Count by
Map<Integer, Long> counts = words.stream()
    .collect(Collectors.groupingBy(String::length, Collectors.counting()));

Streams read well and are usually not the interview-preferred style — imperative for loops are more concrete on a whiteboard and easier for interviewers to follow. But knowing streams earns credit on "can you write more idiomatic Java?" follow-ups.

Common patterns

Frequency count with `merge`

Map<Character, Integer> counts = new HashMap<>();
for (char c : s.toCharArray()) counts.merge(c, 1, Integer::sum);

Group by key

Map<String, List<String>> groups = new HashMap<>();
for (String word : words) {
    String key = sortedChars(word);
    groups.computeIfAbsent(key, k -> new ArrayList<>()).add(word);
}

Two-sum with hash map

Map<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
    Integer j = seen.get(target - nums[i]);
    if (j != null) return new int[]{j, i};
    seen.put(nums[i], i);
}

Top-k with a size-k min-heap

PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int x : nums) {
    heap.offer(x);
    if (heap.size() > k) heap.poll();
}
// heap contains the k largest, minimum on top

BFS with `ArrayDeque`

Deque<int[]> queue = new ArrayDeque<>();
queue.offer(new int[]{startRow, startCol});
Set<Integer> visited = new HashSet<>();
visited.add(startRow * cols + startCol);

while (!queue.isEmpty()) {
    int[] pos = queue.poll();
    for (int[] d : DIRS) {
        int nr = pos[0] + d[0], nc = pos[1] + d[1];
        int key = nr * cols + nc;
        if (0 <= nr && nr < rows && 0 <= nc && nc < cols && !visited.contains(key)) {
            visited.add(key);
            queue.offer(new int[]{nr, nc});
        }
    }
}

Gotchas — the traps

`Integer` boxing and equality

Integer a = 127;
Integer b = 127;
Integer c = 128;
Integer d = 128;
a == b;       // TRUE — cached (-128..127)
c == d;       // FALSE — separate boxed objects
c.equals(d);  // TRUE — value equality

Always use .equals() for boxed types. == compares references.

`Arrays.sort` worst-case

Arrays.sort(int[]) uses dual-pivot Quicksort — O(n²) worst case on adversarial inputs. Arrays.sort(Object[]) and Collections.sort(List) use Timsort — O(n log n) guaranteed. If worst-case matters, box to Integer[].

`HashMap.get` on primitive vs boxed

HashMap<Integer, Integer> is fine, but .get(key) returns Integer (nullable), not int. Auto-unboxing a null throws NPE. Use getOrDefault when a missing key should return a value, or check for null explicitly.

`List.of` and `Map.of` are immutable

List<Integer> nums = List.of(1, 2, 3);
nums.add(4);   // UnsupportedOperationException

For a mutable list from a fixed set, use new ArrayList<>(List.of(1, 2, 3)).

`for-each` over an int array vs Integer array

int[] intArr = {1, 2, 3};
Integer[] boxedArr = {1, 2, 3};

for (int x : intArr) { ... }        // fine, no boxing
for (Integer x : boxedArr) { ... }  // boxed — allocates per iteration if you're unlucky

For performance-sensitive interview code, prefer int[] over Integer[].

Map<String, List<Integer>> map = new HashMap<>();     // classic
var map = new HashMap<String, List<Integer>>();       // Java 10+

Interviewers accept both. var is fine for locals; explicit types are still required for fields and method signatures.

Complexity quick reference

Same underlying bounds as every other language for hash and tree operations; see the Big-O cheat sheet and the time-complexity-of-common-operations post for the exhaustive per-language table.

The patterns this cheat sheet backs

Every pattern post's Java translation cashes in on the primitives above:

Sliding window — HashMap<Character, Integer> with merge(c, 1, Integer::sum) for the window count.
Two-pointer — int[] with Arrays.sort (know the O(n²) worst case!).
Binary search — plain while loop; the boundary template ports one-to-one.
Monotonic stack — ArrayDeque<Integer> with push / pop / peek.
Backtracking — List<Integer> current with current.add(x) / current.remove(current.size() - 1). Snapshot with new ArrayList<>(current).
BFS vs DFS — ArrayDeque<int[]> for BFS; recursion for DFS. Never LinkedList.
Union-find — int[] parent and int[] rank, both O(1) access.
Topological sort — HashMap<Integer, List<Integer>> for the adjacency list, ArrayDeque<Integer> for Kahn's queue.

The idioms above aren't decoration. They're the interview-preferred spelling for each pattern.