15 Java Collection Framework Interview Questions and Answers

The Java Collection Framework is a cornerstone of Java programming, providing a standardized architecture to manage and manipulate groups of objects. It includes interfaces, implementations, and algorithms that offer a robust and flexible way to handle data structures such as lists, sets, and maps. Mastery of this framework is essential for writing efficient and maintainable Java code, making it a critical skill for any Java developer.

This article offers a curated selection of interview questions focused on the Java Collection Framework. By working through these questions and their detailed answers, you will deepen your understanding of the framework’s intricacies and be better prepared to demonstrate your expertise in technical interviews.

Java Collection Framework Interview Questions and Answers

1. What is the difference between a Set and a List?

In the Java Collection Framework, both Set and List are interfaces that define collections of objects, but they have distinct characteristics and use cases.

A *List* is an ordered collection that allows duplicate elements. It maintains the insertion order, meaning elements can be accessed by their index. Common implementations include ArrayList, LinkedList, and Vector. Lists are useful when you need to maintain a sequence of elements and access them by their position.

A *Set*, on the other hand, is an unordered collection that does not allow duplicate elements. It models the mathematical set abstraction. Common implementations include HashSet, LinkedHashSet, and TreeSet. Sets are useful when you need to ensure no duplicates are present and the order of elements is not important.

Key differences:

• Order: List maintains insertion order, while Set does not.
• Duplicates: List allows duplicates, whereas Set does not.
• Access: List provides positional access via indices, while Set does not.

2. How does a HashMap handle collisions?

A HashMap handles collisions using chaining. When two keys hash to the same index, a linked list (or a binary tree in high collision scenarios) stores multiple entries at that index. Each entry contains a key-value pair. When a collision occurs, the new entry is added to the linked list at the corresponding index.

Here is a high-level overview of how it works:

• When a key-value pair is inserted, the hash code of the key is computed.
• The hash code determines the index in the underlying array where the entry should be stored.
• If the index is already occupied (collision), the new entry is added to the linked list at that index.
• When retrieving a value, the hash code of the key is computed again to find the index. The linked list at that index is traversed to find the entry with the matching key.

3. How would you implement a custom Comparator for sorting a list of objects?

A Comparator is an interface used to define a custom ordering for objects. It is useful when you need to sort a collection of objects differently from their natural ordering. The Comparator interface has a single method, compare, which takes two objects and returns an integer indicating their relative order.

Here is an example of how to implement a custom Comparator for sorting a list of objects:

import java.util.*;

class Person {
    String name;
    int age;

    Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public String toString() {
        return name + " (" + age + ")";
    }
}

class AgeComparator implements Comparator<Person> {
    @Override
    public int compare(Person p1, Person p2) {
        return Integer.compare(p1.age, p2.age);
    }
}

public class Main {
    public static void main(String[] args) {
        List<Person> people = new ArrayList<>();
        people.add(new Person("Alice", 30));
        people.add(new Person("Bob", 25));
        people.add(new Person("Charlie", 35));

        Collections.sort(people, new AgeComparator());

        for (Person person : people) {
            System.out.println(person);
        }
    }
}

In this example, the Person class represents the objects to be sorted. The AgeComparator class implements the Comparator interface and provides the custom sorting logic based on the age attribute of the Person objects. The Collections.sort method is then used to sort the list of Person objects using the custom Comparator.

4. What are the main differences between HashSet and TreeSet?

The main differences between HashSet and TreeSet are:

• Underlying Data Structure: HashSet is backed by a hash table, whereas TreeSet is backed by a Red-Black tree.
• Ordering: HashSet does not guarantee any order of the elements. TreeSet maintains elements in a sorted order.
• Performance: HashSet generally offers constant-time performance for basic operations like add, remove, and contains. TreeSet provides log(n) time cost for these operations due to its tree structure.
• Null Elements: HashSet allows null elements, while TreeSet does not as it needs to compare elements to maintain order.
• Methods: TreeSet provides additional methods like first(), last(), headSet(), tailSet(), and subSet() to retrieve specific ranges of elements, which are not available in HashSet.

5. Describe the internal structure of a LinkedHashMap.

A LinkedHashMap combines a hash table and a linked list. It maintains a doubly-linked list running through all of its entries, defining the iteration ordering. This ordering can be either the order in which keys were inserted (insertion-order) or the order in which keys were last accessed (access-order).

