Data Structures You Actually Need to Know for Interviews (No Fluff)
I wasted months studying obscure data structures I never saw in interviews. Here are the 8 that actually matter, with exactly what you need to know about each.
When I started studying for interviews, I tried to learn everything. AVL trees, red-black trees, B-trees, skip lists, bloom filters. I thought being thorough would help me.
After 40+ interviews at tech companies, I can count on one hand how many times I needed anything beyond the basics. The reality is: 8 data structures cover 95% of interview questions.
Here's exactly what you need to know about each—operations, complexity, and when to use them.
Quick Reference: Time Complexity
| Structure | Access | Search | Insert | Delete |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) |
| Linked List | O(n) | O(n) | O(1) | O(1) |
| Hash Table | N/A | O(1)* | O(1)* | O(1)* |
| BST (balanced) | O(log n) | O(log n) | O(log n) | O(log n) |
| Heap | O(1) top | O(n) | O(log n) | O(log n) |
| Graph | Varies | O(V+E) | O(1) | O(E) |
*Average case. Worst case O(n) with many collisions.
1. Arrays
What You Need to Know
Key Properties:
- • Contiguous memory → O(1) access by index
- • Fixed size (static) or resizable (dynamic)
- • Insertion/deletion at arbitrary position is O(n)
Common Operations:
arr[i] → O(1) access
arr.append(x) → O(1) amortized (dynamic array)
arr.insert(i, x) → O(n) shift elements
arr.pop() → O(1) from end
arr.pop(0) → O(n) from beginning
Interview Patterns:
Two pointers, sliding window, prefix sums, in-place modifications
2. Hash Tables (Dictionaries/Maps)
What You Need to Know
Key Properties:
- • Key-value storage with O(1) average operations
- • Uses hash function to map keys to buckets
- • Collisions handled by chaining or open addressing
- • Unordered (in most implementations)
Common Operations:
d[key] = value → O(1) insert
d[key] → O(1) access
key in d → O(1) lookup
del d[key] → O(1) delete
d.keys(), d.values() → O(n) iteration
Interview Patterns:
Frequency counting, two sum, grouping anagrams, caching, deduplication
Pro Tip:
When you need O(n²) → O(n), think hash table. Trading space for time.
3. Linked Lists
What You Need to Know
Types:
- • Singly linked: Each node points to next
- • Doubly linked: Points to next and previous
- • Circular: Last node points back to first
Key Properties:
- • O(1) insert/delete if you have the node reference
- • O(n) access (must traverse from head)
- • No random access like arrays
Interview Patterns:
Reverse list, detect cycle (fast/slow pointers), merge sorted lists, find middle
# Reverse linked list
prev, curr = None, head
while curr:
next_temp = curr.next
curr.next = prev
prev, curr = curr, next_temp
return prev
4. Stacks & Queues
What You Need to Know
Stack (LIFO)
- • Last In, First Out
- • push(), pop(), peek() all O(1)
- • Use cases: undo, parsing, DFS
stack = []
stack.append(x) # push
stack.pop() # pop
stack[-1] # peek
Queue (FIFO)
- • First In, First Out
- • enqueue(), dequeue() O(1)
- • Use cases: BFS, scheduling
from collections import deque
q = deque()
q.append(x) # enqueue
q.popleft() # dequeue
Interview Patterns:
Valid parentheses, monotonic stack, level-order traversal, sliding window max
5. Trees
What You Need to Know
Types:
- • Binary Tree: Each node has at most 2 children
- • BST: Left < Node < Right property
- • Balanced BST: Height is O(log n)
- • N-ary Tree: Each node has N children
Traversals (Know These Cold):
Inorder (LNR)
Left → Node → Right
BST: sorted order
Preorder (NLR)
Node → Left → Right
Copy tree, prefix
Postorder (LRN)
Left → Right → Node
Delete tree, postfix
Interview Patterns:
Max depth, validate BST, LCA, serialize/deserialize, path sum
6. Heaps (Priority Queues)
What You Need to Know
Key Properties:
- • Complete binary tree stored as array
- • Min-heap: parent ≤ children (smallest at root)
- • Max-heap: parent ≥ children (largest at root)
- • O(1) access to min/max, O(log n) insert/delete
Common Operations:
import heapq
heapq.heappush(h, x) # O(log n)
heapq.heappop(h) # O(log n) remove min
h[0] # O(1) peek min
heapq.heapify(list) # O(n) build heap
Interview Patterns:
K largest/smallest, merge K sorted lists, median from stream, task scheduler
Python Tip:
Python heapq is min-heap only. For max-heap, negate values: heappush(h, -x)
7. Graphs
What You Need to Know
Representations:
Adjacency List
Space: O(V + E)
graph = {A: [B, C], B: [A]}
Better for sparse graphs
Adjacency Matrix
Space: O(V²)
matrix[i][j] = 1 if edge
Better for dense graphs
Types:
- • Directed vs Undirected
- • Weighted vs Unweighted
- • Cyclic vs Acyclic (DAG)
- • Connected vs Disconnected
Essential Algorithms:
- • BFS: Shortest path (unweighted), level order
- • DFS: Explore all paths, detect cycles, connected components
- • Topological Sort: Dependency ordering (DAG only)
- • Dijkstra: Shortest path (weighted, positive)
8. Tries
What You Need to Know
Key Properties:
- • Tree where each node represents a character
- • Path from root to node = prefix
- • O(m) operations where m = word length
- • Space-efficient for common prefixes
Implementation:
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
Interview Patterns:
Autocomplete, spell checker, word search II, longest common prefix
Apply Data Structures Under Pressure
Knowing data structures is different from applying them under pressure. LastRound AI offers practice problems and AI mock interviews to help you master choosing the right structure and implementing it confidently.
When to Use What
Quick Decision Guide
"Need O(1) lookup" → Hash Table
"Need sorted data with fast insert" → BST / TreeMap
"Need min/max quickly" → Heap
"Need LIFO access" → Stack
"Need FIFO access" → Queue
"Prefix/autocomplete problems" → Trie
"Relationships between entities" → Graph
"Hierarchical data" → Tree
"Need index access" → Array
"Frequent insert/delete in middle" → Linked List
Study Order Recommendation
- Week 1: Arrays, Hash Tables (most common in interviews)
- Week 2: Stacks, Queues, Linked Lists
- Week 3: Trees (binary trees, BST, traversals)
- Week 4: Graphs (BFS, DFS, representations)
- Week 5: Heaps, Tries (less common but important)