Arrays and Strings
Arrays give constant time access by index, but inserting or removing from the middle requires shifting elements, which is linear time. Appending to the end is usually constant time on average, though occasionally the underlying storage needs to be resized. Strings behave like arrays of characters in most languages, and many interview problems, like checking for a palindrome or finding a substring, are really array problems in disguise.
Two pointer techniques, where you move indices from both ends or at different speeds through an array, solve a large share of array and string interview problems efficiently, often turning an approach that would otherwise take quadratic time into a linear one.
Hash Maps and Hash Sets
Hash maps give average case constant time lookup, insertion, and deletion, which makes them the go-to structure any time a problem involves checking whether something has been seen before, counting occurrences, or looking up a value by a key quickly. A classic example is the two-sum problem, where a hash map turns an approach that would otherwise take quadratic time into a single linear pass.
Be ready to explain that hash maps trade memory for speed, and that worst case operations can degrade if there are many hash collisions, though this is rarely the focus of interview discussion. Hash sets are the same idea without the associated value, useful for deduplication and fast membership checks.
Stacks and Queues
A stack is last in, first out, and shows up constantly in problems involving matching pairs like parentheses, tracking history for undo functionality, or depth first traversal implemented iteratively. A queue is first in, first out, and is the natural structure for breadth first traversal, task scheduling, and anything that needs to process items in the order they arrived.
A common follow-up is implementing a queue using two stacks or vice versa, which tests whether you actually understand the underlying behavior rather than just the names.
Trees and Graphs
Binary trees, and specifically binary search trees, support efficient search, insertion, and deletion when balanced, all roughly logarithmic time, but degrade toward linear time if the tree becomes skewed. Know the difference between depth first traversal, pre-order, in-order, post-order, and breadth first traversal using a queue, and be able to implement both recursively and iteratively.
- Tries are useful for prefix based string problems like autocomplete
- Graphs are represented as either an adjacency list or an adjacency matrix, and the choice affects the time and space complexity of your algorithm
- Depth first search is good for exploring paths fully, breadth first search is good for finding the shortest path in an unweighted graph
Heaps and Choosing the Right Structure Under Pressure
A heap, usually a binary heap, gives efficient access to the minimum or maximum element and is the structure behind priority queues, useful for problems like finding the k largest elements or merging multiple sorted lists efficiently. Insertion and removal are logarithmic time, while peeking at the top is constant time.
Under interview pressure, the fastest way to choose a structure is to ask what operation you need most: do you need fast lookup by key, use a hash map, do you need order preserved with fast access to both ends, use a queue or deque, do you need the smallest or largest item repeatedly, use a heap, do you need to explore relationships between items, use a graph. Naming this reasoning out loud during the interview also shows the interviewer you are choosing deliberately rather than guessing.
Matching Common Problem Patterns to the Right Structure
Beyond knowing individual structures, recognizing recurring problem patterns speeds up how quickly you can choose the right one under pressure. A sliding window, using two pointers that expand and contract over an array or string with a hash map tracking counts, solves most substring or subarray problems efficiently. Two pointers moving from opposite ends of a sorted array solve problems like finding a pair that sums to a target without needing extra memory.
- Fast and slow pointers moving through a linked list at different speeds detect cycles without extra memory
- Backtracking with recursion handles problems asking for all combinations, permutations, or subsets that satisfy a condition
- Breadth first search finds the shortest path in an unweighted graph or explores a tree level by level
- Depth first search explores full paths, checks connectivity, or detects cycles in a graph
When a new problem looks unfamiliar, checking whether it resembles one of these shapes, rather than starting from a blank mental slate, is often the fastest route to a working approach.
Complexity You Should Be Able to State Instantly
For each core structure, you should be able to state its typical time complexity for common operations without pausing to work it out. Array access is constant time, but inserting into the middle is linear. Hash map lookup, insertion, and deletion are constant time on average. Balanced binary search tree operations are logarithmic. Heap insertion and removal are logarithmic, while peeking at the top is constant. Being able to rattle these off immediately when asked frees up your mental effort for the actual problem instead of the bookkeeping around it.
Choosing Between Two Reasonable Structures
Many interview problems can be solved correctly with more than one data structure, and part of what interviewers are testing is whether you can reason about which one fits better given the specific constraints. If you need to check membership quickly and order does not matter, a hash set usually beats a sorted array, since the sorted array requires a binary search that is slower for repeated lookups unless the data changes rarely. If you need the data to stay sorted as new elements arrive, a heap or a balanced tree often beats repeatedly sorting an array from scratch.
When you are unsure which structure fits better, say both options out loud along with the deciding factor, for example noting that a hash map would be faster here but a sorted structure would be necessary if the problem also required retrieving elements in order. This shows the interviewer you understand the actual tradeoff rather than defaulting to whichever structure you remember most easily.
It is also worth practicing converting between representations quickly, such as turning a list of pairs into an adjacency list for a graph problem, since interview problems often present data in one format while the cleanest solution requires reshaping it into another first.