The internal structure consists of:

• Hash Table: Similar to a HashMap, it uses a hash table to store key-value pairs. Each entry is a node containing a key, a value, a hash, and references to the next node (for handling collisions).
• Doubly-Linked List: Each node also contains references to the previous and next nodes in the linked list, maintaining the order of entries.

LinkedHashMap provides predictable iteration order, useful for applications where the order of elements is important, such as caching mechanisms.

6. How can you make a Collection thread-safe?

You can make a collection thread-safe by using synchronization wrappers provided by the Collections class or by using concurrent collections from the java.util.concurrent package.

One way is by using the synchronized wrappers provided by the Collections class. For example, you can wrap a List with Collections.synchronizedList:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

List<String> synchronizedList = Collections.synchronizedList(new ArrayList<>());

Another approach is to use concurrent collections from the java.util.concurrent package, designed for concurrent access. For example, you can use a ConcurrentHashMap for a thread-safe map:

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;

ConcurrentMap<String, String> concurrentMap = new ConcurrentHashMap<>();

7. Explain the concept of load factor in a HashMap.

The load factor in a HashMap determines when the HashMap should increase its capacity to maintain efficient performance. It is defined as the ratio of the number of elements in the HashMap to its current capacity. The default load factor is 0.75, meaning that when the HashMap is 75% full, it will resize itself.

When the number of entries exceeds the product of the load factor and the current capacity, the HashMap undergoes rehashing. During rehashing, the capacity is increased, and all existing entries are redistributed into the new, larger array. This process helps maintain a balance between time complexity for insertion and lookup operations.

A lower load factor reduces the likelihood of collisions, improving lookup time but increasing memory consumption. Conversely, a higher load factor reduces memory usage but increases the likelihood of collisions, which can degrade performance.

8. How would you implement a LRU (Least Recently Used) cache using Java Collections?

An LRU (Least Recently Used) cache discards the least recently used items first when it reaches its capacity. This is useful in scenarios where you want to limit memory usage and ensure that the most recently accessed items are retained.

In Java, the LinkedHashMap class can be used to implement an LRU cache. By overriding the removeEldestEntry method, we can ensure that the least recently used entry is removed when the cache exceeds its capacity.

Example:

import java.util.LinkedHashMap;
import java.util.Map;

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

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

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

    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(3);
        cache.put(1, "one");
        cache.put(2, "two");
        cache.put(3, "three");
        cache.get(1);
        cache.put(4, "four");

        System.out.println(cache);
    }
}

In this example, the LRUCache class extends LinkedHashMap and overrides the removeEldestEntry method to ensure the cache does not exceed the specified capacity. The true parameter in the LinkedHashMap constructor enables access-order, which is essential for the LRU behavior.

9. How would you detect a cycle in a LinkedList?

To detect a cycle in a LinkedList, use Floyd’s Cycle-Finding Algorithm, also known as the “Tortoise and Hare” algorithm. This algorithm uses two pointers that move at different speeds. If there is a cycle, the two pointers will eventually meet; if there is no cycle, the faster pointer will reach the end of the list.

Example:

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class LinkedListCycle {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }

        ListNode slow = head;
        ListNode fast = head.next;

        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}

10. What are weak references and how are they used in WeakHashMap?

import java.util.WeakHashMap;

