Java Toolkit for DSA

In simple words

Half of solving a problem quickly is knowing which Java collection to reach for. You already use many of these at work; here is how they map to DSA ideas and what each operation costs.

Key ideas

• Use ArrayDeque for stacks — the old Stack class is synchronized and legacy.
• Never compare Integer objects with ==. It works for −128..127 (cache) and silently fails above. Use .equals() or unbox to int.
• Sums and products overflow int (max ≈ 2.1 × 10⁹). Use long, and write (long) a * b.
• Comparator trap: (a, b) -> a - b can overflow. Prefer Integer.compare(a, b).
• Arrays.sort(int[]) uses dual-pivot quicksort (not stable); Arrays.sort(Object[]) and Collections.sort use TimSort (stable).
• String concatenation inside a loop is O(n²) because strings are immutable — use StringBuilder.
• Handy map methods: getOrDefault, merge, computeIfAbsent, putIfAbsent.

Operations & cost

Java code

import java.util.*;

// Frequency count in one line
Map<Character, Integer> freq = new HashMap<>();
for (char c : s.toCharArray()) freq.merge(c, 1, Integer::sum);

// Map of lists (adjacency list, grouping)
Map<String, List<String>> groups = new HashMap<>();
groups.computeIfAbsent(key, k -> new ArrayList<>()).add(word);

// Stack and queue
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); stack.pop(); stack.peek();
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(1); queue.poll(); queue.peek();

// Min-heap and max-heap
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
// Heap of int[] sorted by second value
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));

// Sorted map: nearest keys
TreeMap<Integer, String> tm = new TreeMap<>();
Integer floor = tm.floorKey(10);   // largest key <= 10, or null
Integer ceil  = tm.ceilingKey(10); // smallest key >= 10, or null

// Sort 2D array by start time
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

// Safe math
long product = (long) a * b;
int mid = lo + (hi - lo) / 2;      // avoids overflow of (lo + hi)

Spot it when

• Need order + fast lookup → TreeMap.
• Need 'most recent' → ArrayDeque as stack.
• Need 'smallest/largest so far' repeatedly → PriorityQueue.

Interview tip

★ Say why you picked a structure: "I'll use a TreeMap because I need the nearest smaller key in O(log n)." Interviewers score the reasoning, not only the code.