Data Structures Interview Questions (2026)
Data structures interviews are the fastest way to differentiate 'coded for two years' from 'thinks like an engineer.' The interviewers are not testing whether you remember Fibonacci heap constants — they're testing whether you can pick the right structure for the constraint, explain the amortized cost, and spot the operation the structure is bad at. This guide covers the 12 structures that show up in FAANG loops and the follow-up questions.
Beginner questions
1. What are the tradeoffs between an array and a linked list? Beginner
Array: O(1) random access, O(n) middle insert/delete, cache-friendly (contiguous memory), fixed capacity unless you use a growable variant (dynamic array). Linked list: O(1) insert/delete at head/tail, O(n) random access, cache-unfriendly (nodes scattered in memory). In practice, dynamic arrays win almost every use case — LinkedList is worse than ArrayDeque even for FIFO in Java.
2. How does a stack help with balanced-parentheses and expression parsing? Beginner
Push opening brackets, pop and match on closing. If pop mismatches or stack is empty at close, invalid. If stack non-empty at end, invalid. For expression evaluation (shunting-yard), one stack for operators, one for operands — pop operators with higher precedence when a new operator arrives.
3. What are the tradeoffs of a HashSet vs a TreeSet? Beginner
HashSet: O(1) average add/contains/remove, no ordering. TreeSet: O(log n) same operations, in-order iteration, floor/ceiling queries in O(log n). Use HashSet as the default. Reach for TreeSet when you need next-greater / previous-smaller lookups or ordered iteration.
Practice these live, in your voice
MiPrep's practice mode turns your resume into a rehearsed answer set. Talk through the idioms the way top-tier interviewers score.
Download MiPrep 🔒 Interview audio is never stored on our serversIntermediate questions
4. How does a hashmap work? Intermediate
Array of buckets. Insert: hash(key) mod bucket_count → bucket index. Walk chain in bucket for equality → insert or overwrite. Load factor (entries / buckets) triggers resize at ~0.75. Resize doubles the bucket array and rehashes every entry. Amortized O(1) put/get; worst-case O(n) if all keys collide (avoided by good hash function). Interviewer follow-up: 'What happens if the key is mutable and its hash changes after insert?' You can never find it again.
5. What is a heap (priority queue) and when do you use it? Intermediate
Binary heap: complete binary tree stored as an array, with the heap invariant (min-heap: every parent <= children). O(log n) insert and extract-min, O(1) peek. Use for: top-k problems, streaming median (two heaps), Dijkstra, Prim's MST, event schedulers, and job queues by priority. Python heapq is min-heap; negate values for max-heap.
6. Explain BST vs balanced BST vs hashmap. Intermediate
Plain BST: O(log n) average, O(n) worst-case if input is sorted (degenerates to linked list). Balanced BST (AVL, red-black): guaranteed O(log n) insert/search/delete. Hashmap: O(1) average but no ordering. Use balanced BST when you need in-order traversal (range queries, next-greater lookup) — std::map in C++ and TreeMap in Java are red-black trees.
7. What is a graph and how do you represent one? Intermediate
Two representations: adjacency list (dict node → list of neighbors) — O(V + E) space, better for sparse graphs and iterating neighbors. Adjacency matrix (V×V grid, 1 for edge) — O(V²) space, better for dense graphs and O(1) edge-exists check. Choose based on E vs V² — sparse graphs (E << V²) always use lists.
8. Explain a deque and when to prefer it over stack/queue. Intermediate
Double-ended queue: O(1) push/pop at both ends. Wins over stack + queue when you need both. Canonical use: sliding-window maximum — deque of indices with decreasing values, pop from the back while smaller than the new element, pop from the front when out of window. Python collections.deque is O(1) at both ends and better than list for FIFO.
Advanced questions
9. What is a trie and when to use it? Advanced
Prefix tree — each node has a character and links to children. Insert / lookup / prefix search all O(word_length). Wins over hashmap for autocomplete, spell check, IP routing (longest-prefix match), and word-search puzzles. Memory-heavy if the alphabet is large (Unicode); optimize with hashmap children instead of fixed-size arrays.
10. Explain LRU cache implementation. Advanced
Doubly-linked list ordered by recency + hashmap from key to node. get: hashmap lookup → move node to head of list. put: same, plus evict tail if over capacity. All operations O(1). Python shortcut: OrderedDict has move_to_end and popitem(last=False), gives you LRU in ~10 lines. functools.lru_cache is a decorator that gives you LRU on any pure function.
11. What is a Bloom filter and when do you use it? Advanced
Probabilistic membership structure. Bit array + K hash functions. Insert: hash the item K ways, set K bits. Query: check all K bits set. False positives possible (bits collided from other items), false negatives impossible. Wins when you have a huge set and can tolerate 'maybe present' answers — CDN cache prefilters, spam filters, dedup at ingest. Follow with a real membership check if the Bloom filter says yes.
12. What's a segment tree and what problem does it solve? Advanced
Binary tree over array indices. Each node stores the aggregate (sum, min, max, gcd) of a subrange. O(log n) point update and range query. Wins when the array is mutable and you need repeated range queries. Alternative: Fenwick (BIT) tree — simpler and faster for prefix-sum queries specifically, but doesn't handle min/max.
Common mistakes candidates make
- Reaching for a set to dedup and forgetting hashCode() (Java) or __hash__ (Python) on custom types.
- Assuming HashMap iteration order is stable — it's not in Python < 3.7 or in Java's HashMap.
- Using a plain BST in production code — one adversarial input degenerates to O(n).
- Not considering memory: a Python dict costs ~200 bytes per entry — millions of small dicts are millions of bytes.
- Choosing recursion where a stack-with-explicit-loop is safer — very deep call stacks blow up (~1000 deep default).
Study strategy
Two-week plan. Week 1: implement each structure from scratch — hashmap with linear probing, min-heap with array, LRU cache, trie. One per day. Week 2: solve 3 LeetCode problems per structure. When you solve a problem, ask 'is there a smaller structure that would have worked?' — most candidates over-engineer.
Do timed mocks with MiPrep before the real thing
Upload your resume and target job description. MiPrep generates a rehearsed answer set in your voice from your own projects — so mock interviews sound like real ones.
Get MiPrep — free 🔒 Interview audio is never stored on our servers