Java Collections for DSA Interviews: The Cheat Sheet and the Pitfalls

Java is the most common interview language in Indian product-company rounds after C++ and Python, and it is a fine choice: the Collections Framework has everything a DSA problem needs. What trips people up is not missing features but Java's specific semantics: boxing, reference equality, overloaded methods and comparator contracts. This page covers the APIs you need, with every snippet compiled and run on JDK 17, and then the pitfalls that turn correct algorithms into failed test cases.

Writing C++ instead? Read the C++ STL cheat sheet. Still deciding? See Java vs Python vs C++ for DSA.

Which Java Collection to Use When

Arrays, the Arrays Class and ArrayList

int[] arr = {5, 3, 8, 1};
Arrays.sort(arr);                              // [1, 3, 5, 8], ascending only
int idx = Arrays.binarySearch(arr, 5);         // 2 (negative if absent)
Arrays.fill(arr, -1);
int[][] grid = new int[3][4];                  // all zeros
for (int[] row : grid) Arrays.fill(row, -1);   // fill is 1-D only
System.out.println(Arrays.toString(arr));      // printing arrays
System.out.println(Arrays.deepToString(grid));

// sort 2-D array (intervals) by start
int[][] intervals = {{5, 6}, {1, 3}, {2, 4}};
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

// descending sort needs boxed types
Integer[] boxed = {5, 3, 8, 1};
Arrays.sort(boxed, Collections.reverseOrder());

List<Integer> list = new ArrayList<>(List.of(5, 3, 8, 1));
Collections.sort(list);
list.add(7); list.get(0); list.set(0, 9); list.size();
list.remove(Integer.valueOf(8));   // remove by VALUE
list.remove(0);                    // remove by INDEX

// adjacency list for a graph with n nodes
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
adj.get(u).add(v);

Facts worth knowing: Arrays.sort on primitives uses a dual-pivot quicksort (not stable, which does not matter for primitives); on objects it uses TimSort (stable, O(n log n) worst case). You cannot pass a comparator to sort an int[]; box it to Integer[], or sort ascending and read it backwards. On some older JDKs, adversarial inputs could push the primitive quicksort towards quadratic time, which is why competitive programmers sometimes shuffle before sorting; for interviews this never matters.

Two fixed-size traps: Arrays.asList(...) returns a fixed-size list backed by the array (you can set but add throws UnsupportedOperationException), and List.of(...) is fully immutable. Wrap either in new ArrayList<>(...) if you need to modify it.

HashMap and HashSet: The Modern API

Most Java DSA code is longer than it needs to be because people write if (map.containsKey(k)) ... else ... blocks. Java 8 added methods that collapse those patterns into one line.

Map<String, Integer> freq = new HashMap<>();
for (String w : words) freq.merge(w, 1, Integer::sum);          // frequency count
int c = freq.getOrDefault("z", 0);                              // 0 if absent
Integer maybe = freq.get("z");                                  // null if absent!

Map<Integer, List<Integer>> graph = new HashMap<>();
graph.computeIfAbsent(u, k -> new ArrayList<>()).add(v);        // group / adjacency

for (Map.Entry<String, Integer> e : freq.entrySet()) {          // iterate pairs
    String key = e.getKey();
    int count = e.getValue();
}
freq.entrySet().removeIf(e -> e.getValue() == 1);              // safe bulk removal

Set<Integer> seen = new HashSet<>();
if (!seen.add(x)) { /* x was already present: add returns false */ }

A merge remapping function that returns null removes the key, which is handy for "decrement and delete at zero" in sliding-window problems:

window.merge(ch, -1, (oldV, delta) -> oldV + delta == 0 ? null : oldV + delta);

HashMap iteration order is unspecified; never rely on it in output. If you need insertion order, use LinkedHashMap. For the problems these maps solve, see the hashing interview problems guide.

TreeMap and TreeSet: Navigation Methods

TreeMap is Java's most underused interview weapon. It is a red-black tree with O(log n) operations and a set of navigation methods that solve "nearest value" problems in one call.

TreeMap<Integer, String> tm = new TreeMap<>();
tm.put(10, "a"); tm.put(20, "b"); tm.put(30, "c");

tm.floorKey(25);     // 20   greatest key <= 25
tm.ceilingKey(25);   // 30   smallest key >= 25
tm.lowerKey(10);     // null greatest key < 10
tm.higherKey(30);    // null smallest key > 30
tm.firstKey(); tm.lastKey(); tm.lastEntry().getValue();
tm.headMap(20);          // {10=a}            keys < 20
tm.tailMap(20, true);    // {20=b, 30=c}      keys >= 20
tm.subMap(10, 30);       // {10=a, 20=b}      [10, 30)
tm.pollFirstEntry();     // removes and returns 10=a

