Data Structures interview questions

What a strong answer covers

• Linked lists give O(1) insertion or deletion at a known node or at the ends without shifting elements, and grow without reallocation or amortized resize cost.
• Dynamic arrays give O(1) random access by index and far better cache locality because elements are contiguous, while linked lists require O(n) traversal to reach the k-th node.
• Call out the memory overhead of per-node pointers and the pointer chasing that causes cache misses, so in practice arrays often win even for insert-heavy workloads.
• Concrete fits: linked list for an LRU cache eviction list or a queue with frequent splicing; dynamic array for lookups, iteration, and binary search.

Where people lose the point

• ×Claiming linked-list insertion is O(1) without noting you first need an O(n) traversal to find the insertion point.
• ×Ignoring cache locality and asserting linked lists are faster for insert-heavy work when contiguous arrays usually outperform them in practice.
• ×Forgetting that dynamic array append is amortized O(1), not O(n), because of doubling.

What a strong answer covers

• A hash function maps keys to bucket indices; with a good uniform hash and a bounded load factor, expected chain length is constant, giving O(1) average insert, lookup, and delete.
• Collisions are resolved by separate chaining (linked list or tree per bucket) or open addressing (linear or quadratic probing, double hashing); each has different clustering and deletion behavior.
• Degradation to O(n) happens when many keys collide into one bucket, from a poor hash, adversarial inputs, or a high load factor; resizing and rehashing when the load factor crosses a threshold keeps operations amortized O(1).
• Mention real mitigations: Java 8 converts long buckets to balanced trees for O(log n) worst case, and randomized or cryptographic hashing defends against collision attacks.

Where people lose the point

• ×Stating lookup is O(1) worst case rather than O(1) average and O(n) worst case.
• ×Not explaining resizing and rehashing, or forgetting that rehashing makes individual inserts amortized rather than strictly O(1).
• ×Confusing chaining with open addressing, or missing that open addressing needs tombstones to delete correctly.

What a strong answer covers

• Hash tables give O(1) average point lookups but no ordering, so range queries and sorted iteration are impossible without scanning all keys.
• A balanced BST (red-black or AVL) or a skip list gives O(log n) lookup, insert, and delete plus O(log n) range boundary location and O(log n + k) range retrieval, and O(n) in-order traversal yields sorted output.
• Choose the balanced BST or sorted structure here because ordering and range queries are required; accept the O(log n) versus O(1) point-lookup cost as the tradeoff.
• Note real analogues: C++ std::map and Java TreeMap are red-black trees, while std::unordered_map is a hash table; databases use B-trees for the same range-query reason on disk.

Where people lose the point

• ×Defaulting to a hash table because it is fastest for lookups while ignoring that the question requires ordering and ranges.
• ×Forgetting that an unbalanced BST degrades to O(n) on sorted insertions, so balancing or a skip list is essential.
• ×Claiming a hash table can do range queries efficiently by sorting keys on demand, which is O(n log n) per query.

What a strong answer covers

• Maintain a min-heap of size k: for each incoming element, if the heap has fewer than k elements push it, otherwise compare against the heap minimum and replace-if-larger in O(log k).
• Total cost is O(n log k) time and O(k) space, which beats sorting the whole stream at O(n log n) and works for unbounded streams where you cannot hold everything.
• Explain why a min-heap and not a max-heap: the root is the smallest of the current top k, so it is exactly the element to evict when a larger one arrives.
• Discuss alternatives and their fit: Quickselect gives O(n) average for a static array but needs all data in memory and is not streaming; a balanced BST or order-statistics tree also works but with more overhead.

Where people lose the point

• ×Using a max-heap of all n elements (O(n) space, O(n log n)) instead of a size-k min-heap, defeating the streaming goal.
• ×Mixing up which heap type to use, or evicting the wrong element so the top-k set becomes incorrect.
• ×Quoting Quickselect as O(n) worst case rather than average, and ignoring that it does not handle a stream.

What a strong answer covers

• Adjacency list stores per-vertex neighbor lists using O(V + E) space and iterates a vertex's neighbors in O(degree), which is ideal for sparse graphs and traversals like BFS and DFS.
• Adjacency matrix uses O(V^2) space and answers edge-existence in O(1) but wastes space on sparse graphs and makes neighbor iteration O(V); it suits dense graphs and algorithms like Floyd-Warshall.
• Match representation to algorithm: BFS and DFS run in O(V + E) on a list; Dijkstra with a binary heap is O((V + E) log V); dense all-pairs shortest paths favor a matrix.
• Mention variants: store weights on edges, use edge lists for Kruskal with union-find, and note directed vs undirected changes how you record each edge.

Where people lose the point

• ×Using an adjacency matrix for a large sparse graph, wasting O(V^2) memory when O(V + E) would do.
• ×Stating BFS or DFS is O(V^2) on an adjacency list when it is O(V + E).
• ×Forgetting the visited set, which causes infinite loops on cyclic graphs during traversal.

What a strong answer covers

• Use Floyd's tortoise-and-hare: advance a slow pointer one step and a fast pointer two steps; if they ever meet, a cycle exists, all in O(n) time and O(1) space.
• If the fast pointer reaches null, the list is acyclic; this avoids the O(n) extra space of a hash set of visited nodes.
• To find the cycle start, after the meeting point reset one pointer to the head and advance both one step at a time; they meet at the entry node, which follows from the distance math of the algorithm.
• State the edge cases: empty list, single node with no self-loop, and a self-loop of length one.

Where people lose the point

• ×Reaching for a visited hash set (O(n) space) when the interviewer asked for constant space.
• ×Advancing the fast pointer without null-checking both fast and fast.next, causing a null-pointer error.
• ×Knowing cycles can be detected but being unable to derive the cycle-entry step, or misremembering which pointer to reset.