Data Structures You Must Know for Interviews

Every coding interview problem is ultimately about choosing the right data structure and applying the right operations to it. You do not need to know every data structure that exists — but you need to deeply understand the core ones. Knowing when to use a hash map versus a tree versus a heap is the difference between a clean O(n) solution and a struggling O(n²) attempt.

This guide covers the data structures that appear most frequently in coding interviews, what you need to know about each one, and how they show up in actual interview problems.

Why they matter

Arrays and strings are the most common data structures in interview problems. Nearly every interview starts with an array or string problem. You need to be completely fluent with array operations in your language: indexing, slicing, iteration, sorting, and searching. For strings, know how to iterate through characters, compare substrings, and handle immutability if your language has immutable strings.

Key techniques

Two pointers: use two indices moving toward each other or in the same direction to solve problems in O(n) time. Sliding window: maintain a window of elements and slide it across the array to find subarrays or substrings meeting a condition. Prefix sums: precompute cumulative sums to answer range queries in O(1). These three techniques cover a large percentage of array and string problems.

Common interview problems

Two sum, valid palindrome, longest substring without repeating characters, container with most water, merge intervals. If you can solve these fluently, you have a solid foundation in array and string manipulation.

Why they matter

Hash maps provide O(1) average-case lookup, insertion, and deletion. This makes them the go-to data structure when you need to check membership, count occurrences, or associate keys with values. If your solution involves searching for something repeatedly, a hash map almost certainly improves it.

Key techniques

Frequency counting: count occurrences of elements to detect duplicates, find the most common element, or check if two collections are anagrams. Index tracking: store the index of elements as you iterate to solve problems like two sum in a single pass. Grouping: group elements by a shared property (like sorted character order for anagrams).

When to use sets instead

When you only care about presence (not associated values), use a set. Sets are cleaner for membership checks, deduplication, and intersection/union operations. If you find yourself creating a hash map where every value is true or 1, you should be using a set.

Stacks

Stacks follow last-in-first-out ordering. Use them when you need to track nested structures (matching parentheses, nested function calls), implement undo operations, or process elements in reverse order. The monotonic stack pattern — maintaining a stack where elements are always increasing or decreasing — solves problems like "next greater element" and "largest rectangle in histogram" efficiently.

Queues

Queues follow first-in-first-out ordering. They are essential for breadth-first search (BFS) in graphs and trees. Whenever you need to process elements in the order they were encountered, use a queue. The deque (double-ended queue) extends this by allowing efficient insertion and removal at both ends, which is useful for sliding window problems.

Binary trees

Most tree problems in interviews involve binary trees. You need to know all three traversal orders (in-order, pre-order, post-order) and be able to implement them both recursively and iteratively. Common operations include finding the height, checking if a tree is balanced, finding the lowest common ancestor, and serializing/deserializing.

Binary search trees

A BST maintains the invariant that all left descendants are smaller and all right descendants are larger. This enables O(log n) search, insertion, and deletion. Know how to validate a BST (the common mistake is checking only immediate children rather than maintaining a valid range), and how in-order traversal of a BST produces sorted output.

Tries

A trie (prefix tree) stores strings character by character. It enables O(m) lookup where m is the string length, regardless of how many strings are stored. Tries appear in problems involving autocomplete, prefix matching, and word search. Know how to implement insert and search operations.

Representations

Know both adjacency list and adjacency matrix representations. Adjacency lists use less space for sparse graphs and are the default choice in interviews. Many interview problems present graphs implicitly — a grid, a list of connections, or a set of dependencies — so practice recognizing when a problem is actually a graph problem.

Traversal

BFS and DFS are the two fundamental graph traversal algorithms. BFS finds the shortest path in unweighted graphs and processes nodes level by level. DFS explores as deep as possible before backtracking and is useful for detecting cycles, topological sorting, and finding connected components. You should be able to implement both from memory.

Common patterns

Detect cycles in directed and undirected graphs. Find connected components. Topological sort for dependency ordering. Shortest path with BFS (unweighted) or Dijkstra (weighted). These patterns cover the majority of graph problems in interviews.

A heap (priority queue) gives you O(1) access to the minimum or maximum element and O(log n) insertion and removal. Use heaps when you need the k-th largest or smallest element, when you need to process elements by priority, or when you need to efficiently merge sorted lists. The top-k pattern — maintaining a heap of size k — is one of the most useful interview techniques.

Know how to use your language's built-in heap implementation. In Python, use heapq. In Java, use PriorityQueue. In JavaScript, you may need to implement your own since there is no built-in heap, though this is rare in interviews.

Do not try to learn all data structures at once. Start with arrays and hash maps, which cover the most interview problems. Then add stacks, queues, and trees. Finally, add graphs and heaps. For each data structure, solve 5 to 10 problems that use it before moving to the next one.

The goal is not to memorize implementations but to build intuition for when to use each structure. When you see a new problem, you should immediately think: "This looks like a hash map problem" or "I need a BFS here." Phantom Coder can accelerate this process by providing real-time analysis of problems, helping you see which data structure fits before you commit to an approach.