Collections Internals & Scenarios — Interview Questions

How to use this lesson

Intermediate collections questions are about behaviour under pressure: what breaks when a key mutates, which algorithm sorts your list, what clear() really frees. Back up every claim with a short snippet. These are the bugs you've probably met in production.

Q1. Describe a scenario where you used a PriorityQueue, and why it beat other queues.

Short answer: Whenever items must be processed by priority, not arrival order. For example:

• a job scheduler running the earliest-deadline job first;
• a notification dispatcher where OTPs jump ahead of marketing emails;
• keeping the top-K items from a stream.

A PriorityQueue is a binary min-heap: offer/poll are O(log n), and peek is O(1). A FIFO queue would need re-sorting on every insert.

record Job(String id, int priority, Instant deadline) { }

PriorityQueue<Job> queue = new PriorityQueue<>(
        Comparator.comparingInt(Job::priority).reversed().thenComparing(Job::deadline));

// top-K largest orders with a bounded min-heap: O(n log k)
PriorityQueue<Order> topK = new PriorityQueue<>(Comparator.comparing(Order::total));
for (Order o : orders) {
    topK.offer(o);
    if (topK.size() > 10) topK.poll();        // evict the smallest
}

Key points to cover:

• Iteration order isn't sorted. Only poll() returns elements in priority order.
• It isn't thread-safe. Use PriorityBlockingQueue for producer/consumer designs, or DelayQueue for scheduled items.

Learn it in depth → Top K Elements

Q2. What goes wrong when mutable objects are used as HashMap keys?

Short answer: The entry is stored in a bucket chosen by the key's hash at insertion time. If you then mutate a field that hashCode() uses, lookups compute a different hash, search the wrong bucket, and can't find the entry. It's still in the map, taking memory, and it's effectively lost: a silent leak and data bug.

Set<Point> visited = new HashSet<>();
Point p = new Point(1, 2);          // mutable, with value-based equals/hashCode
visited.add(p);
p.setX(5);
visited.contains(p);                // false, although the object is "in" the set

Key points to cover:

• Use immutable keys: String, boxed numbers, records with immutable fields. If mutation is unavoidable, remove the entry, mutate, and re-insert.

Learn it in depth → HashMap Deep Dive

Q3. What happens if a key class overrides equals() but not hashCode()?

Short answer: It breaks the contract that equal objects must have equal hash codes. Two logically equal keys get different identity hashes, land in different buckets, and never get compared with equals. Result: get returns null for an "equal" key, and put stores logical duplicates.

Key points to cover:

• Fix: implement both consistently, over the same fields (Objects.hash(id, region)), or use a record.
• Static analysis (SpotBugs, SonarQube) flags equals without hashCode.

Q4. How do HashMap and IdentityHashMap differ in handling keys?

Short answer: HashMap compares keys with equals()/hashCode(), which is logical equality. IdentityHashMap compares with == and System.identityHashCode, which is reference equality. Two different but equal String objects are one key in a HashMap, and two keys in an IdentityHashMap.

Key points to cover:

• Legitimate uses are rare:
  • Graph algorithms tracking visited objects.
  • Serialization or deep-copy code that must handle object cycles (a map from each original object to its copy).
  • Proxies that must not trigger equals.
• Internally, it uses linear probing in a single array, not buckets of nodes.
• It intentionally violates the Map contract, which is specified in terms of equals.

Q5. How does Collections.sort() work internally?

Short answer: Collections.sort(list) calls list.sort(null). The default List.sort copies the list into an array, sorts it with Arrays.sort(Object[]) → TimSort, and writes the elements back. ArrayList overrides it to sort its internal array directly. TimSort is a stable hybrid of merge sort and insertion sort that finds existing ordered "runs": O(n log n) in the worst case, and O(n) on data that's already sorted.

Key points to cover:

• Stability means equal elements keep their relative order, so you can sort by one key, then stably re-sort by another.
• Lists hold objects, so Collections.sort never sorts primitives. Primitive arrays use Dual-Pivot Quicksort in Arrays.sort(int[]), which isn't stable, but stability doesn't matter for primitives.
• A comparator that breaks its contract (inconsistent or non-transitive) can make TimSort throw "Comparison method violates its general contract!".

Q6. What happens if you sort a list containing null with Collections.sort()?

