Here's a secret that top interview coaches won't charge you $500 to learn: roughly 90% of coding interview problems revolve around just seven data structures. If you deeply understand when and why to reach for each one, you've already won half the battle. The other half is practice — but without the right mental models, practice is just memorisation. This lesson gives you the map so every problem you encounter feels like familiar territory.
Every technical interview draws from the same well. Here are the structures you'll encounter, ranked by frequency:
| Data Structure | Interview Frequency | Core Operations | When Interviewers Expect It | |---|---|---|---| | Arrays / Strings | ★★★★★ | Access O(1), Search O(n), Insert O(n) | Almost every problem starts here | | Hash Maps / Sets | ★★★★★ | Insert O(1), Lookup O(1), Delete O(1) | "Optimise this from O(n²) to O(n)" | | Linked Lists | ★★★★☆ | Insert O(1), Delete O(1), Access O(n) | Pointer manipulation, cycle detection | | Stacks & Queues | ★★★★☆ | Push/Pop O(1), Enqueue/Dequeue O(1) | Parsing, BFS, undo operations | | Trees (Binary, BST) | ★★★★☆ | Search O(log n), Insert O(log n) | Hierarchical data, sorted operations | | Graphs | ★★★☆☆ | Depends on representation | Relationships, paths, connectivity | | Heaps | ★★★☆☆ | Insert O(log n), Extract-min O(log n) | "Find the k largest/smallest" |
Arrays are the starting point for almost every interview problem. The key insight is that most array problems aren't really about arrays — they're about recognising patterns like two pointers, sliding window, or prefix sums.
# Two Sum — the most classic interview problem
# "Given an array and target, find two numbers that add to target"
def two_sum(nums, target):
seen = {} # Hash map to store complement
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
# Time: O(n), Space: O(n) — trading space for time
Notice how even this "array" problem is really a hash map problem. That pattern repeats constantly: the brute force uses nested loops over an array, and the optimal solution introduces a hash map.
If you're stuck on any problem and the brute force is O(n²), ask yourself: "Can a hash map reduce this to O(n)?" The answer is yes surprisingly often.
Sign in to join the discussion
Hash maps shine when you need to:
// Group Anagrams — a classic hash map problem
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String s : strs) {
char[] chars = s.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(map.values());
}
Linked list problems test your ability to manipulate pointers without losing track of nodes. The three techniques you need are:
# Detect a cycle in a linked list (Floyd's Algorithm)
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
Stacks (LIFO) and queues (FIFO) are simpler structures, but they unlock entire categories of problems:
# Valid Parentheses — classic stack problem
def is_valid(s: str) -> bool:
stack = []
matching = {')': '(', '}': '{', ']': '['}
for char in s:
if char in matching:
if not stack or stack[-1] != matching[char]:
return False
stack.pop()
else:
stack.append(char)
return len(stack) == 0
Tree problems typically involve recursion and one of three traversal orders (in-order, pre-order, post-order). The mental model to develop is: "What do I need from the left subtree, the right subtree, and how do I combine them at the current node?"
# Maximum depth of a binary tree — the template for tree recursion
def max_depth(root):
if not root:
return 0
left_depth = max_depth(root.left)
right_depth = max_depth(root.right)
return 1 + max(left_depth, right_depth)
BST (Binary Search Tree) problems add one crucial property: in-order traversal yields sorted elements. If you see "sorted" and "tree" in the same problem, think BST immediately.
Graph problems feel intimidating but most reduce to BFS or DFS once you've built the adjacency list. The key skills are:
# BFS shortest path in an unweighted graph
from collections import deque
def shortest_path(graph, start, end):
queue = deque([(start, 0)])
visited = {start}
while queue:
node, distance = queue.popleft()
if node == end:
return distance
for neighbour in graph[node]:
if neighbour not in visited:
visited.add(neighbour)
queue.append((neighbour, distance + 1))
return -1 # Not reachable
Whenever a problem says "find the K largest", "K closest", or "merge K sorted lists", a heap (priority queue) is almost certainly the answer. In Python, heapq provides a min-heap; for a max-heap, negate the values.
import heapq
# Find the K largest elements in an array
def k_largest(nums, k):
return heapq.nlargest(k, nums) # Uses a min-heap of size k internally
You need to find the median of a stream of numbers in O(log n) per insertion. Which data structure combination is most appropriate?
| Structure | Access | Search | Insert | Delete | Space | |---|---|---|---|---|---| | Array | O(1) | O(n) | O(n) | O(n) | O(n) | | Hash Map | — | O(1)* | O(1)* | O(1)* | O(n) | | Linked List | O(n) | O(n) | O(1) | O(1) | O(n) | | Stack/Queue | O(n) | O(n) | O(1) | O(1) | O(n) | | BST (balanced) | O(log n) | O(log n) | O(log n) | O(log n) | O(n) | | Heap | — | O(n) | O(log n) | O(log n) | O(n) |
* Average case; worst case is O(n) due to hash collisions.
Develop this mental checklist when reading a problem: