Which data structures appear most often in coding interviews?
Arrays, hash maps, linked lists, trees, graphs, stacks, and queues together account for the majority of coding interview problems at major technology companies. Hash maps and arrays appear in the largest proportion of problems because they underlie the optimal solutions to a wide range of problem types. Mastering these seven structures before moving to more specialized ones is the most efficient preparation strategy.
Data structures form the foundation of every coding interview. A candidate who understands which structure to reach for in a given problem context, why that structure is efficient, and how to implement it correctly will outperform a candidate who has memorized more algorithms but lacks this structural intuition. This guide covers every major data structure tested in technical interviews, with implementation notes, time complexity analysis, and the problem types where each structure excels.
Why Data Structures Are the Core of Coding Interviews
Coding interview problems are essentially exercises in applied data structure selection and algorithm design. The best solution to most interview problems is determined primarily by the data structure choice, not by the specific algorithm used. Once you select the right structure, the algorithm often follows naturally.
"Every time I see a candidate struggle on a medium-difficulty problem, the root cause is almost always a data structure selection issue, not a logic issue. They know how to code, but they do not yet have the intuition for which container fits which problem." — Software Engineer and interview coach, formerly at Google
The time invested in deep understanding of data structures pays dividends across hundreds of different problems. It is more leverage than memorizing specific problem solutions.
Arrays and Dynamic Arrays
Arrays are the most fundamental data structure in programming and appear as a component of solutions to an enormous range of problems.
Key Properties
- Access: O(1) random access by index
- Search: O(n) unsorted, O(log n) if sorted with binary search
- Insertion: O(1) at end (amortized for dynamic arrays), O(n) at arbitrary position
- Deletion: O(n) for arbitrary position, O(1) at end
When to Use Arrays
Use arrays when:
- You need O(1) access by index
- The data has a natural sequential structure
- You need to sort data and perform binary search
- You are implementing a sliding window, two-pointer, or prefix sum approach
Common Array Interview Patterns
Two pointers: Start one pointer at each end and move them toward each other based on conditions. Used for pair sum problems, container with most water, and sorted array problems.
Sliding window: Maintain a window of fixed or variable size that moves across the array. Used for maximum subarray sum, longest substring with constraints, and minimum window problems.
Prefix sum: Precompute cumulative sums to answer range queries in O(1). Used for subarray sum equals k, range sum queries, and equilibrium index problems.
Hash Tables and Hash Maps
Hash maps are the single most universally applicable data structure in interview problems. If you are unsure what structure to use, hash maps are frequently the right answer.
Key Properties
- Lookup: O(1) average, O(n) worst case with collisions
- Insertion: O(1) average
- Deletion: O(1) average
- Space: O(n)
When to Use Hash Maps
Use hash maps when:
- You need to count frequencies of elements
- You need to check membership quickly
- You need to remember a value associated with a key (memoization)
- You are looking for pairs or complements (two sum pattern)
- You need to group elements by a computed property
The Two Sum Problem: Hash Map Archetype
The canonical hash map interview problem is Two Sum: given an array of integers and a target, return indices of two numbers that sum to target. The naive O(n²) solution checks all pairs. The hash map solution is O(n): for each element, check whether the complement (target - current) is already in the map. If not, store the current element in the map. This pattern — iterate and check complement in map — appears in dozens of interview problems.
Linked Lists
Linked lists are tested in interviews primarily to assess pointer manipulation and recursive thinking. They appear less frequently than arrays and hash maps but are a staple of many interview loops.
Key Properties
- Access: O(n) — no random access
- Search: O(n)
- Insertion at head: O(1)
- Insertion at arbitrary position: O(n) to find position, O(1) to insert
- Deletion: O(n) to find, O(1) to remove
Common Linked List Interview Patterns
Fast and slow pointer: Use two pointers moving at different speeds to detect cycles (Floyd's algorithm), find the middle of a list, or find the nth node from the end.
Reversal in place: Reverse all or part of a linked list using three pointers (previous, current, next). This is a foundational operation that appears as a subtask in many problems.
Merge two sorted lists: Standard divide-and-conquer building block used in merge sort and in merge k sorted lists problems.
Trees and Binary Search Trees
Tree problems are among the most commonly asked in interviews and require comfort with both recursive and iterative approaches.
Binary Tree Traversals (Critical to Master)
| Traversal | Order | Use Case |
|---|---|---|
| Inorder | Left, Root, Right | Produces sorted output for BST |
| Preorder | Root, Left, Right | Serialize/deserialize tree, copy tree |
| Postorder | Left, Right, Root | Delete tree, evaluate expression tree |
| Level-order | BFS across levels | Find level-specific properties, minimum depth |
Binary Search Tree Properties
In a valid BST: all nodes in the left subtree have values less than the root, and all nodes in the right subtree have values greater. This property enables O(log n) average search, insertion, and deletion (O(n) in the worst case when the tree degenerates to a linked list).
Common Tree Interview Patterns
Recursive DFS: Most tree problems that operate on subtrees are naturally solved with recursion. The base case is typically the null node.
Iterative with stack: When recursion depth is a concern or you need explicit control over traversal order.
BFS with queue: For level-order traversal, finding minimum depth, or checking balanced properties level by level.
Heaps and Priority Queues
Heaps are underutilized by many candidates but enable elegant solutions to a specific class of problems.
Key Properties
- Find min/max: O(1)
- Extract min/max: O(log n)
- Insert: O(log n)
- Build heap from array: O(n)
When to Use Heaps
Use heaps when:
- You need to repeatedly extract the minimum or maximum element
- You are solving a "k largest" or "k smallest" type problem
- You need to merge k sorted lists
- You are implementing Dijkstra's shortest path algorithm
- You need to maintain a running median
The K Largest Elements Pattern
A common heap pattern: to find the k largest elements in a stream or array, maintain a min-heap of size k. For each new element, if it is larger than the heap minimum, replace the minimum. At the end, the heap contains the k largest elements. This runs in O(n log k), which is significantly better than sorting for large n with small k.
Graphs and Graph Traversal
Graph problems represent one of the most diverse and frequently tested topic areas in technical interviews.
Graph Representation Options
| Representation | Space | Edge Lookup | Best For |
|---|---|---|---|
| Adjacency list | O(V + E) | O(degree) | Sparse graphs (most interview problems) |
| Adjacency matrix | O(V²) | O(1) | Dense graphs, weighted graph operations |
| Edge list | O(E) | O(E) | Kruskal's algorithm, when processing all edges |
BFS vs. DFS for Graphs
BFS (Queue-based): Use when you need the shortest path in an unweighted graph, the minimum number of steps to reach a target, or level-by-level exploration.
DFS (Stack or recursion): Use when you need to detect cycles, explore all paths, check connectivity, or perform topological sorting.
Common Graph Problem Categories
- Connected components: Union-Find or DFS/BFS
- Cycle detection: DFS with coloring (white/gray/black)
- Topological sort: Kahn's algorithm (BFS-based) or DFS post-order
- Shortest path: BFS (unweighted), Dijkstra (weighted, non-negative), Bellman-Ford (negative weights)
- Islands and grids: Grid cells as graph nodes, DFS or BFS for region exploration
Stacks and Queues
Stack Use Cases
Stacks are LIFO structures used for:
- Balanced parentheses problems
- Implementing recursion iteratively
- Monotonic stack problems (next greater element, daily temperatures)
- Browser history and undo operations
Queue Use Cases
Queues are FIFO structures used for:
- BFS traversal
- Task scheduling problems
- Sliding window maximum (deque variant)
- Cache implementation (combined with hash map for LRU Cache)
Trie (Prefix Tree)
Tries are specialized tree structures for string problems.
When to Use Tries
- Word search and dictionary lookup
- Autocomplete functionality
- Prefix-based searches
- IP routing tables
A trie allows O(m) search where m is the length of the search string, which is faster than hash map for prefix queries.
A Data Structure Selection Guide
| Problem Signal | Primary Data Structure | Secondary Consideration |
|---|---|---|
| Need fast lookup by value | Hash map | Set for membership only |
| Need sorted data with fast search | BST or sorted array | Binary search on sorted array |
| Need min or max repeatedly | Heap | Monotonic stack for local min/max |
| Working with paths and connections | Graph | Tree if hierarchical, no cycles |
| String prefix operations | Trie | Hash map for whole-string lookup |
| First in, first out | Queue | Deque for double-ended access |
| Last in, first out | Stack | Recursion call stack |
| Range queries on array | Prefix sum or segment tree | Segment tree for dynamic updates |
Frequently Asked Questions
In what order should I study data structures for interview preparation? Start with arrays and hash maps because they appear in the most problems and many optimal solutions rely on them. Then add trees and graphs, which cover the largest category of interview problems. After that, add heaps, stacks and queues, and linked lists. Tries and specialized structures like segment trees should come last if time permits.
Do I need to implement every data structure from scratch in an interview? Most interviewers do not require from-scratch implementations of standard library structures like heaps or hash maps. You should understand the implementation well enough to explain time and space complexity and to debug if something behaves unexpectedly. For linked lists and trees, implementing from scratch is commonly required.
How important is it to know both recursive and iterative approaches? Very important. Some interviewers specifically ask for one or the other. More importantly, understanding both deepens your comprehension of the structure. If you only know the recursive tree traversal, you will struggle to implement it iteratively when asked — and you will not understand the space complexity implications of your solution.
References
- Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley Professional.
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
- Skiena, S. S. (2008). The Algorithm Design Manual (2nd ed.). Springer.
- Gayle Laakmann McDowell. (2015). Cracking the Coding Interview (6th ed.). CareerCup.
- Adnan Aziz, Tsung-Hsien Lee, & Amit Prakash. (2018). Elements of Programming Interviews in Python. CreateSpace.