Data Structures Interview Questions: The Complete 2026 Guide

TL;DR

• Coding interviews are 70 percent data structures, and ten core structures cover almost every question you will see.
• Master arrays, strings, linked lists, stacks, queues, hash tables, trees, heaps, graphs, and tries cold, with their complexity profiles and canonical patterns (two pointers, sliding window, BFS/DFS, monotonic stack, top-K heap).
• Pattern recognition under one minute beats grinding 500 LeetCode problems without retention.

Introduction

Coding interviews are 70 percent data structures. Every "dynamic programming" problem is secretly about a 2D array. Every "design" problem is secretly about hash maps, heaps, and queues. If you want to stop grinding LeetCode and start pattern-matching, internalise the ten data structures below cold. This guide covers the questions, the patterns, and the complexity trade-offs interviewers expect you to state out loud.

Table of Contents

• The Ten Structures You Must Know Cold
• Arrays and Strings
• Linked Lists
• Stacks and Queues
• Hash Tables
• Trees
• Heaps (Priority Queues)
• Graphs
• Tries
• Disjoint Set Union (Union-Find)
• Segment Trees and Fenwick Trees
• How Interviewers Grade Your Answers
• FAQ
• Conclusion

The Ten Structures You Must Know Cold

For each structure you should be able to answer these five questions without hesitation:

1. What are the time complexities for insert, delete, lookup, and iterate?
2. What is the space overhead?
3. What is the canonical use case?
4. What is the anti-pattern? When should you NOT use it?
5. Can you implement it from scratch in 10 minutes?

If you cannot answer all five for any structure on this list, that is your next study target.

Arrays and Strings

Arrays are asked in roughly 35 percent of all coding interviews, which makes them the single most common topic. The canonical patterns are:

• Two pointers. Example: reverse an array in place, remove duplicates from a sorted array, container with most water.
• Sliding window. Example: longest substring without repeating characters, minimum window substring, longest substring with at most k distinct characters.
• Prefix sums. Example: subarray sum equals K, range sum query.
• Binary search. Example: search in rotated sorted array, find peak element, find minimum in rotated array.

Sample questions that come up often:

1. Two Sum (LC 1): O(n) with a hash map.
2. Three Sum (LC 15): O(n^2) with sort + two pointers.
3. Container With Most Water (LC 11): O(n) with two pointers.
4. Longest Substring Without Repeating Characters (LC 3): O(n) with sliding window and a hash set.
5. Trapping Rain Water (LC 42): O(n) with two pointers or a stack.

Complexity you must state: index access O(1), push/pop at the end O(1) amortized, insert/delete in the middle O(n).

Linked Lists

Linked lists are asked less frequently than arrays, but when they come up, the solution is almost always one of three patterns.

