Java Collections Interview Questions

Dynamic array (resizable array)

ArrayList is backed by a dynamic array (Object[]). When the array reaches capacity, a new array is created with 1.5x the size, and elements are copied over. This gives O(1) amortized time for add operations and O(1) for random access via index, but O(n) for insertions or deletions in the middle due to element shifting.

[A, X, B, C]

The add(int index, E element) method inserts the element at the specified index and shifts existing elements to the right. Here, "X" is inserted at index 1, pushing "B" and "C" one position forward. The result is [A, X, B, C].

When you frequently add/remove elements at the beginning or end of the list

LinkedList implements both List and Deque interfaces and excels at adding/removing elements at the head or tail in O(1) time. ArrayList requires O(n) shifting for insertions at the beginning. However, LinkedList has higher memory overhead per element (each node stores two pointers) and O(n) random access, so ArrayList is generally preferred unless you need frequent head/tail operations.

A collision occurs and both entries are stored in the same bucket using a linked list (or tree if the bucket grows large)

When two keys hash to the same bucket index, a hash collision occurs. In Java 8+, the bucket stores entries in a linked list. If the number of entries in a single bucket exceeds 8 (and the table has at least 64 buckets), the linked list is converted to a balanced red-black tree for O(log n) lookup instead of O(n). This is called treeification.

Initial capacity: 16, load factor: 0.75

HashMap has a default initial capacity of 16 and a load factor of 0.75. The load factor determines when the map is resized: when the number of entries exceeds capacity * load factor (i.e., 12 entries for the default), the internal array doubles in size and all entries are rehashed. A load factor of 0.75 is a good trade-off between time (fewer collisions) and space (less wasted memory).

Because HashMap uses hashCode() to find the bucket and equals() to find the exact key within the bucket; breaking the contract causes incorrect lookups

HashMap relies on hashCode() to determine which bucket to place an entry in, and equals() to locate the exact key within that bucket. If two objects are equal (equals() returns true) but have different hash codes, a get() call may look in the wrong bucket and fail to find the entry. This is why the contract states: if a.equals(b), then a.hashCode() == b.hashCode().

HashMap provides O(1) average lookup with no ordering; TreeMap provides O(log n) lookup with keys sorted in natural or custom order

HashMap is backed by a hash table, providing O(1) average-case performance for get/put but no ordering guarantees. TreeMap is backed by a red-black tree, providing O(log n) performance but maintaining keys in sorted order (natural ordering via Comparable, or custom ordering via a Comparator). Note that HashMap allows one null key while TreeMap does not (it would throw NullPointerException when comparing).

[Apple, Banana, Cherry]

TreeMap sorts its keys in natural ordering (alphabetical for Strings). Regardless of insertion order, the keys are always maintained in sorted order. So the keySet() returns [Apple, Banana, Cherry]. If you need insertion-order preservation, use LinkedHashMap instead.

It internally uses a HashMap where elements are stored as keys, relying on hashCode() and equals()

HashSet is backed by a HashMap internally. When you add an element to a HashSet, it is stored as a key in the underlying HashMap (with a dummy constant as the value). Since HashMap does not allow duplicate keys (using hashCode() to find the bucket and equals() to check for duplicates within the bucket), HashSet naturally prevents duplicate elements.

[C, A, B]

LinkedHashSet maintains insertion order while still preventing duplicates. "A" is added first at position 2, and the second add("A") is ignored since it already exists. The result is [C, A, B] in insertion order. A regular HashSet would not guarantee any particular order.

add()/remove() throw exceptions on failure; offer()/poll() return special values (false/null) on failure

The Queue interface provides two sets of methods for each operation. add() throws an IllegalStateException if the queue is full, while offer() returns false. remove() throws a NoSuchElementException if the queue is empty, while poll() returns null. For bounded queues (like ArrayBlockingQueue), the offer/poll methods are generally preferred as they handle capacity limits gracefully.

Methods to add, remove, and examine elements at both the front and back (e.g., addFirst, addLast, pollFirst, pollLast)

Deque (Double-Ended Queue) extends Queue to allow insertion and removal at both ends. It provides methods like addFirst(), addLast(), removeFirst(), removeLast(), peekFirst(), and peekLast(). ArrayDeque is the recommended implementation for both stack (LIFO) and queue (FIFO) operations, and is generally faster than both Stack and LinkedList for these use cases.

It uses segment-level locking (Java 7) or CAS operations with synchronized blocks on individual buckets (Java 8+)

In Java 7, ConcurrentHashMap used segment-level locking (dividing the map into 16 segments, each independently lockable). In Java 8+, the design changed to use a combination of CAS (Compare-And-Swap) operations for insertion into empty buckets and synchronized blocks on the first node of each bucket for collision handling. This allows much higher concurrency since threads operating on different buckets never block each other.

{A=1, B=2, C=3}

putIfAbsent() only inserts the value if the key is not already present. Since "A" already maps to 1, putIfAbsent("A", 99) does nothing and returns 1. Since "C" is not present, putIfAbsent("C", 3) inserts it. The result is {A=1, B=2, C=3}. Note that ConcurrentHashMap does not allow null keys or null values, unlike HashMap.

Fail-fast iterators throw ConcurrentModificationException if the collection is modified during iteration; fail-safe iterators work on a copy or snapshot and do not throw

Fail-fast iterators (used by ArrayList, HashMap, HashSet) detect structural modification during iteration via an internal modCount and throw ConcurrentModificationException. Fail-safe iterators (used by ConcurrentHashMap, CopyOnWriteArrayList) operate on a snapshot or allow concurrent modification without throwing. The trade-off is that fail-safe iterators may not reflect the latest changes made during iteration.

[A, C, D]

Using Iterator.remove() is the safe way to remove elements during iteration. It removes the last element returned by next() and updates the internal state so no ConcurrentModificationException is thrown. Calling list.remove() directly during iteration would trigger the exception. The result is [A, C, D].

It can iterate in both directions (forward and backward), add elements, and replace elements

ListIterator extends Iterator with bidirectional traversal (hasPrevious(), previous()), the ability to add elements at the current position (add()), replace the last returned element (set()), and retrieve the index of the next or previous element (nextIndex(), previousIndex()). It is only available for List implementations via list.listIterator().

It throws an UnsupportedOperationException at runtime

Collections.unmodifiableList() returns an unmodifiable view of the original list. Any mutating operation (add, remove, set) throws an UnsupportedOperationException at runtime. However, it is a view, not a copy, so changes to the original backing list will still be visible through the unmodifiable wrapper. For a truly immutable list in Java 9+, use List.of() or List.copyOf().

Index: 1

After Collections.sort(list), the list becomes [1, 3, 5, 8]. Collections.binarySearch() then searches the sorted list for 3 and returns its index, which is 1. Note that binarySearch() requires the list to be sorted in ascending order beforehand; if the list is not sorted, the result is undefined. If the element is not found, it returns -(insertion point) - 1.

Comparable defines one natural ordering inside the class via compareTo(); Comparator allows multiple custom orderings defined externally via compare()

Comparable is implemented by the class itself (e.g., class Employee implements Comparable<Employee>) and defines a single natural ordering through compareTo(). Comparator is a separate functional interface that defines an external comparison strategy, allowing you to create multiple sort orders (by name, by age, by salary) without modifying the original class. In Java 8+, you can use Comparator.comparing() for clean lambda-based comparators.