Short answer: With natural ordering, compareTo is called on or with null, which throws a NullPointerException. (A one-element list is returned unchanged without comparing, so List.of(null)-like single-element cases don't throw.) Handle nulls explicitly with a null-safe comparator:

names.sort(Comparator.nullsLast(Comparator.naturalOrder()));
employees.sort(Comparator.comparing(Employee::manager, Comparator.nullsFirst(Comparator.comparing(Manager::name))));

Q7. Can you sort custom objects with Collections.sort() without a comparator?

Short answer: Only if the class implements Comparable<T>, which defines its natural ordering in compareTo. Otherwise, sorting fails at runtime with a ClassCastException ("cannot be cast to class java.lang.Comparable").

record Version(int major, int minor) implements Comparable<Version> {
    public int compareTo(Version o) {
        return Comparator.comparingInt(Version::major).thenComparingInt(Version::minor).compare(this, o);
    }
}

Key points to cover:

• Keep compareTo consistent with equals. TreeSet and TreeMap treat compareTo == 0 as "the same element".

Q8. What's the difference between Collections.sort() and Stream.sorted()?

Short answer:

orders.sort(Comparator.comparing(Order::createdAt));                  // mutates 'orders'
List<Order> latest = orders.stream()
        .sorted(Comparator.comparing(Order::createdAt).reversed())
        .limit(10).toList();                                           // new list; source unchanged

Key points to cover:

• List.of(...) is immutable, so Collections.sort on it throws UnsupportedOperationException, while stream().sorted() works.

Q9. How do you choose an ArrayList's initial capacity when the list is cleared and reused over and over?

Short answer: Size it for the typical peak batch (new ArrayList<>(expectedMax)), to avoid repeated growth copies on the first fill. Remember that clear() keeps the grown backing array: it nulls the elements, but never shrinks. After the first big batch, capacity is never a problem again, but memory is. One huge batch leaves the list holding a huge array forever.

Key points to cover:

• If the batch sizes vary wildly, either create a new list per batch (allocation is cheap, and the GC handles short-lived arrays well), or call trimToSize() after an unusually large batch.
• Reuse only matters in genuinely hot paths. Measure before optimising.

Q10. Scenario: how would you compare two custom objects for content equality?

Short answer: Override equals() and hashCode() over the fields that define the object's identity or value, following the contract (reflexive, symmetric, transitive, consistent, and false for null). Or declare the type as a record, which does it for you.

public final class Money {
    private final BigDecimal amount;
    private final Currency currency;

    @Override public boolean equals(Object o) {
        return o instanceof Money m
                && amount.compareTo(m.amount) == 0          // 10.0 == 10.00 for money purposes
                && currency.equals(m.currency);
    }
    @Override public int hashCode() {
        return Objects.hash(amount.stripTrailingZeros(), currency);   // consistent with equals
    }
}

Key points to cover:

• For entities, equality is usually based on the identifier. For value objects, it's based on all the values.
• In tests, AssertJ's usingRecursiveComparison() compares objects field by field, without needing equals at all.

Q11. Scenario: you store user sessions in a HashMap. How do you make it thread-safe?

Short answer: Replace it with a ConcurrentHashMap, which allows many concurrent readers and writers with fine-grained locking, and use its atomic compound methods. Collections.synchronizedMap also works, but it serialises every access behind one lock, and you must lock manually while iterating.

private final ConcurrentMap<String, Session> sessions = new ConcurrentHashMap<>();

Session s = sessions.computeIfAbsent(sessionId, id -> Session.create(id));   // atomic get-or-create
sessions.computeIfPresent(sessionId, (id, old) -> old.touch());               // atomic update
sessions.values().removeIf(Session::isExpired);                                // safe cleanup

Key points to cover:

• Thread-safe operations aren't enough if you do check-then-act across calls (if (!map.containsKey(k)) map.put(k, v)). Use the atomic methods instead.
• In a clustered app, in-memory sessions don't survive failover or scale across instances. Use Spring Session with Redis.
• Add expiry. A cache library such as Caffeine gives you TTL and size bounds for free.

Learn it in depth → HashMap Concurrency Variants

Q12. How does a TreeSet order custom objects (not wrapper classes)?

Short answer: A TreeSet is backed by a red-black tree (a TreeMap). It orders elements using either:

1. their natural ordering, which requires implementing Comparable; or
2. a Comparator passed to the constructor.

If you provide neither, the first add throws a ClassCastException. (Since Java 7, even adding the first element triggers a comparison with itself.)

TreeSet<Employee> bySalary = new TreeSet<>(
        Comparator.comparing(Employee::salary).thenComparing(Employee::id));   // tie-breaker!

Q13. How does a TreeSet sort objects? (Follow-up: what about duplicates?)

Short answer: Same mechanism as Q12, with the key follow-up: TreeSet decides uniqueness by comparison, not equals. If your comparator says two different employees compare as 0, for example because they have the same salary, the second one is silently dropped. Always add a tie-breaker (such as the ID) to comparators used for sorted sets and maps.

Follow-up questions this topic invites — and their answers

Q: LinkedHashMap access order: how do you build an LRU cache from it? A: Construct it with accessOrder = true, and override removeEldestEntry to return size() > capacity. Each get then moves the entry to the end, and the eldest (least recently used) entry is evicted automatically. Wrap it for thread safety, or use Caffeine in production.

Q: What does Collections.unmodifiableList actually protect? A: Only the view. Changes through the original list still show through. List.copyOf creates a truly independent, immutable copy.

Q: WeakHashMap: when would you use it? A: For metadata attached to objects whose lifecycle you don't control. Entries disappear once the key is no longer strongly referenced elsewhere. Note that its keys are weak, not its values.

Q: Why is ArrayDeque preferred over Stack and LinkedList? A: Stack is synchronised legacy code (it extends Vector). ArrayDeque is a resizable circular array: faster, with less memory per element than LinkedList, and without per-operation locking.