The Java Collections Framework is one of the most tested interview topics. Know implementation internals, time complexity, and when to use each collection.

Collections Hierarchy 

  Collection
├── List (ordered, allows duplicates)
│   ├── ArrayList
│   ├── LinkedList
│   └── Vector (legacy, synchronized)
├── Set (no duplicates)
│   ├── HashSet
│   ├── LinkedHashSet
│   └── TreeSet (sorted)
└── Queue
    ├── PriorityQueue
    └── Deque (ArrayDeque, LinkedList)

Map (key-value, not a Collection)
├── HashMap
├── LinkedHashMap
├── TreeMap (sorted)
├── Hashtable (legacy, synchronized)
└── ConcurrentHashMap

ArrayList vs LinkedList

Q: When to use ArrayList vs LinkedList?

Operation ArrayList LinkedList
get(index) O(1) O(n)
add(end) O(1)* O(1)
add(middle) O(n) O(n) — must traverse
remove(middle) O(n) O(n) — must traverse
Memory Less overhead More (node pointers)

*Amortized — occasional resize copies array.

Default choice: ArrayList — cache-friendly contiguous memory, faster iteration. LinkedList rarely wins in practice (despite O(1) insert “in the middle”, finding the position is O(n)).

  List<String> list = new ArrayList<>();  // default choice
list.add("a");
list.get(0);  // O(1)

HashMap Internals

Q: How does HashMap work internally?

  1. Computes hash = key.hashCode()
  2. Bucket index = (n - 1) & hash (n = array length, power of 2)
  3. Stores Node (key, value, hash, next) in bucket
  4. Collision: linked list (Java 7) or tree (Java 8+, when bucket > 8 nodes)
  5. Load factor 0.75 — resize doubles capacity when 75% full
  Map<String, Integer> map = new HashMap<>();
map.put("apple", 3);
map.get("apple");  // O(1) average

Q: Why is HashMap not thread-safe?

Concurrent modification can cause infinite loops (Java 7) or lost updates. Use:

  • ConcurrentHashMap — thread-safe, segmented locking
  • Collections.synchronizedMap() — wraps with synchronized methods (slower)
  • External synchronization

HashMap vs Hashtable vs ConcurrentHashMap

HashMap Hashtable ConcurrentHashMap
Null keys/values One null key, null values Not allowed Not allowed
Thread-safe No Yes (synchronized) Yes (lock striping)
Performance Fastest (single thread) Slow (global lock) Fast (concurrent)
Legacy No Yes (avoid) No 
  // Thread-safe concurrent access
ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
map.put("count", 1);
map.merge("count", 1, Integer::sum);  // atomic increment

HashSet Internals

Q: How is HashSet implemented?

HashSet is a HashMap where elements are keys and values are dummy PRESENT objects:

  // Conceptually
private transient HashMap<E, Object> map;
private static final Object PRESENT = new Object();

public boolean add(E e) {
    return map.put(e, PRESENT) == null;
}

Therefore: add/contains/remove are O(1) average, requires good hashCode().

TreeMap and TreeSet

Q: When to use TreeMap/TreeSet?

Red-black tree implementation — O(log n) operations, elements sorted by natural order or Comparator:

  TreeMap<Integer, String> map = new TreeMap<>();
map.put(3, "three");
map.put(1, "one");
map.firstKey();  // 1
map.lastKey();   // 3
map.headMap(3);  // entries with key < 3

Use when you need sorted iteration or range queries.

Fail-Fast vs Fail-Safe Iterators

Q: What is fail-fast behavior?

  List<String> list = new ArrayList<>(List.of("a", "b", "c"));
for (String s : list) {
    list.remove(s);  // ConcurrentModificationException!
}

Iterator tracks modCount — detects structural modification during iteration.

Safe removal:

  Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().equals("b")) {
        it.remove();  // safe
    }
}

// Or Java 8+
list.removeIf(s -> s.equals("b"));

Fail-safe iterators (ConcurrentHashMap, CopyOnWriteArrayList) iterate over a snapshot — no exception but may not see recent changes.

Comparable vs Comparator 

  // Comparable — natural ordering (inside class)
public record User(String name, int age) implements Comparable<User> {
    @Override
    public int compareTo(User other) {
        return Integer.compare(this.age, other.age);
    }
}

// Comparator — external, multiple sort orders
Comparator<User> byName = Comparator.comparing(User::name);
Comparator<User> byAgeDesc = Comparator.comparingInt(User::age).reversed();

users.sort(byName);

Common Interview Questions

Q: How to convert List to Set and remove duplicates?

  List<String> list = List.of("a", "b", "a", "c");
Set<String> set = new LinkedHashSet<>(list);  // preserves order
List<String> unique = new ArrayList<>(set);

Q: Find the first non-repeating character.

  char firstUnique(String s) {
    Map<Character, Integer> count = new LinkedHashMap<>();
    for (char c : s.toCharArray()) {
        count.merge(c, 1, Integer::sum);
    }
    return count.entrySet().stream()
        .filter(e -> e.getValue() == 1)
        .map(Map.Entry::getKey)
        .findFirst()
        .orElse('\0');
}

Q: Implement LRU Cache.

  class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    LRUCache(int capacity) {
        super(capacity, 0.75f, true); // accessOrder = true
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

Or use Caffeine cache library in production.

Stream API Quick Reference 

  List<Integer> result = numbers.stream()
    .filter(n -> n > 0)
    .map(n -> n * 2)
    .sorted()
    .distinct()
    .collect(Collectors.toList());

Map<String, Long> counts = words.stream()
    .collect(Collectors.groupingBy(w -> w, Collectors.counting()));
Operation Parallel safe?
filter, map Yes (stateless)
sorted, distinct Yes (with merge cost)
forEach Side effects need care

Key Takeaways

  • Default to ArrayList, HashMap, HashSet
  • Know O(1) vs O(log n) vs O(n) for each operation
  • Never modify a collection while iterating (except iterator.remove())
  • Use ConcurrentHashMap for concurrent access, not synchronized wrappers
  • Override equals() and hashCode() together for hash-based collections

Next: Concurrency Interview Questions