Fifteen common data structures questions
- Array versus linked list — trade-offs?
- How does a dynamic array grow, and what is amortised cost?
- Implement a stack using queues, or a queue using stacks.
- How does a hash table work? How are collisions handled?
- What is a load factor, and when does rehashing happen?
- What makes a binary search tree efficient, and how can it degrade?
- What are AVL and red-black trees?
- What is a heap, and what is it used for?
- Adjacency list versus adjacency matrix?
- BFS versus DFS — when to use each?
- What is a trie, and when is it useful?
- How would you implement an LRU cache?
- What is a deque? A priority queue?
- What is a union-find structure?
- Which structure would you use for autocomplete? For a leaderboard?
Core operations and complexity
| Structure | Access | Search | Insert / delete | Best for |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) (end: amortised O(1)) | Indexed access, cache-friendly scans |
| Linked list | O(n) | O(n) | O(1) at a known node | Frequent insertions at known positions |
| Hash table | — | O(1) average | O(1) average | Lookups by key, counting, de-duplication |
| Balanced BST | — | O(log n) | O(log n) | Ordered data, range queries |
| Binary heap | O(1) min/max | O(n) | O(log n) | Priority queues, top-k |
| Trie | — | O(length of key) | O(length of key) | Prefix search, autocomplete |
Hash tables in depth
A hash function maps a key to a bucket index. Collisions are handled by chaining (each bucket holds a list) or open addressing (probe for the next free slot). As the load factor — entries divided by buckets — rises, collisions increase, so the table resizes, typically doubling and rehashing every entry; that occasional O(n) cost averages out to O(1) per insertion. Worst-case lookups degrade to O(n) with a poor hash function or adversarial keys, which is why some implementations switch long chains to balanced trees.
Trees, heaps and graphs
- BST: left subtree smaller, right larger; O(log n) when balanced but O(n) if keys arrive sorted. Self-balancing trees such as AVL (stricter balance, faster lookups) and red-black (cheaper updates) keep height logarithmic.
- Heap: a complete binary tree where each parent is smaller (min-heap) or larger than its children, usually stored in an array; used for priority queues, Dijkstra's algorithm and top-k problems.
- Graphs: adjacency lists use O(V + E) space and suit sparse graphs; adjacency matrices use O(V²) and give O(1) edge checks for dense graphs. BFS finds shortest paths in unweighted graphs; DFS suits connectivity, cycle detection and topological sort.
Design-flavoured questions
An LRU cache combines a hash map (key to node) with a doubly linked list (recency order) for O(1) get and put. Autocomplete uses a trie, often storing top suggestions at each node. A leaderboard uses a sorted structure or a heap depending on whether you need full rankings or just the top k. These questions test combining structures, so practise explaining why each piece is there. See BFS vs DFS and how to answer coding interview questions.
Practising
The fastest way to find gaps is to be asked. Run a spoken mock round on data structures topics — a free AI interview assistant such as CoPilot Interview builds one from your résumé and the job description and scores every answer — then study whatever you stumbled on. For each structure, solve two problems and implement the structure once from scratch; implementation questions are common in campus rounds.
Disclosure: CoPilot Interview is our product, so weigh what we say about it accordingly. Everything else on this page applies whichever tool you use, or none.
Frequently asked questions
Which data structures are most important for interviews?
Arrays, strings, hash tables, linked lists, stacks, queues, trees (especially binary search trees), heaps and graphs, with tries and union-find for more advanced rounds.
How does a hash table achieve O(1) lookups?
A hash function maps each key directly to a bucket. With a good hash function and a controlled load factor, buckets stay small, so lookups take constant time on average.
When should I use a linked list instead of an array?
When you frequently insert or delete at known positions and don't need random access. Arrays are usually faster in practice for scans because of cache locality.
How do you implement an LRU cache?
Combine a hash map from keys to nodes with a doubly linked list ordered by recency, moving accessed nodes to the front and evicting from the back, giving O(1) operations.
Practise on real interview questions
Run 145 real interview questions across 10 tracks, answer out loud and see a structured answer to compare with yours. Free, no signup.
Try a practice question