Collections in action: the 7 patterns at a glance

For this lesson, we'll focus on the seven patterns that show up constantly in Java interviews and everyday backend code: frequency counting, deduplication, LRU caching, top-K selection, grouping, stack algorithms and range queries. The point is not to memorize class names. The point is to start with the operation, not the collection, then choose the structure whose core operation matches it.

01Picture it first: signal to structure

Think of the problem statement as a set of road signs. "Most frequent" points toward a counter. "Unique" points toward membership. "Next greater" points toward a stack because the newest unresolved item matters first. Once you read the signal correctly, the collection choice becomes much less mysterious.

The picture below is the map I keep in my head before writing code.

Fig. 1

Seven Java collection problem signals mapped to the data structures that usually solve them

Notice two things. First, HashMap appears in more than one pattern because maps are general key-to-state machines. Second, order has a cost: if the prompt cares about sorted order, recency, or priority, expect extra pointers, heap work or tree rotations.

02The seven patterns under the hood

1. Frequency counting with HashMap

Signal words: frequency, occurrences, histogram, count by key, most common, same multiset. Interviewers like this because it tests whether you can replace repeated scanning with one pass of state.

The collection is usually HashMap<K, Integer> for ordinary counts, or Map<K, Long> when a stream collector or very large count is possible. The update operation should be expected O(1), so the whole scan is expected O(n), with O(u) extra space for u unique keys.

Map<String, Integer> frequency = new HashMap<>();
for (String service : List.of("api", "db", "api")) {
    frequency.merge(service, 1, Integer::sum);
}
System.out.println(frequency.get("api")); // 2

Notice that merge handles both the first occurrence and later increments. We cover the choices among merge, getOrDefault, compute and stream collectors in Frequency counting and deduplication.

2. Deduplication with HashSet or LinkedHashSet

Signal words: unique, duplicate, already seen, visited, first time, contains duplicate. This is the pattern behind duplicate detection, graph visited sets and the common "two-sum" seen-set solution.

Use HashSet when order does not matter. Use LinkedHashSet when the output must keep first-seen order. Expected time is O(n), with O(u) extra space.

Set<String> seen = new HashSet<>();
for (String eventId : List.of("e1", "e2", "e1")) {
    if (!seen.add(eventId)) {
        System.out.println("duplicate " + eventId);
    }
}

The trick is that add returns false when an equal element is already present. We go deeper on order, custom objects and dedup by field in Frequency counting and deduplication.

3. LRU cache with access-order LinkedHashMap

Signal words: cache, capacity, evict, least recently used, access recency. The requirement has two moving parts: find by key, then move the entry to the recently used end.

LinkedHashMap can do this because it combines hash lookup with a linked order. In access-order mode, a successful get moves an entry. Each ordinary operation is expected O(1), and the map stores O(capacity) entries.

var cache = new LinkedHashMap<Integer, String>(16, 0.75f, true);
cache.put(1, "home");
cache.put(2, "pricing");
cache.get(1);
System.out.println(cache.keySet()); // [2, 1]

That snippet shows recency, not eviction. The full cache override uses removeEldestEntry, and we build it properly in LinkedHashMap and building an LRU cache.

4. Top-K with a bounded PriorityQueue

Signal words: top K, K largest, K smallest, most frequent K, best K, streaming winners. The mistake is sorting everything when you only need a small frontier.

For K largest values, keep a min-heap of size K. The root is the smallest value currently accepted, so it is the easiest one to evict. Processing costs O(n log k), with O(k) extra space.

PriorityQueue<Integer> top = new PriorityQueue<>();
for (int score : new int[] {17, 4, 30, 9}) {
    top.offer(score);
    if (top.size() > 2) top.poll();
}
System.out.println(top); // contains 17 and 30

A PriorityQueue does not iterate in sorted order. If the output must be sorted, poll repeatedly or sort a copy. The detailed version lives in Top-K with a heap.

5. Grouping with Map<K, List<V>>

Signal words: group by, bucket by, partition, by department, by customer, aggregate per key. Frequency counting stores a number; grouping stores the actual items or a downstream aggregate.

