Java Built-In Data Structures for Coding Interviews

Java gives you fifteen ways to store a collection. In a coding interview you need eight of them, but you need to reach for the right one instantly, spell the constructor correctly under pressure, and explain your choice out loud while also solving the problem. Pick the wrong one and you spend five minutes in silent debugging purgatory. Use the wrong comparator and your solution is silently wrong. Use Stack and your interviewer makes a note.

The Two-Second Decision Table

You need	Reach for
Indexed sequence	`int[]` or `ArrayList<Integer>`
Stack	`ArrayDeque<Integer>`
Queue	`ArrayDeque<Integer>`
Key-value lookup	`HashMap<K, V>`
Sorted key-value, floor/ceiling	`TreeMap<K, V>`
Insertion-ordered map	`LinkedHashMap<K, V>`
Fast membership test	`HashSet<T>`
Sorted membership, floor/ceiling	`TreeSet<T>`
Min or max heap	`PriorityQueue<T>`
Mutable string	`StringBuilder`

Never use Stack, Vector, or Hashtable. All three are synchronized legacy classes that acquire a lock on every operation. They exist because Java 1.0 shipped in 1996 and backwards compatibility is forever. They show up in old tutorials, old StackOverflow answers, and old codebases. They do not show up in good interviews.

Complexity at a Glance

Structure	Get/Contains	Insert	Remove	Ordered?
`int[]`	O(1)	n/a	n/a	by index
`ArrayList`	O(1)	O(1) amort.	O(n)	by index
`ArrayDeque`	O(1) peek	O(1)	O(1)	no
`HashMap`	O(1) avg	O(1) avg	O(1) avg	no
`LinkedHashMap`	O(1) avg	O(1) avg	O(1) avg	insertion
`TreeMap`	O(log n)	O(log n)	O(log n)	sorted
`HashSet`	O(1) avg	O(1) avg	O(1) avg	no
`TreeSet`	O(log n)	O(log n)	O(log n)	sorted
`PriorityQueue`	O(1) peek	O(log n)	O(log n)	heap only

Java collections complexity map showing O(1) in green, O(log n) in blue, O(n) in amber, with PriorityQueue.contains callout

One number worth burning into memory: PriorityQueue.contains() is O(n). It scans linearly. If you need fast membership alongside heap operations, maintain a separate HashSet. Yes, this is annoying. Java contains multitudes.

Start Here. Seriously.

When you know the size upfront, a plain array is the right choice. No autoboxing, no resizing overhead, no generics ceremony.

int[] arr = new int[n];             // initialized to 0
int[][] grid = new int[rows][cols]; // initialized to 0
Arrays.fill(arr, -1);
int[] copy = Arrays.copyOf(arr, arr.length);
int[] slice = Arrays.copyOfRange(arr, 2, 5); // [2, 5)
Arrays.binarySearch(arr, target);   // requires sorted input

Arrays.sort(int[]) uses dual-pivot quicksort and cannot accept a comparator. To sort with custom ordering you have to box to Integer[], which is its own adventure. This trips up everyone at least once.

// Does not compile. You will try this.
Arrays.sort(arr, (a, b) -> b - a);

// Works. You will be annoyed.
Integer[] boxed = new Integer[arr.length];
for (int i = 0; i < arr.length; i++) { boxed[i] = arr[i]; }
Arrays.sort(boxed, (a, b) -> Integer.compare(b, a));

Arrays.sort(int[]) is unstable. Arrays.sort(Object[]) uses Timsort and is stable. For most interview problems the distinction does not matter, but it matters for multi-key sorts and for radix sort correctness.

ArrayList: O(1) Until You Call Remove

List<Integer> list = new ArrayList<>();
list.add(x);          // amortized O(1)
list.get(i);          // O(1)
list.set(i, x);       // O(1)
list.remove(i);       // O(n), shifts everything left
list.contains(x);     // O(n), linear scan
list.size();          // O(1)