public class WeakHashMapExample {
    public static void main(String[] args) {
        WeakHashMap<String, String> map = new WeakHashMap<>();
        String key1 = new String("key1");
        String key2 = new String("key2");

        map.put(key1, "value1");
        map.put(key2, "value2");

        System.out.println("Before GC: " + map);
        
        key1 = null; // Remove strong reference to key1
        System.gc(); // Suggest garbage collection

        // Wait for a moment to let GC do its work
        try {
            Thread.sleep(1000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        System.out.println("After GC: " + map);
    }
}

In this example, we create a WeakHashMap and add two key-value pairs. We then remove the strong reference to one of the keys and suggest garbage collection. After garbage collection, the entry with the key that was set to null is removed from the map.

11. Explain the difference between ConcurrentHashMap and synchronizedMap.

ConcurrentHashMap and synchronizedMap are both used to handle concurrent access to a map, but they have different implementations and performance characteristics.

ConcurrentHashMap is part of the java.util.concurrent package and is designed for high concurrency. It allows multiple threads to read and write without locking the entire map. Instead, it uses a finer-grained locking mechanism called lock striping, which divides the map into segments and locks only the segment being accessed. This results in better performance and scalability in multi-threaded environments.

synchronizedMap, on the other hand, is a wrapper provided by the Collections.synchronizedMap() method. It synchronizes the entire map, meaning that every read and write operation requires acquiring a single lock. This can lead to contention and reduced performance when multiple threads try to access the map simultaneously.

12. What is the difference between ArrayList and LinkedList?

ArrayList:

• ArrayList is backed by a dynamic array, providing fast random access to elements (O(1) time complexity for get operations).
• Insertion and deletion operations can be slow (O(n) time complexity) because elements may need to be shifted to maintain the array’s order.
• ArrayList is more memory efficient when it comes to storing data, as it does not have the overhead of storing node pointers.
• It is a better choice when you need fast access to elements and infrequent insertions or deletions.

LinkedList:

• LinkedList is backed by a doubly linked list, meaning each element (node) contains a reference to the previous and next node.
• Insertion and deletion operations are generally faster (O(1) time complexity) because they only involve updating node references.
• Random access to elements is slower (O(n) time complexity) because it requires traversing the list from the beginning or end.
• LinkedList is more memory-intensive due to the overhead of storing node pointers.
• It is a better choice when you need frequent insertions or deletions and do not require fast access to elements.

13. How does the CopyOnWriteArrayList work and when would you use it?

The CopyOnWriteArrayList works by creating a new copy of the underlying array whenever a modification is made. This means that all read operations can proceed without locking, as they are working on a snapshot of the array that does not change. This makes CopyOnWriteArrayList particularly useful in scenarios where the list is mostly read and infrequently modified, such as in caching, event-handling systems, or observer lists.

Example:

import java.util.concurrent.CopyOnWriteArrayList;

public class CopyOnWriteArrayListExample {
    public static void main(String[] args) {
        CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
        list.add("A");
        list.add("B");
        list.add("C");

        // Iterating over the list
        for (String s : list) {
            System.out.println(s);
        }

        // Modifying the list
        list.add("D");

        // Iterating over the list again
        for (String s : list) {
            System.out.println(s);
        }
    }
}

In this example, the CopyOnWriteArrayList allows for safe iteration and modification without the need for explicit synchronization. The first iteration prints the initial elements, and after adding a new element, the second iteration includes the new element.

14. What is the difference between a Queue and a Deque?

A Queue is a collection designed for holding elements prior to processing, following the First-In-First-Out (FIFO) principle. Common implementations include LinkedList and PriorityQueue.

A Deque (Double-Ended Queue) is a more versatile data structure that allows elements to be added or removed from both ends, supporting both FIFO and Last-In-First-Out (LIFO) operations. Common implementations include ArrayDeque and LinkedList.

Key differences:

• Queue: Elements are added at the end and removed from the front (FIFO).
• Deque: Elements can be added or removed from both ends, supporting both FIFO and LIFO operations.
• Use Cases: Queue is typically used for task scheduling and buffering, while Deque is used for scenarios requiring flexible insertion and deletion operations.

15. Explain how the Spliterator works and its advantages over traditional iterators.

Spliterator is an advanced iterator introduced in Java 8, designed to support parallel processing and efficient traversal of elements in a collection. It is part of the java.util package and works seamlessly with the Stream API. Unlike traditional iterators, Spliterator can split a collection into multiple parts, enabling parallel processing and improving performance for large datasets.

Key features of Spliterator include:

• Splitting: Spliterator can divide a collection into multiple parts, allowing for parallel processing.
• Traversal: It supports efficient traversal of elements in a collection.
• Characteristics: Spliterator provides various characteristics such as ORDERED, DISTINCT, SORTED, and SIZED, which help optimize processing.

Example:

import java.util.Arrays;
import java.util.List;
import java.util.Spliterator;

public class SpliteratorExample {
    public static void main(String[] args) {
        List<String> list = Arrays.asList("A", "B", "C", "D", "E", "F");

        Spliterator<String> spliterator1 = list.spliterator();
        Spliterator<String> spliterator2 = spliterator1.trySplit();

        System.out.println("Spliterator 1:");
        spliterator1.forEachRemaining(System.out::println);

        System.out.println("Spliterator 2:");
        spliterator2.forEachRemaining(System.out::println);
    }
}