Choosing the Right Data Structure
Fast recall
Quick revision
Core answer
Knowledge of data structure trade-offs and problem pattern recognition
Always defaulting to arrays without considering if a HashMap or set would be more efficient
Explicitly state why you chose a structure by linking it to the dominant operation needed
Interview-ready guide
Interview answer
I choose a data structure from the operations the algorithm needs. First I check correctness requirements such as ordering, duplicate handling, and whether I need indexed access. Then I compare the cost of the operations that happen most often.
For duplicate detection, I need repeated membership checks, so a HashSet gives expected O(1) lookup and an expected O(n) scan overall, using O(n) additional space. For word frequencies, a HashMap stores each word with its count. If I repeatedly need the smallest element, Java's PriorityQueue exposes the minimum in O(1) and inserts or removes in O(log n). If I need keys in sorted order and range operations, a TreeMap may be a better fit at O(log n) per operation.
I also mention the boundary. A linked list does not make arbitrary middle deletion O(1) if I must first scan to find the node, and a priority queue is not a fully sorted list. The choice is therefore based on the exact operations and constraints, not only on a keyword in the prompt.
Choosing the Right Data Structure
Direct Answer
Match the data structure to the problem's access pattern. Need fast lookups? Use a HashMap. Need ordering? Use a sorted set. Need LIFO? Use a stack. Identify the most frequent operation needed, then choose the structure that performs it in the best time complexity.
Code Example
// Scenario 1: Check if array contains duplicates -> HashSet for O(1) lookup
public boolean hasDuplicates(int[] nums) {
var seen = new HashSet<Integer>();
for (int num : nums) {
if (seen.contains(num)) return true; // O(1) check
seen.add(num);
}
return false;
}
// Scenario 2: Count word frequencies -> HashMap for key-value pairs
public Map<String, Integer> wordFrequencies(List<String> words) {
var freq = new HashMap<String, Integer>();
for (var word : words) {
freq.put(word, freq.getOrDefault(word, 0) + 1); // O(1) update
}
return freq;
}
// Scenario 3: Always process smallest element -> PriorityQueue (min-heap)
public int findKthSmallest(int[] nums, int k) {
var minHeap = new PriorityQueue<Integer>();
for (int num : nums) {
minHeap.offer(num); // maintains sorted order
}
for (int i = 1; i < k; i++) {
minHeap.poll(); // remove k-1 smallest
}
return minHeap.peek(); // kth smallest is now at top
}
// Scenario 4: Reverse a string -> Stack for LIFO
public String reverseString(String s) {
var stack = new Stack<Character>();
for (char c : s.toCharArray()) stack.push(c);
var reversed = new StringBuilder();
while (!stack.isEmpty()) reversed.append(stack.pop());
return reversed.toString();
}
Common Mistakes & Pitfalls
- Defaulting to arrays for everything: Freshers often use arrays even when a HashMap would drop time complexity from O(n-squared) to O(n). If you're scanning an array repeatedly with contains or indexOf, consider a HashSet instead.
- Using TreeSet when HashSet suffices: TreeSet maintains sorted order but is slower (O log n operations) than HashSet (O of 1). Only use TreeSet if you actually need the elements sorted.
- Not justifying your choice: Don't just say I'll use a HashMap. Say I'll use a HashMap because I need O of 1 lookups to check if I've seen this element before. This shows you're thinking about complexity, not just picking randomly.
Check your understanding
Answer these without looking back at the article.
- When would you use a TreeMap instead of a HashMap?
- Can you give an example where switching data structure reduces time complexity significantly?
Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.