Common Data Structures Interview Questions

Data structures interviews rarely test whether you memorized a definition. They test whether you understand the tradeoffs behind a choice: why an array beats a linked list for random access, why a hash map gives average O(1) lookup but can degrade, and why a balanced tree guarantees what a plain BST cannot. This topic collects the questions that come up again and again across coding interviews, with answers that focus on the 'why', not just the 'what'.

Arrays store elements in contiguous memory, so indexing is O(1) and iteration is cache-friendly, but inserting or deleting in the middle requires shifting elements, an O(n) operation. Linked lists give O(1) insertion/deletion once you have a reference to the node, but indexing requires O(n) traversal and each node has pointer overhead plus poor cache locality. Choose arrays when you read far more than you insert/delete in the middle; choose linked lists when you need frequent mid-sequence insertion/deletion and don't need random access, e.g. implementing an LRU cache's node list alongside a hash map.

Use a stack (LIFO) when the most recently added item must be processed first: function call stacks, undo/redo, matching brackets, DFS traversal, and expression evaluation. Use a queue (FIFO) when items must be processed in the order they arrived: task scheduling, BFS traversal, print job queues, and buffering streamed data. The core signal is whether order of arrival should match order of processing (queue) or be reversed (stack).

A hash table gives average O(1) lookup, insert, and delete, which is faster than a balanced BST's O(log n) in the average case. However, a BST keeps keys in sorted order, enabling O(log n) range queries, in-order traversal for sorted output, floor/ceiling/predecessor/successor queries, and stable performance without needing a good hash function. Pick a hash table for pure existence/lookup checks; pick a BST (or a balanced variant like an AVL or red-black tree) when you need ordered operations.

Array: access O(1), search O(n), insert/delete at end O(1) amortized, insert/delete at arbitrary index O(n). Singly linked list: access O(n), search O(n), insert/delete at head O(1), insert/delete at tail O(n) without a tail pointer (O(1) with one), insert/delete at known node O(1). Hash table: access by key O(1) average / O(n) worst case, search O(1) average, insert O(1) average, delete O(1) average. Interviewers expect you to state both the average and worst case, not just the average.

A hash function maps a key to an array index (a bucket). If the hash function distributes keys uniformly and the table resizes to keep the load factor (elements / buckets) low, each bucket holds very few elements on average, so lookup, insert, and delete only touch a small constant number of entries — O(1) on average. Collisions are handled with chaining (each bucket holds a list) or open addressing (probing for the next free slot). Worst case is O(n) if all keys collide into one bucket, which is why a good, well-distributed hash function and periodic resizing matter.

Use Floyd's cycle detection (the 'tortoise and hare' algorithm): one pointer moves one step at a time, another moves two steps. If there is a cycle, the fast pointer eventually laps the slow pointer and they meet; if the fast pointer reaches null, there is no cycle. This runs in O(n) time and O(1) extra space, compared to O(n) space if you tracked visited nodes in a hash set.

A heap is ideal when you only need the minimum/maximum (or top-k) repeatedly without needing the full data sorted. Building a heap is O(n), and each extract-min/max is O(log n) — finding the k smallest of n elements is O(n + k log n) with a heap versus O(n log n) to fully sort. Heaps also support efficient priority queue operations (decrease-key, insert) used in algorithms like Dijkstra's shortest path and in scheduling.

BFS explores level by level using a queue and finds the shortest path in an unweighted graph; it uses O(V) extra space in the worst case for the queue and visited set. DFS explores as deep as possible before backtracking, using a stack (explicit or via recursion); it uses less memory for wide graphs but can miss the shortest path. Choose BFS for shortest-path/level-order problems, DFS for exhaustive search, topological sort, cycle detection, and connectivity problems where path length doesn't matter.

When a dynamic array is full, it allocates a new block (typically double the size) and copies all existing elements over — an O(n) operation. But because this only happens occasionally (geometric growth), the total cost of n appends is O(n), so each append is O(1) on average, i.e. amortized. A single append can still spike to O(n) in the worst case, which matters in latency-sensitive interview follow-ups.

Combine an array with a hash map. The array stores the values (enabling O(1) random access via a random index for getRandom). The hash map stores value → index in the array. To delete in O(1), swap the element to delete with the last element in the array, update the hash map for the swapped element, then pop the last element — avoiding the O(n) shift a plain array delete would need.