TreeSet<Integer> ts = new TreeSet<>(List.of(10, 20, 30));
ts.floor(15); ts.ceiling(15); ts.first(); ts.last(); ts.pollFirst();

Note that the navigation methods return null when nothing qualifies, so unboxing them into an int without a check throws NullPointerException. Also note firstKey() throws NoSuchElementException on an empty map while firstEntry() returns null.

TreeMap as a multiset

Java has no built-in multiset. Use TreeMap<Integer, Integer> of value to count, removing the key when its count hits zero. This is how you solve Sliding Window Median, Hand of Straights or "maximum minus minimum in a window" in Java:

TreeMap<Integer, Integer> ms = new TreeMap<>();
void add(int x)    { ms.merge(x, 1, Integer::sum); }
void remove(int x) { ms.merge(x, -1, (a, b) -> a + b == 0 ? null : a + b); }
int min() { return ms.firstKey(); }
int max() { return ms.lastKey(); }

Typical TreeMap problems: My Calendar I (check floorKey and ceilingKey for overlap), Time Based Key-Value Store (floorEntry on timestamps), Contains Duplicate III (ceiling within a window), and the skyline problem.

PriorityQueue: Min-Heap, Max-Heap and Custom Order

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
minHeap.offer(4); minHeap.peek(); minHeap.poll(); minHeap.size();

// int[] entries ordered by the second element (e.g. {node, dist})
PriorityQueue<int[]> pq = new PriorityQueue<>((p, q) -> Integer.compare(p[1], q[1]));

// long distances: compare with comparingLong
PriorityQueue<long[]> lpq = new PriorityQueue<>(Comparator.comparingLong(x -> x[0]));

// objects: higher priority first, then name alphabetical
record Task(int priority, String name) {}
PriorityQueue<Task> tasks = new PriorityQueue<>(
    Comparator.comparingInt(Task::priority).reversed().thenComparing(Task::name));

Things interviewers check:

• offer/poll are O(log n), peek is O(1), but remove(Object) and contains are O(n). If you need arbitrary deletion, use lazy deletion (skip stale entries on poll) or a TreeSet.
• Iterating a PriorityQueue is not sorted. Printing it or looping with for-each shows heap order. Poll repeatedly to get sorted output.
• There is no decrease-key. For Dijkstra, push a new entry and skip outdated ones with if (d > dist[u]) continue;.
• new PriorityQueue<>(collection) heapifies in O(n), faster than n offers.

For the patterns (top-K, K-way merge, two heaps), see heap and priority queue problems.

ArrayDeque as a Stack, Queue and Deque

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); stack.push(2);
stack.peek();   // 2
stack.pop();    // 2   (throws if empty; use isEmpty() first)

Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1); queue.offer(2);
queue.poll();   // 1   (returns null if empty)

Deque<Integer> dq = new ArrayDeque<>();      // monotonic deque for window max
dq.offerLast(i); dq.peekFirst(); dq.peekLast(); dq.pollFirst(); dq.pollLast();

Why not Stack? It extends Vector, so every call is synchronized (wasted overhead) and it exposes get(i) and add(i, x), which let code break the LIFO contract. Oracle's own Javadoc recommends Deque implementations instead. One subtle difference: iterating a Stack goes bottom-to-top, iterating an ArrayDeque used via push goes top-to-bottom. And ArrayDeque rejects null elements, so do not use null as a sentinel in BFS level markers; use the queue size per level instead.

The deque patterns themselves (monotonic stack, next greater element, sliding window maximum) are in the stack, queue and monotonic stack guide.

Comparators That Sort Anything (Safely)

// ascending by start, then by end
Arrays.sort(intervals, (a, b) -> a[0] != b[0]
        ? Integer.compare(a[0], b[0])
        : Integer.compare(a[1], b[1]));

// same thing with Comparator combinators
Arrays.sort(intervals, Comparator.<int[]>comparingInt(a -> a[0]).thenComparingInt(a -> a[1]));

// strings by length, then lexicographically
words.sort(Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder()));

// Largest Number: custom concatenation order
Arrays.sort(strs, (x, y) -> (y + x).compareTo(x + y));

When chaining with .reversed(), watch for type inference: Comparator.comparingInt(a -> a[0]).reversed() on int[] fails to compile because Java infers Object for the lambda; add the explicit type witness Comparator.<int[]>comparingInt(...) or write the lambda by hand.

Strings, chars and StringBuilder

String s = "interview";
s.length(); s.charAt(0); s.substring(2, 6);   // "terv": (begin, END exclusive)
s.indexOf("view");                            // 5, or -1
s.equals(t);                                  // never == for strings
char[] cs = s.toCharArray(); Arrays.sort(cs); String sorted = new String(cs);
int idx = s.charAt(1) - 'a';                  // 13 for 'n'
Integer.parseInt("42"); String.valueOf(42); String.join(",", parts);