The remove ambiguity is a gift that keeps giving. list.remove(2) removes by index. list.remove(Integer.valueOf(2)) removes by value. Pass a primitive, get index semantics. Pass a boxed Integer, get value semantics. The Java type system is consistent and well-designed.

Arrays.asList() returns a fixed-size view backed by the original array. set works. add and remove throw UnsupportedOperationException at runtime, not at compile time, which means you find out the hard way. Use new ArrayList<>(Arrays.asList(...)) for a mutable copy. List.of() is fully immutable and throws on everything including set.

More on why array access outperforms linked structures at the same Big-O here.

One Class, Zero Excuses for Using Stack

ArrayDeque is the right tool for both stack and queue operations. It's faster than LinkedList (contiguous memory, better cache behavior) and not synchronized like the Stack class. Use it for both. Every time.

Deque<Integer> dq = new ArrayDeque<>();

// As a stack
dq.push(x);    // addFirst
dq.pop();      // removeFirst, throws if empty
dq.peek();     // peekFirst, null if empty

// As a queue
dq.offer(x);   // addLast
dq.poll();     // removeFirst, null if empty
dq.peek();     // peekFirst, null if empty

// Full deque access
dq.offerFirst(x);
dq.offerLast(x);
dq.pollFirst();
dq.pollLast();
dq.peekFirst();
dq.peekLast();

All operations are O(1) amortized. ArrayDeque does not permit null elements. That's almost never a constraint in interview problems, but it explains the NPE you get when you push null and there is no obvious cause.

HashMap: O(1) Average, O(Infinity) Debugging

HashMap is the default for key-value storage. O(1) average for everything.

Map<String, Integer> map = new HashMap<>();
map.put(key, val);
map.get(key);                      // null if absent, not 0
map.getOrDefault(key, 0);          // safe default
map.containsKey(key);
map.remove(key);
map.size();

Two idioms that appear in nearly every interview solution:

// Frequency count
map.put(key, map.getOrDefault(key, 0) + 1);

// Group values into lists
map.computeIfAbsent(key, k -> new ArrayList<>()).add(val);

Never write int x = map.get(key) when the key might be absent. get returns null for missing keys. Unboxing null to a primitive int throws NullPointerException at the assignment line, not at get. The stack trace points at the assignment. You stare at it. You question everything. Just use getOrDefault(key, 0).

for (Map.Entry<String, Integer> entry : map.entrySet()) {
    String k = entry.getKey();
    int v = entry.getValue();
}

The deep explanation of why HashMap lookup is O(1) and when it quietly degrades is in this breakdown.

LinkedHashMap gives you insertion-order iteration at the same O(1) cost. It's the base class for LRU cache implementations. Override removeEldestEntry and you have a working cache in about ten lines. Classic interview ask.

TreeMap: When You Need Floor and Ceiling

TreeMap<Integer, String> tree = new TreeMap<>();
tree.put(k, v);
tree.floorKey(k);    // largest key <= k, null if none
tree.ceilingKey(k);  // smallest key >= k, null if none
tree.lowerKey(k);    // largest key < k strictly
tree.higherKey(k);   // smallest key > k strictly
tree.firstKey();
tree.lastKey();
tree.headMap(k);     // keys strictly less than k
tree.tailMap(k);     // keys >= k

TreeMap is backed by a Red-Black tree, so all operations are O(log n). Reach for it when you need a sorted map and the nearest key: tracking a sliding window's frequency distribution, finding the closest appointment time, building a calendar of events. The floor and ceiling methods are the whole point. You pay log factor, you get sorted order.

Sets: HashMap's Antisocial Cousin

HashSet for fast membership testing. TreeSet when you also need sorted traversal or floor/ceiling queries.

Set<Integer> seen = new HashSet<>();
seen.add(x);
seen.contains(x);   // O(1) average
seen.remove(x);

