Data Structures Interview Questions

A curated set of data structures interview questions, ordered roughly from fundamentals to more advanced — the kind you'll actually be asked in real screens and on-sites.

Arrays and linked lists#

Q: What are the trade-offs between an array and a linked list? An array gives O(1) index access (direct address calculation) but O(n) insertion/deletion at the front or middle, since elements must shift. A linked list gives O(1) insertion/deletion once you're already at the right node (no shifting — just repointing references), but O(n) access by position, since you must walk from the head. Arrays are also more cache-friendly, since their elements sit contiguously in memory, while a linked list's nodes are scattered — so even an O(n) traversal is often faster in practice on an array than on a linked list of the same size. The right choice depends on which operation dominates: frequent random access favors an array; frequent front insertion/deletion favors a linked list.

Q: Why is a dynamic array's append considered O(1) if it sometimes has to resize and copy everything? Because that expensive O(n) resize only happens occasionally — each time it happens, the array's capacity roughly doubles, so the cost of copying is spread ("amortized") across all the cheap O(1) appends that happen before the next resize is needed. Averaged over a long sequence of appends, the cost per append works out to O(1), even though any single append could, rarely, trigger an O(n) copy.

Q: How would you detect a cycle in a linked list without using extra memory proportional to the list's length? Floyd's cycle detection algorithm (tortoise and hare): use two pointers starting at the head, one advancing one node at a time and the other advancing two nodes at a time. If there's no cycle, the faster pointer reaches the end first. If there is a cycle, the faster pointer will eventually lap the slower one from behind, and they'll land on the same node — proving a cycle exists. This runs in O(n) time using only O(1) extra space, compared to the O(n) space a hash-set-of-visited-nodes approach would need.

Hash tables#

Q: How does a hash table achieve average O(1) lookup, and when can that degrade? It runs a key through a hash function to compute a bucket index directly, then jumps straight to that bucket rather than searching — so lookup, insertion, and deletion are all typically O(1). It degrades to O(n) in the worst case when many keys collide into the same bucket (a poor hash function, or an adversarially chosen set of keys), since a bucket internally falls back to a linear scan (in chaining-based implementations) once it holds more than a couple of entries. Real implementations mitigate this with well-designed hash functions and by resizing the bucket array once the load factor gets too high.

Q: Why can't you use a Python list as a dictionary key? Because lists are mutable, and a dictionary key's hash value must never change for as long as it's stored — if a key's contents (and therefore its hash) could change after insertion, the hash table would no longer know which bucket to look in to find it again. Tuples work as dictionary keys because they're immutable (as long as everything inside them is also immutable).

Q: Walk through how you'd solve "two sum" efficiently. Iterate through the array once, keeping a hash map of every number seen so far mapped to its index. For each new number, compute its complement (target - number) and check whether that complement already exists in the map — an O(1) average lookup. If it does, you've found your pair immediately; if not, add the current number to the map and continue. This solves the problem in O(n) time and O(n) space, versus the naive nested-loop approach's O(n²) time, by trading "search for a partner" for "remember what you've already seen and ask an O(1) question about it."

Trees and heaps#

Q: How can a binary search tree degrade from O(log n) to O(n) operations? A BST's efficiency depends entirely on staying reasonably balanced — its height needs to stay close to log n. If data is inserted in already-sorted order (or any order that consistently favors one side), every new node ends up as, say, the right child of the previous node, and the tree degenerates into what is structurally a linked list, with height equal to n. Self-balancing trees like AVL trees and Red-Black trees solve this by performing rotations after insertions/deletions to guarantee height stays O(log n) regardless of insertion order.

Q: When would you use a heap instead of just sorting the whole collection? Use a heap when you repeatedly need only the current minimum or maximum while the collection keeps changing (a priority queue, a live leaderboard), or when you need just the top/bottom k elements out of a much larger collection. A heap gives O(log n) insert/remove-extreme and O(1) peek at the extreme, without ever fully ordering the rest of the data — finding the top k this way costs O(n log k), which beats a full O(n log n) sort whenever k is meaningfully smaller than n. If you genuinely need the entire collection in sorted order, a full sort is simpler and no less efficient.

Q: What's the difference between an in-order, pre-order, and post-order tree traversal, and when would you use each? In-order (left, node, right) visits a binary search tree's nodes in ascending sorted order — use it whenever you need sorted output. Pre-order (node, left, right) visits the node before its children, which is useful for serializing or copying a tree's structure, since the root is always processed first. Post-order (left, right, node) visits a node only after both its children, which is needed whenever children must be fully handled before their parent — safely deleting a tree bottom-up, or evaluating an expression tree where operands must be evaluated before the operator is applied.

Graphs#

Q: What's the difference between an adjacency list and an adjacency matrix, and when would you choose each? An adjacency list stores, per vertex, only its actual neighbors — O(V + E) space, ideal for sparse graphs (most real-world graphs, like social networks or road maps), though checking "are these two vertices connected" costs O(degree of the vertex). An adjacency matrix stores a full V×V grid marking every possible pair — O(V²) space regardless of how many edges actually exist, but it gives O(1) edge-existence checks. Choose the list for sparse graphs (the common case) and the matrix for dense graphs, or when O(1) connectivity checks matter more than memory.

Q: When would you use BFS versus DFS on a graph? Use BFS when you need the shortest path in an unweighted graph, or anything based on "distance in number of hops" — it explores level by level, so the first time it reaches a target, that's necessarily via the fewest edges. Use DFS when you need to explore exhaustively down one path before trying another — natural for cycle detection, topological sorting, and problems better expressed recursively. Both are correct, complete traversals of the same graph; the right one depends on what property of the traversal order the problem actually needs.

Q: Why does detecting a cycle in a directed graph require more bookkeeping than in an undirected graph? In a directed graph, encountering an already-visited node doesn't necessarily mean a cycle — it might just be a valid, different path converging on a node you already fully explored via another route. What actually indicates a cycle is encountering a node that's still on your current DFS path (an ancestor, tracked separately as an "in progress" set), not merely any node marked visited overall. In an undirected graph, by contrast, any edge back to an already-visited node (other than the one you just came from) is sufficient to prove a cycle, since edges go both ways.