Interview Prep
Data structures interview questions and how to answer them
Data structures questions test whether you can pick the right tool and explain the tradeoff. Knowing the structure isn't enough. Interviewers want to hear your reasoning about when to use it and what you give up.
PrepVault surfaces the questions you need and tracks your study by role. Free to start.
Data structures interview questions and how to answer them
How does the sliding window technique improve performance when searching for a subarray that meets a condition?
left and right pointer maintain window boundaries. O(1) update by adding right and removing left. reduces O(n^2) nested loop to O(n). applies to max sum, longest substring, minimum window
When would you use breadth-first search over depth-first search on a graph?
BFS: shortest path in unweighted graph, queue-based. DFS: cycle detection, topological sort, stack/recursion. BFS memory scales with level width. both are O(V + E)
Compare separate chaining and open addressing as collision resolution strategies, including their trade-offs for cache performance and load factor?
chaining: linked list per bucket, pointer-chasing cache misses. open addressing: probes flat array, cache-friendly. open addressing clusters above ~0.7 load factor. Python dict uses open addressing with perturbation probing
What is a binary search tree and what property must every node satisfy?
BST property: left < node < right. O(log n) average search, insert, delete. O(n) worst case on degenerate tree. self-balancing variants avoid worst case
What is the balance factor in an AVL tree and how does rotation restore the invariant after insertion?
balance factor = height(left) - height(right), must be in {-1, 0, 1}. post-insertion height update walks up the path. single rotation for LL and RR; double rotation for LR and RL. all rotations O(1), insertion stays O(log n)
How does a hash map achieve O(1) average-case lookup, and what causes a worst-case O(n)?
hash function maps key to bucket index. O(1) average when keys distribute evenly. O(n) worst case from collision chains. load factor controls resize threshold
What is a min-heap and how does heapq implement one in Python?
min at root always. O(log n) push and pop. stored as array with index arithmetic. used for priority queues and k-smallest problems
What is an array and what is the time complexity of accessing an element by index?
O(1) index access via pointer arithmetic. O(n) insert at arbitrary index due to shifting. amortized O(1) append on dynamic arrays. contiguous memory enables cache locality
How does a singly linked list differ from an array, and when would you choose one over the other?
O(n) index traversal vs O(1) array access. O(1) head insert and delete. pointer overhead vs cache-friendly contiguous memory. choose based on dominant operation
What is a stack, and what are the two core operations it supports?
LIFO order. O(1) push and pop. implemented with a list using append/pop. used for call stacks, undo, and parsing
Common mistakes
- Knowing a structure but not when to use it
- Skipping the time and space tradeoff
- Reaching for the heaviest tool by default
What interviewers weigh
- Choosing the right structure for the job
- Reasoning about complexity
- Explaining what you give up