StringBuilder sb = new StringBuilder();
sb.append('a').append("bc");
sb.reverse(); sb.setCharAt(0, 'z'); sb.deleteCharAt(sb.length() - 1);
sb.insert(0, 'x');      // O(n): shifts characters
String out = sb.toString();

Strings are immutable, so result += c inside a loop copies the whole string each time: O(n²) total. Use StringBuilder. Note that substring copies characters (since JDK 7u6), so it costs O(length), not O(1). Use int[26] instead of HashMap<Character, Integer> for lowercase letter counts: faster, no boxing, and Arrays.equals(countA, countB) compares two of them.

The Integer Caching Bug: Why == Works Until It Doesn't

This is the most famous Java DSA bug, and it is nasty because it passes small test cases. Integer is an object, and == on objects compares references. Java caches the Integer objects for values -128 to 127 (the upper bound can be raised with a JVM flag, but -128..127 is the guaranteed default), so autoboxing small values returns the same object every time.

Integer a = 127, b = 127, c = 128, d = 128;
System.out.println(a == b);          // true  (same cached object)
System.out.println(c == d);          // false (two different objects)
System.out.println(c.equals(d));     // true
System.out.println(c.intValue() == d);  // true (unboxes, compares ints)

Map<Character, Integer> m1 = new HashMap<>(), m2 = new HashMap<>();
m1.put('x', 1000); m2.put('x', 1000);
System.out.println(m1.get('x') == m2.get('x'));      // false!
System.out.println(m1.get('x').equals(m2.get('x'))); // true

Where it bites in interviews:

• Comparing two frequency maps' values in anagram or permutation-in-string problems: passes when counts are small, fails on long inputs.
• stack.peek() == queue.peek() when both hold Integers, as in Implement Queue using Stacks checks or "Number of Students Unable to Eat Lunch" style problems.
• Comparing list elements: list.get(i) == list.get(j) on a List<Integer>.
• Min Stack implementations that compare stack.peek() == minStack.peek() to decide whether to pop the min: works for small values, breaks for large ones.

Fixes: use .equals(), use Objects.equals(a, b) if either might be null, or assign to int first (int top = stack.peek();). When one side is a primitive, Java unboxes the other and compares values, which is why c.intValue() == d works.

More Java Pitfalls in DSA Code

1. Unboxing null. int v = map.get(k); throws NullPointerException if k is absent. Use getOrDefault.
2. remove(int) vs remove(Object). On a List<Integer>, list.remove(x) with an int x removes the element at index x. Use list.remove(Integer.valueOf(x)) to remove the value.
3. ConcurrentModificationException. Removing from a list or map inside a for-each loop over it throws. Use removeIf, an explicit Iterator with it.remove(), or collect removals first.
4. Arrays as keys. Set<int[]> uses identity, so contains(new int[]{1, 2}) is false even after adding an equal array. Use List.of(r, c), a string key, or (long) r << 32 | c.
5. Mutable keys. Adding a List to a HashSet and then modifying the list changes its hash code and loses it inside the set. Add a copy.
6. int overflow. int mid = (lo + hi) / 2 overflows near Integer.MAX_VALUE; use lo + (hi - lo) / 2. Products like a * b need (long) a * b.
7. Negative modulo. -7 % 3 is -1 in Java. Use Math.floorMod(-7, 3) (= 2) for array indexing and hashing.
8. Copying references in backtracking. result.add(path) adds the same list object you keep mutating; add new ArrayList<>(path).
9. Boxing overhead. List<Integer> with 10⁶ elements is several times heavier than int[]. Prefer primitive arrays for DP tables.
10. Slow input. Scanner is slow for 10⁵+ tokens in OAs; use BufferedReader with StringTokenizer.

Java Collections Complexity Table

LinkedHashMap as an LRU cache in five lines

Interviewers often ask for LRU cache and then ask "is there a library shortcut?". In Java there is:

Map<Integer, Integer> lru = new LinkedHashMap<>(16, 0.75f, true) {   // true = access order
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }
};

Mention it, but expect to be asked to build the HashMap plus doubly linked list version anyway; the LRU cache walkthrough has both.

What Interviewers Probe in Java DSA Code

• "Why ArrayDeque and not Stack?" Legacy, synchronized, leaks Vector methods.
• "What does this comparator do with equal elements?" They want to see that you thought about tie-breaking, especially in TreeSet where comparator-equal elements are treated as duplicates and silently dropped.
• "What is the complexity of pq.remove(x)?" O(n), a common hidden cost.
• "How does HashMap work internally?" Array of buckets, hash spreading, load factor 0.75 triggering resize, and treeification of long buckets in Java 8+. This crosses into the language questions in Java interview questions.
• "Can this overflow?" Sums, products, mid computation and comparator subtraction.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.