TreeSet<Integer> ts = new TreeSet<>();
ts.add(x);
ts.floor(x);        // largest element <= x
ts.ceiling(x);      // smallest element >= x
ts.lower(x);        // largest element < x strictly
ts.higher(x);       // smallest element > x strictly
ts.first();
ts.last();

HashSet is backed by a HashMap with a dummy value. TreeSet is backed by a TreeMap. Their complexities mirror their map counterparts exactly. There's nothing surprising here. Java is transparent about its implementation details, in documentation that most people never read.

PriorityQueue: It's a Min-Heap. This Will Catch You.

// Min-heap (default)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// Max-heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

// Custom comparator for arrays sorted by first element
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));

minHeap.offer(x);  // O(log n), inserts
minHeap.poll();    // O(log n), removes and returns minimum
minHeap.peek();    // O(1), returns minimum without removing

The default is a min-heap. poll() returns the smallest element. This is the single most common PriorityQueue mistake in interviews. You write a max-heap solution, forget Collections.reverseOrder(), and spend five minutes debugging why your top-K result is backwards. It is a deeply demoralizing five minutes. It happens to good engineers constantly.

And please: never write (a, b) -> a - b as a comparator. If a = Integer.MIN_VALUE and b = 1, the subtraction overflows to a large positive number, silently reverses the comparison, and gives you wrong results with no error or warning. Use Integer.compare(a, b) or Comparator.comparingInt. Every time. No exceptions.

The internal structure of a heap and why these complexities hold is covered in the heap deep dive.

StringBuilder: Paying the O(n²) Tax Voluntarily

String concatenation with + in a loop is O(n²). Each + allocates a new string object and copies all previous content. Java strings are immutable, which is great for most things and a trap for this one.

StringBuilder sb = new StringBuilder();
sb.append("hello");
sb.append(' ');
sb.append(42);
sb.insert(0, "prefix");
sb.deleteCharAt(sb.length() - 1);
sb.delete(2, 5);      // [2, 5)
sb.reverse();
sb.charAt(i);
String result = sb.toString();

Building a result string character by character is O(n) with StringBuilder and O(n²) without it. In a 45-minute interview, the difference shows up. The methods you'll use most: append, deleteCharAt, reverse, length, toString.

Five Bugs That Are Technically Your Fault

Integer equality with ==. Java caches boxed Integer values from -128 to 127. Integer a = 127; Integer b = 127; a == b is true. Change 127 to 128 and it's false. This is documented, intentional, and responsible for a shocking number of subtle interview bugs. Use .equals() or Objects.equals(a, b) any time you compare boxed integers.

Comparator subtraction overflow. (a, b) -> a - b is not a safe ascending comparator. Subtraction overflows when values are near Integer.MIN_VALUE. Write Integer.compare(a, b) in every comparator you write, without exception.

Autoboxing NPE. int x = map.get(key) throws NullPointerException when the key is absent, at the unboxing step, not at get. The stack trace points at the assignment line. Use getOrDefault.

Arrays.sort modifies in place. If you need the original order later, copy first: int[] copy = Arrays.copyOf(arr, arr.length). Otherwise you sort the input, permanently modify it, and spend time wondering why your algorithm is wrong.

Arrays.asList is not a full list. add and remove throw at runtime. Wrap in new ArrayList<>() if you need mutability.

A fuller breakdown of Java-specific interview traps, including how Arrays.sort stability affects multi-key sorting, is in the Java interview guide.

You Know the APIs. Now Say Them Out Loud.

Knowing that TreeMap.floorKey(k) exists is different from explaining your choice out loud, mid-problem, to someone watching and taking notes. Most engineers can describe HashMap in isolation. Fewer can choose TreeMap over HashMap in real time, say "I need floor/ceiling so I'll pay the log factor," and keep coding without pausing.

That's the gap SpaceComplexity trains: voice-based mock interviews with rubric feedback on communication, problem-solving, and code quality. You build the muscle of deploying these data structures in the actual condition that causes interview failures.