Collections interview (Java)

The collections framework in Java provides data structures to store and manipulate groups of objects efficiently, overcoming the limitations of fixed-size arrays. A solid grasp of collections is essential for writing optimized code and is a frequent topic in technical interviews. Let's quickly review the fundamentals.

Core Interfaces

The Java Collections Framework (JCF) is built around a set of core interfaces. You will almost always work with collections through these interfaces to keep your code flexible.

While we'll focus on the standard, single-threaded implementations, the JCF also includes concurrent-aware implementations designed for safe use in multi-threaded applications.

• List: An ordered collection that maintains the insertion order of elements. It allows duplicate elements and gives you precise control over where is the list each element is inserted. Users can access elements by their integer index and search for elements in the list. (The List interface)

  • ArrayList is your go to implementation, backed by a dynamic (resizable) array. ArrayList has a capacity, which is the size of its internal array. As you add elements, this capacity grows automatically. Adding an element to the end is typically an O(1) operation. However, if the internal array is full, it must be resized (a new larger array is created and all elements are copied over), which is an O(n) operation. Over many additions, this averages out, giving add an amortized constant time O(1). Operations like get, set, and size run in constant time. (ArrayList)

  • LinkedList is a doubly-linked list implementation of the List and Deque interfaces (we'll cover Deque shortly). Each element is a node that holds the actual data along with references to the previous and next nodes. Operations that index into list will traverse it from the beginning or end, whichever is closer. This makes it a better choice when you have a larger number of frequent insertions and deletions, especially at the ends of the list. (LinkedList)

  • Read more: LinkedList vs. ArrayList

  ArrayList and LinkedList are not synchronized. If multiple threads access them concurrently, and at least one thread modifies the list, it must be synchronized externally.

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

  List<String> names = new ArrayList<>();
  names.add("Duke");
  names.add("James");
  String first = names.get(0); // "Duke"
  

• Set: A collection that holds only unique elements. The uniqueness is determined by the element's equals() and hashCode() methods. The contract is critical: if two objects are equal according to a.equals(b), then their hashCode() must return the same integer. Failing to uphold this when using custom objects can lead to unpredictable behaviour. (The Set interface)

  • HashSet is the most common implementation, offering the best performance for general use. It is backed by a HashMap, where the elements of the Set are stored as keys in the map, and a constant placeholder object is used as the value. This allows for constant-time O(1) for add, remove, and contains operations, assuming a good hash function that distributes elements evenly across the internal "buckets". HashSet makes no guarantees about iteration order. (Introduction to HashSet, HashSet internals)

  • TreeSet stores its elements in a sorted order, making it ideal when you need to maintain a unique, sorted collection. It is backed by a TreeMap (which uses a self-balancing binary search tree, specifically a Red-Black tree). This guarantees log(n) time for add, remove, and contains. The sorting is based on either the elements' "natural ordering" (if they implement the Comparable interface) or a custom Comparator supplied at the set's creation. (TreeSet)

  • LinkedHashSet is a blend of HashSet and LinkedList. It uses a hash table for fast lookups (like HashSet) but also maintains a doubly-linked list running through all its entries. This linked list preserves the insertion order of the elements. The result is a Set that iterates in a predictable order without the performance overhead of the sorting required by TreeSet. (LinkedHashSet)

  Like the List implementations we covered, these Set implementations are not synchronized are required external synchronization for concurrent use.

  Set<String> languages = new HashSet<>();
  languages.add("Java");
  languages.add("Kotlin");
  languages.add("Java"); // This will be ignored
  boolean hasJava = languages.contains("Java"); // true
  

• Queue and Deque: Collections designed for holding elements prior to processing.

  A Queue is designed for First-In, First-Out (FIFO) processing. The interface provides two sets of methods for core operation: one set throws an exception if the operation fails (e.g., removing from an empty queue), while the other returns a special value like null or false. The latter is useful for capacity-restricted queues where failing to add an element is a normal condition, not an exceptional one. (Queue)

  A Deque is a "double-ended queue" that allows for efficient insertion and removal from both ends. This makes it incredibly versatile. It can function as a standard FIFO queue (by adding to the end and removing from the front) or as a Last-In, First-Out (LIFO) stack. (Deque general overview)

  • ArrayDeque is the recommended implementation for both Queue and Deque. It is backed by a resizable, circular array, which allows it to efficiently add and remove elements from both ends in amortized constant time. It is generally faster than LinkedList because it avoids the overhead of creating node objects for every element. (ArrayDeque)

  // 1. Using ArrayDeque as a FIFO Queue
  Queue<String> taskQueue = new ArrayDeque<>();
  taskQueue.offer("Task 1: Code review");
  taskQueue.offer("Task 2: Write tests");
  // taskQueue is now ["Task 1: Code review", "Task 2: Write tests"]
  
  // Retrieving and removing "Task 1: Code review"
  String nextTask = taskQueue.poll();
  // taskQueue now contains only ["Task 2: Write tests"]
  System.out.println("Next up: " + taskQueue.peek());
  // Output: "Next up: Task 2: Write tests"
  
  // 2. Using ArrayDeque as a LIFO Stack
  Deque<String> browserHistory = new ArrayDeque<>();
  browserHistory.push("google.com");      // Add to the front
  browserHistory.push("hyperskill.org");  // Add to the front again
  // browserHistory is now ["hyperskill.org", "google.com"]
  
  //  Retrieving and removing "hyperskill.org"
  String lastVisited = browserHistory.pop(); 
  // browserHistory now contains only ["google.com"]
  System.out.println("Last page: " + lastVisited);
  // Output: "Last page: hyperskill.org"
  

• Map: An object that maps unique keys to values. While part of the JCF, Map does not extend the Collection interface. (The Map interface)

  Great care must be taken if mutable objects are used as map keys. The behavior of a map is not specified if an object's value is changed in a way that affects equals() comparisons while it is a key in the map.

  • HashMap is the most widely used Map implementation. It uses a key's hashCode() to find a "bucket" (an index in an internal array) where the key-value entry is stored. If multiple keys hash to the same bucket (a collision), their entries are stored in a list or, if the list grows too long, a balanced tree within that bucket. This mechanism provides an impressive O(1) average time complexity for get and put operations. HashMap does not guarantee any iteration order. (HashMap)

  • TreeMap keeps its keys in a sorted order, backed by a Red-Black tree. This guarantees log(n) performance for containsKey, get, put, and remove operations. It's the ideal choice when you need to iterate over the keys in a sorted manner. (TreeMap)

  • LinkedHashMap maintains the insertion order of its entries by combining a hash table with a doubly-linked list. It provides the near O(1) performance of HashMap but with the benefit of predictable, ordered iteration. A special constructor allows it to be configured to order entries by their last access time, making it a powerful tool for building LRU (Least Recently Used) caches. (LinkedHashMap)

  These Map implementations are not synchronized. For concurrent use, consider ConcurrentHashMap or use Collections.synchronizedMap().

  Map<String, Integer> userScores = new HashMap<>();
  userScores.put("Michael", 100);
  userScores.put("John", 85);
  int michaelsScore = userScores.get("Michael"); // 100
  

Common Operations with Streams

Java 8 introduced the Stream API, a powerful tool for processing collections in a functional style. It makes code more declarative and readable.

• Filtering: Select elements that match a condition. (Stream filtering)

  List<Integer> numbers = List.of(1, 2, 3, 4, 5, 6);
  List<Integer> evens = numbers.stream()
          .filter(n -> n % 2 == 0)
          .collect(Collectors.toList()); // [2, 4, 6]
  

  If you're using Java 16 or newer, you can use the more concise .toList() shortcut, which returns an immutable list.

• Transforming (Mapping): Convert each element into a new element. (Map and flatMap)

  List<String> words = List.of("short", "long");
  List<Integer> lengths = words.stream()
          .map(String::length)
          .collect(Collectors.toList()); // [5, 4]
  

• Collecting & Grouping: Accumulate stream elements into a collection. Grouping is a powerful way to categorize elements. (Collectors, Grouping collectors)

  List<String> fruits = List.of("Apple", "Mango", "Avocado", "Melon");
  Map<Character, List<String>> groupedFruits = fruits.stream()
          .collect(Collectors.groupingBy(s -> s.charAt(0)));
  // {A=[Apple, Avocado], M=[Mango, Melon]}
  

• Reducing: Combine all elements into a single result. (Reduction methods)

  List<Integer> costs = List.of(10, 20, 30);
  int totalCost = costs.stream()
          .reduce(0, (sum, cost) -> sum + cost); // 60
  

Final thoughts

Mastering Java collections is vital for any developer. During an interview, be prepared to explain not just what each collection does, but also why you would choose one over another for a specific task. This brief review should serve as a good starting point for your preparation.

Remember to check out the links for more in-depth knowledge and practice solving problems.