• Fast and slow pointers. Example: detect a cycle (Floyd's algorithm), find the middle node, find the Nth node from the end.
• Dummy head node. Lets you avoid special cases when the head changes. Example: remove duplicates, merge two sorted lists.
• In-place reversal. Example: reverse a linked list, reverse every k nodes, reverse a sublist between positions m and n.

Sample questions:

1. Reverse Linked List (LC 206): O(n) time, O(1) space iterative.
2. Linked List Cycle (LC 141): O(n) time, O(1) space with Floyd's.
3. Merge Two Sorted Lists (LC 21): O(n+m) time.
4. Reorder List (LC 143): find middle, reverse second half, merge.
5. LRU Cache (LC 146): doubly linked list + hash map.

Complexity: access by index is O(n). Insert and delete at known position O(1). Search O(n).

Stacks and Queues

Stack and queue problems reduce to recognising when the "last in, first out" or "first in, first out" ordering matches the problem structure.

Stack patterns:

• Monotonic stack for "next greater/smaller element" problems.
• Parenthesis matching for validation and calculator problems.
• Call stack simulation for converting recursion to iteration.

Queue patterns:

• BFS traversal on a graph or tree.
• Sliding window maximum (double-ended queue).
• Task scheduling with timestamps.

Sample questions:

1. Valid Parentheses (LC 20): classic stack.
2. Min Stack (LC 155): two stacks or one stack of pairs.
3. Daily Temperatures (LC 739): monotonic decreasing stack.
4. Sliding Window Maximum (LC 239): deque.
5. Implement Queue using Stacks (LC 232): two stacks.

Hash Tables

Hash tables are the "free pass" of coding interviews. When a problem mentions "count", "group", "find duplicates", or "match pairs", reach for a hash map first.

Patterns:

• Frequency counting. Example: first unique character, valid anagram, group anagrams.
• Prefix lookups. Example: two sum, subarray sum equals K.
• Set membership. Example: longest consecutive sequence, happy number.

Sample questions:

1. Group Anagrams (LC 49): hash map with sorted-string keys.
2. Longest Consecutive Sequence (LC 128): O(n) with a hash set.
3. Valid Anagram (LC 242): frequency map.
4. Subarray Sum Equals K (LC 560): prefix sum + hash map.
5. Happy Number (LC 202): hash set for cycle detection.

Complexity: average O(1) insert, delete, lookup. Worst case O(n) if you hit a pathological hash collision chain. In interviews state average case unless the problem specifies adversarial input.

Trees

Trees appear in roughly 25 percent of interviews. Almost every tree problem is solved with one of four traversals.

• Depth-first search (DFS): preorder, inorder, postorder. Use recursion or a stack.
• Breadth-first search (BFS): level-order with a queue.
• Divide and conquer: solve the problem on each subtree, combine.
• Morris traversal: O(1) space inorder traversal using tree threading. Rare but impressive.

Sample questions:

1. Maximum Depth of Binary Tree (LC 104): DFS recursion, one-liner.
2. Binary Tree Level Order Traversal (LC 102): BFS with a queue.
3. Lowest Common Ancestor (LC 236): recursive DFS.
4. Serialize and Deserialize Binary Tree (LC 297): BFS with null markers.
5. Validate Binary Search Tree (LC 98): inorder traversal must be strictly increasing.

Complexity: most tree operations are O(n). Balanced BST operations are O(log n).

Heaps (Priority Queues)

Heaps are your go-to for "kth smallest/largest" and "top k" problems, and for anything resembling Dijkstra's shortest path.

Patterns:

• Top-k problems. Example: top k frequent elements, kth largest in a stream.
• Two-heap pattern. Example: median from a data stream (a max-heap for the lower half, min-heap for the upper half).
• Scheduling. Example: task scheduler, meeting rooms II.

Sample questions:

1. Kth Largest Element in an Array (LC 215): min-heap of size k.
2. Top K Frequent Elements (LC 347): bucket sort or min-heap.
3. Find Median from Data Stream (LC 295): two heaps.
4. Meeting Rooms II (LC 253): min-heap on end times.
5. Merge K Sorted Lists (LC 23): min-heap on list heads.

Complexity: insert O(log n), extract min O(log n), peek min O(1), build heap from n items O(n).

Graphs

Graph questions appear in 15 percent of interviews. The structure is one of: adjacency list (most common), adjacency matrix (for dense graphs), or edge list (rare).

Patterns:

• DFS and BFS for traversal, connected components, cycle detection.
• Topological sort for ordering problems with dependencies.
• Dijkstra's algorithm for shortest path in a weighted graph with non-negative edges.
• Union-Find for connectivity and cycle detection.

Sample questions:

1. Number of Islands (LC 200): DFS or BFS.
2. Course Schedule (LC 207): topological sort, cycle detection.
3. Clone Graph (LC 133): BFS with a hash map.
4. Network Delay Time (LC 743): Dijkstra's with a priority queue.
5. Word Ladder (LC 127): BFS on the word graph.

Tries

Tries are used for prefix-based problems. They are rare in interviews but memorable when they show up.

Sample questions:

1. Implement Trie (LC 208): insert, search, startsWith.
2. Word Search II (LC 212): trie + DFS on a grid.
3. Design Add and Search Words (LC 211): trie with wildcard support.
4. Replace Words (LC 648): build a trie of roots, replace each word.
5. Longest Word in Dictionary (LC 720): trie + BFS.

Complexity: insert O(L) where L is word length. Search O(L). Space O(total characters).

Disjoint Set Union (Union-Find)

Union-find is a specialised structure that appears in about 5 percent of interviews, but when it does appear, the problem is almost impossible to solve cleanly without it.

Patterns:

• Path compression and union by rank for near-constant operations.
• Detecting cycles in an undirected graph.
• Grouping disjoint sets (Kruskal's MST).

Sample questions:

1. Number of Provinces (LC 547).
2. Redundant Connection (LC 684).
3. Accounts Merge (LC 721).
4. Graph Valid Tree (LC 261).

Segment Trees and Fenwick Trees

These are senior-engineer-level structures. Interviews at Google L5 and Meta E6 and above occasionally ask them. If you are interviewing at L4 or below, you can skip this section.

Segment tree: O(log n) range updates and queries. Fenwick tree (BIT): simpler than segment trees, O(log n) prefix-sum updates and queries.

Sample questions:

1. Range Sum Query Mutable (LC 307).
2. Count of Smaller Numbers After Self (LC 315).

How Interviewers Grade Your Answers

The interviewer is grading you on four axes. If you miss any of them, your score drops.

1. Did you ask clarifying questions? One or two is enough.
2. Did you state your approach before coding? If not, you look like you are guessing.
3. Did you state the time and space complexity? Both must be stated, not just "this is O(n log n)".
4. Did you test your code on a small example? Skipping this is the most common reason good coders fail otherwise-solved problems.

Frequently Asked Questions

How many LeetCode problems should I solve before interviews?

For a FAANG target, 150 to 250 well-understood problems is a good target. Less if they are spread across all ten data structures above. Volume matters less than pattern coverage.

Are tries and segment trees worth studying for L3/L4 interviews?

Tries yes, segment trees no. Tries appear often enough in system design discussions that you should at least know the API.

Which language should I use?

Python for readability in interview time. Java or C++ if you are applying to a performance-critical team that says so in the job description.

Should I memorise the complexities?

Yes. Interviewers lose faith in candidates who fumble basic complexity claims.

Conclusion

Mastering data structures is not about knowing 500 LeetCode problems. It is about internalising the ten structures above so completely that you recognise the pattern in under a minute. The candidates who get offers treat each new problem as a lookup into an existing library. Build that library once, reuse it forever.

Frequently asked questions

Which data structures appear most often in FAANG coding interviews?

Arrays and strings dominate at roughly 35 percent of problems, followed by trees at around 25 percent and graphs at 15 percent. Hash tables thread through almost every category as the default for counting, grouping, and prefix lookups. Heaps appear on top-K and scheduling problems, while tries, union-find, and segment trees show up at lower frequency but are decisive when they do.

How many LeetCode problems should I solve to be FAANG-ready?

For a FAANG target, aim for 150 to 250 well-understood problems spread across the ten core data structures rather than 500 superficial reps. Volume matters less than pattern coverage. If you can recognize the pattern (two pointers, sliding window, top-K heap, topological sort) in under a minute, your problem count is high enough.

When should I use a monotonic stack versus a heap for an interview problem?

Reach for a monotonic stack when the problem asks for the next greater or smaller element, daily temperatures, or histogram-style spans where you process items in order and need O(n) overall. Use a heap when the problem asks for top-K, kth largest, median from a stream, or any priority-based scheduling where you need O(log n) inserts and extractions.

Are tries and segment trees worth studying for L3 or L4 interviews?

Tries yes, segment trees mostly no. Tries appear in prefix-search and word-dictionary problems often enough that you should know the API and be able to implement insert and search in ten minutes. Segment trees and Fenwick trees are senior-level (Google L5+, Meta E6+); below that, time is better spent on graph and DP fluency.

What time complexities do interviewers expect me to state for hash tables?

State average case O(1) for insert, delete, and lookup, with worst case O(n) under adversarial collisions. In an interview, default to average case unless the prompt specifies adversarial input. Pair the complexity claim with the canonical use case (frequency counting, prefix lookup, set membership) so you signal pattern recognition along with the Big-O.