Use a manual loop with computeIfAbsent when validation or side effects matter. Use Collectors.groupingBy when the stream reads clearly. Expected time is O(n), with O(n) space if every item is stored.

Map<String, List<String>> byRegion = new HashMap<>();
for (String order : List.of("west:A1", "east:B2", "west:C3")) {
    String region = order.substring(0, order.indexOf(':'));
    byRegion.computeIfAbsent(region, key -> new ArrayList<>()).add(order);
}

Notice the empty list is created only for the first order in a region. Counts, sums, partitions and group ordering are covered in Grouping and partitioning.

6. Stack algorithms with ArrayDeque

Signal words: nested, most recent, matching, undo, backtrack, next greater, previous smaller. A stack is right when the latest unresolved thing must be resolved first.

Use ArrayDeque as a stack for ordinary single-threaded code. Prefer it over legacy Stack; Stack extends Vector and brings old synchronized methods and an awkward inherited API. A scan is usually O(n), with O(n) worst-case stack space.

Deque<Character> stack = new ArrayDeque<>();
for (char ch : "([])".toCharArray()) {
    if (ch == '(' || ch == '[') stack.push(ch);
    else if (stack.isEmpty()) System.out.println("bad");
    else stack.pop();
}
System.out.println(stack.isEmpty()); // true

Real bracket validation checks the matching type, not only balance. We do that, plus monotonic stacks, in Stack algorithms with ArrayDeque.

7. Range queries with TreeMap

Signal words: nearest, next, previous, floor, ceiling, between, at least, at most, sorted by key. Exact lookup is not enough here; the order of keys is the point.

TreeMap implements NavigableMap, so it gives predecessor, successor and range views in O(log n) navigation time. Iterating m entries in a range costs O(m) after the view is positioned.

TreeMap<Integer, String> slots = new TreeMap<>();
slots.put(10, "A"); slots.put(30, "B"); slots.put(50, "C");
System.out.println(slots.floorKey(34));   // 30
System.out.println(slots.subMap(10, true, 30, true));

subMap, headMap and tailMap return backed views, not isolated copies. We unpack those edge cases in Range queries with TreeMap.

03Cross-pattern comparison

Here is the table I'd use for a quick design review. The "signal" column matters most because it keeps you from starting with a favorite class.

A few definitions: n is input size, u is number of unique values, and k is the requested top-K size. Hash-based costs are expected costs under normal hash distribution. If the interviewer pushes on worst case, mention hash collisions and tree bins for HashMap.

04A practical decision framework

Start with this sequence in an interview or code review. It keeps you honest.

1. What must be fast? Membership, counting, grouping, recency, priority, LIFO or sorted navigation?
2. Does order matter? No order, first-seen order, access order, priority order and sorted key order are different contracts.
3. Are duplicates meaningful? Top-K may keep duplicate values; a set destroys them.
4. How big is K compared with n? A heap shines when K is much smaller than n. If K is close to n, sorting may be clearer.
5. Is the data shared across threads? None of these default choices magically become safe for concurrent mutation.
6. What are the edge cases? Nulls, ties, invalid K, mutable keys, duplicate timestamps and backed views all change code.
7. What should the output guarantee? An unordered correct set is different from a descending list with deterministic tie-breaking.

05Common mistakes checklist

Many candidates know the names but lose points on the contract. Use this as a pre-submit checklist.

1. Assuming HashMap or HashSet preserves iteration order.
2. Overriding equals() without also implementing hashCode().
3. Mutating fields used by equals() or hashCode() after insertion into a hash collection.
4. Assuming a PriorityQueue iterates in sorted order.
5. Using the wrong heap direction for top-K, especially a max-heap for K largest when a bounded min-heap is clearer.
6. Forgetting whether top-K should count duplicate values and how ties should be resolved.
7. Forgetting that TreeMap.subMap() and friends are usually backed views.
8. Treating access-order LinkedHashMap as a thread-safe production cache.
9. Storing full lists when a count, sum or boolean partition is all the problem needs.
10. Ignoring null behavior, invalid input and version differences such as Stream.toList() being available since Java 16.

06How to say it in the interview

When I ask this, I'm listening for three things: you identify the operation first, you pick the smallest fitting structure, and you state the trade-off without pretending expected O(1) is a law of physics.