Data structures are the backbone of every program ever written, and for any developer pursuing a software engineering role at any company from early-stage startups to FAANG, data structure interview questions are the category that defines whether you move forward or not. Studies of NYC tech job postings found that 93 percent required data structures knowledge, and Google explicitly states on its career page that candidates should study as many data structures as possible, with arrays, linked lists, stacks, queues, hash maps, trees, and graphs being the most frequently tested.
Mastering these concepts is not only about clearing interviews. It builds the problem-solving foundation that every other area of technical work depends on, including algorithms, system design, and performance optimisation. The sharper your intuition for choosing the right data structure for a given problem, the more effectively you handle any technical challenge thrown at you.
This guide covers the top 30 data structure interview questions, selected for quality and depth across all major categories. Whether you are preparing for your first developer role or targeting a senior engineering position, these questions represent exactly what gets asked and what separates strong candidates from the rest.
Read Next: Top 50 Technical Interview Questions
Why Data Structure Interviews Go Beyond Memorisation
The goal of a data structure interview question is never to check whether you have memorised a definition. Interviewers use these questions to evaluate how you think: whether you can identify which data structure suits a given problem, articulate the trade-offs between choices, and reason about time and space complexity under real constraints.
A candidate who defines a linked list correctly but cannot explain when to prefer it over an array, or who implements a hash table but cannot discuss collision resolution strategies, will not pass a strong technical interview. The questions in this guide are structured to build both the conceptual understanding and the applied reasoning interviewers are looking for.
Junior interviews focus on foundational structures and basic operations. Mid-level interviews introduce graphs, trees, dynamic programming, and real trade-off questions. Senior interviews blend data structure selection with system design thinking, asking how you would design an LRU cache, optimise a search pipeline, or model a social network. All three levels reward candidates who communicate their reasoning clearly, not just those who arrive at the right answer.
Foundational Data Structure Interview Questions (Q1 to Q8)
These questions are asked at every experience level. They establish whether you have a clean conceptual foundation before more complex problems begin.
Q1. What is a data structure and why does it matter?
Answer: A data structure is a specific way of organising and storing data in a computer’s memory so that it can be accessed, processed, and modified efficiently. The choice of data structure directly determines how fast and how memory-efficiently a program runs.
Different structures are optimised for different operations. An array gives you O(1) random access by index. A linked list gives you O(1) insertion at the head. A hash map gives you O(1) average-case lookup by key. A binary search tree gives you O(log n) search, insertion, and deletion on sorted data.
Data structures are the tools that algorithms operate on. Picking the right structure for a problem is often the difference between an O(n) solution and an O(n squared) one. They are used everywhere: operating systems use queues for process scheduling, databases use B-trees for indexing, browsers use stacks for navigation history, and compilers use trees to represent code. Every significant software system depends on choosing appropriate data structures at its core.
Q2. What is the difference between linear and non-linear data structures?
Answer: The distinction is about how elements are arranged and connected in memory, which affects both traversal patterns and the types of relationships the structure can represent.
Linear data structures arrange elements sequentially. Each element has at most one predecessor and one successor. You can traverse all elements in a single pass from one end to the other. Arrays, linked lists, stacks, and queues are all linear structures. They are simple to implement and well-suited for ordered data.
Non-linear data structures arrange elements in hierarchical or networked relationships where a single element can connect to multiple others. You cannot traverse all elements in a single pass without a traversal algorithm. Trees represent parent-child hierarchies: a root node connects to child nodes, each of which may have further children. Graphs extend this further by allowing arbitrary connections between any nodes, including cycles. Non-linear structures model real-world relationships that sequential structures cannot, such as file systems, social networks, and routing tables.
Q3. What is the difference between an array and a linked list?
Answer: This is one of the most fundamental and frequently asked comparisons in data structure interviews. The core distinction is about memory layout and what operations each structure optimises.
An array stores elements in contiguous memory locations. Because of this, accessing any element by its index is O(1): the address is calculated directly from the base address plus the index multiplied by the element size. This makes arrays ideal for random access patterns. However, inserting or deleting an element in the middle requires shifting all subsequent elements, making these operations O(n). Arrays also have a fixed size in many languages, requiring resizing and copying when capacity is exceeded.
A linked list stores elements in nodes scattered across memory. Each node contains the data and a pointer to the next node. There is no contiguous memory requirement, so insertion and deletion at any position takes O(1) time once you have a reference to the correct node, because only pointer adjustments are needed.
However, accessing the nth element requires traversing from the head, making random access O(n). Linked lists use more memory per element because of the pointer overhead. Use arrays for frequent random access and fixed-size data. Use linked lists for frequent insertions and deletions, especially at arbitrary positions.
Q4. What is Big O notation and why is it critical in data structure interviews?
Answer: Big O notation is a mathematical representation of how an algorithm’s time or space requirements grow as the input size increases. It describes the upper bound on growth rate, allowing engineers to compare algorithm efficiency independent of hardware or implementation details.
Common complexities in order from best to worst: O(1) constant time means the operation takes the same time regardless of input size, like array index access or hash table lookup. O(log n) logarithmic time means operations halve the search space each step, like binary search. O(n) linear time means operations scale directly with input size, like iterating an array. O(n log n) is the time complexity of efficient sorting algorithms like merge sort and quicksort. O(n squared) quadratic time typically appears in naive nested loop algorithms.
Interviewers ask about Big O because it reveals whether you understand the scalability consequences of your design choices. Writing code that works for ten elements but degrades catastrophically for ten million is a production risk.
When you propose a solution, you should always be ready to state its time complexity for each operation and its space complexity, and to explain whether a more efficient alternative exists. Nowadays, it is mostly time complexity that matters more during evaluation since storage is inexpensive.
Q5. What is a stack and what are its real-world use cases?
Answer: A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. The last element added to the stack is the first one removed. Think of it as a physical stack of plates: you always add or remove from the top.
The three primary operations are push which adds an element to the top in O(1), pop which removes the top element in O(1), and peek or top which reads the top element without removing it in O(1). Checking whether the stack is empty is also O(1). All standard stack operations are constant time, making it extremely efficient for its intended use cases.
Real-world applications of stacks are everywhere. Function call management: when a program calls a function, the call frame is pushed onto the call stack. When the function returns, the frame is popped. This is why stack overflow occurs when recursion goes too deep.
Expression evaluation and parsing: compilers use stacks to evaluate arithmetic expressions and match balanced parentheses. Browser navigation: the back button works because visited pages are stored on a stack. Undo functionality in text editors and design software maintains a stack of operations. Depth-First Search graph traversal uses a stack either explicitly or via the call stack during recursion.
Q6. What is a queue and how does it differ from a stack?
Answer: A queue is a linear data structure that follows the First In, First Out (FIFO) principle. The first element added to the queue is the first one removed. It is like a real-world checkout line: the person who joins first is served first.
The primary operations are enqueue which adds an element to the rear in O(1), and dequeue which removes the element from the front in O(1). Peek returns the front element without removing it. A queue is open at both ends: insertion happens at one end (rear) and removal happens at the other (front). This is the fundamental difference from a stack, which operates exclusively from one end.
Real-world applications include CPU process scheduling where the operating system maintains a queue of processes waiting for CPU time. Printer job management queues print requests so they are processed in order. Breadth-First Search graph and tree traversal uses a queue to explore neighbours level by level before going deeper.
Network packet buffering maintains queues to handle bursts of incoming data. Message queues in distributed systems like RabbitMQ or Kafka enable asynchronous communication between services by holding messages until consumers are ready to process them.
Q7. What is a hash table and how does it achieve O(1) lookup?
Answer: A hash table (also called a hash map or dictionary) is a data structure that stores key-value pairs and provides average O(1) time complexity for insertion, deletion, and lookup operations. It is the most widely used data structure in algorithm interviews and production code.
A hash table works by applying a hash function to the key to compute an integer index into an underlying array. The value is then stored at that array position. When looking up a value, the same hash function is applied to the key to find the array index, and the value is retrieved directly. This is why lookup is O(1): the index is computed mathematically rather than searched for.
A collision occurs when two different keys produce the same hash index. There are two primary strategies for resolving collisions. Chaining stores a linked list at each array index; all entries that hash to the same index are stored in the list, and lookup traverses the list.
Open addressing finds the next available slot in the array using a probing sequence such as linear probing or quadratic probing. In the worst case where all keys collide, operations degrade to O(n). Good hash functions distribute keys uniformly to minimise collisions. Hash tables power language dictionaries, database indexes for fast lookups, caching systems, and are the standard solution for frequency counting problems in interviews.
Q8. What is the difference between a singly linked list and a doubly linked list?
Answer: Both are linked list variants but they differ in the direction of traversal they support, which affects both the operations available and memory usage.
A singly linked list has nodes where each node contains data and a single pointer to the next node. Traversal is only possible in one direction, from head to tail. To traverse backwards or to delete a specific node, you need a reference to the previous node, which requires traversing from the head. This makes certain operations like deletion of a given node without its predecessor reference more complex.
A doubly linked list has nodes containing data, a pointer to the next node, and a pointer to the previous node. This enables bidirectional traversal and makes deletion of a node O(1) given a direct reference to it, since you can update both neighbouring pointers without traversing.
The trade-off is higher memory usage per node. A doubly linked list is used to implement the LRU (Least Recently Used) cache, where nodes need to be moved to the front or removed from any position in O(1). Browsers use doubly linked lists for forward and backward navigation because movement in both directions is needed.
Trees and Graphs Interview Questions (Q9 to Q16)
Tree and graph questions are the most commonly asked in mid to senior level interviews. Traversal algorithms, BST properties, and graph search are near-universal topics.
Q9. What is a binary tree and what are its traversal methods?
Answer: A binary tree is a hierarchical data structure where each node has at most two children, referred to as the left child and the right child. The topmost node is the root. Nodes with no children are leaf nodes.
Binary trees support four standard traversal methods, each visiting nodes in a different order. In-order traversal visits nodes in Left, Root, Right order. For a Binary Search Tree, this produces nodes in ascending sorted order, which is its most important property. Pre-order traversal visits Root, Left, Right. It is used to create a copy of the tree or to serialise a tree structure.
Post-order traversal visits Left, Right, Root. It is used to delete a tree (children before parents) or to evaluate expression trees. Level-order traversal (Breadth-First Search) visits all nodes at the current depth before moving to the next level, using a queue.
Recursive implementations of DFS traversals are elegant and concise but consume O(h) stack space where h is the tree height. Iterative implementations using an explicit stack avoid the risk of stack overflow on very deep trees. Knowing when to use each traversal reveals a deeper understanding of tree problems that interviewers look for.
Q10. What are the properties of a Binary Search Tree (BST) and what is its time complexity?
Answer: A Binary Search Tree is a binary tree with a specific ordering property that enables efficient search, insertion, and deletion operations.
The BST property states: for every node, all values in its left subtree are strictly less than the node’s value, and all values in its right subtree are strictly greater. Both the left and right subtrees must themselves also be valid BSTs. This property allows binary search to be applied at every node: at each step, you eliminate half the remaining candidates by going left or right.
For a balanced BST, search, insertion, and deletion all run in O(log n) average time. However, a BST can become unbalanced. If you insert elements in sorted order, the BST degenerates into a linked list with O(n) operations. Self-balancing BST variants like AVL trees and Red-Black trees maintain balance automatically by performing rotations during insertion and deletion, guaranteeing O(log n) in the worst case.
MySQL uses Red-Black trees for table indexes. In-order traversal of a BST always produces elements in sorted ascending order, which is one of the most important BST properties tested in interviews.
Q11. What is a heap and when would you use one?
Answer: A heap is a complete binary tree that satisfies the heap property, making it the standard data structure for implementing priority queues.
In a max-heap, every node’s value is greater than or equal to its children’s values. The root always holds the maximum element. In a min-heap, every node’s value is less than or equal to its children’s values. The root always holds the minimum element. Heaps are typically implemented using an array rather than explicit node objects, using the parent-child index relationships: for a node at index i, its left child is at 2i+1 and its right child is at 2i+2.
Key operations and their complexities: inserting a new element takes O(log n) because the element is added at the bottom and bubbled up. Extracting the min or max takes O(log n) because after removing the root, the last element is moved to the root and sifted down. Peeking at the min or max takes O(1).
Building a heap from an unsorted array takes O(n), not O(n log n) as might be expected. Heaps are used for priority queues in task schedulers and Dijkstra’s shortest path algorithm, heap sort, finding the k largest or k smallest elements efficiently, and median maintenance in streaming data problems.
Q12. What is the difference between a tree and a graph?
Answer: Trees and graphs are both non-linear data structures, but a tree is actually a restricted form of graph with specific constraints that simplify traversal and prevent cycles.
A graph is a collection of vertices (nodes) and edges (connections between nodes). Graphs can have cycles, disconnected components, and edges can be directed (one-way) or undirected (two-way). A directed graph has edges with a specific direction, like following someone on social media. An undirected graph has edges without direction, like a friendship on a social network. Graphs can also have weighted edges representing costs or distances.
A tree is a connected, acyclic, undirected graph where any two nodes are connected by exactly one path. It has n nodes and exactly n-1 edges. The rooted tree variant designates one node as the root and organises the rest as parent-child relationships. Because trees have no cycles and are connected, they are simpler to traverse and reason about than general graphs.
Graphs require cycle detection during traversal using visited arrays or sets. Use trees for hierarchical data like file systems and HTML DOM. Use graphs for network modelling, social relationships, routing problems, and any domain with arbitrary connections between entities.
Q13. What is Depth-First Search (DFS) and when do you use it?
Answer: Depth-First Search is a graph and tree traversal algorithm that explores as far as possible along each branch before backtracking. It goes deep before it goes wide.
DFS can be implemented recursively using the call stack or iteratively using an explicit stack. The algorithm starts at a source node, marks it as visited, then recursively visits each unvisited neighbour. Because it follows one path all the way to the end before backtracking, DFS naturally explores complete branches.
DFS is the right choice when you need to detect cycles in a directed graph (by tracking nodes in the current recursion stack), perform topological sorting of a directed acyclic graph (reverse post-order DFS), find connected components in an undirected graph, solve maze or pathfinding problems where you want to explore one complete path first, check if a path exists between two nodes, or solve backtracking problems like generating permutations. DFS uses O(h) space where h is the maximum depth of the recursion, which for a balanced tree is O(log n) but for a degenerate graph could be O(n).
Q14. What is Breadth-First Search (BFS) and when should you prefer it over DFS?
Answer: Breadth-First Search is a graph and tree traversal algorithm that explores all neighbours of the current node before moving to the next level. It goes wide before it goes deep.
BFS is implemented using a queue. The algorithm starts at a source node, adds it to the queue, then repeatedly dequeues a node, visits it, marks it, and enqueues all its unvisited neighbours. This level-by-level exploration ensures that nodes closer to the source are always visited before nodes farther away.
BFS is the right choice when you need to find the shortest path in an unweighted graph because BFS always finds the shortest path (fewest edges) by virtue of its level-by-level traversal. Use BFS for social network distance problems (finding if two people are connected within k degrees), web crawlers that explore pages level by level, peer-to-peer network broadcasting, and any problem where you want the minimum number of steps to reach a target.
BFS uses O(w) space where w is the maximum width of the graph, which can be O(n) in the worst case. DFS uses O(h) space. For trees with high branching factors, DFS is more memory-efficient. For trees with great depth, BFS is safer against stack overflow.
Q15. What is a balanced binary tree and why does balance matter?
Answer: A balanced binary tree is a tree where the height difference between the left and right subtrees of any node is at most one, recursively. Balance is what ensures that tree operations remain O(log n) rather than degrading to O(n).
Height is the key metric. A balanced binary tree with n nodes has height O(log n). An unbalanced tree can have height O(n) in the worst case (degenerate tree that looks like a linked list). Since search, insertion, and deletion in a BST all run in O(height), a balanced tree gives O(log n) for all operations while an unbalanced one gives O(n).
AVL trees are the strictest self-balancing BST: they maintain the height difference (balance factor) of at most 1 for every node and perform rotations after insertions and deletions to restore balance. Red-Black trees are a more relaxed variant that guarantee a height of at most 2 log n, performing fewer rotations and often having better real-world performance than AVL trees.
Java’s TreeMap and TreeSet, and C++’s map and set use Red-Black trees. Checking whether a binary tree is height-balanced is a classic interview problem: recursively compute the height of each subtree and check that the difference never exceeds 1 at any node.
Q16. How does the LRU Cache work and which data structures implement it?
Answer: The LRU (Least Recently Used) cache is a classic data structure design problem that appears frequently in interviews. It requires two operations, get and put, both running in O(1) time.
The challenge is that O(1) lookup alone could be achieved with a hash map, and O(1) insertion and deletion from any position can be achieved with a doubly linked list. The LRU cache combines both to achieve O(1) for all operations simultaneously.
A hash map stores each key mapped to a pointer to its corresponding node in the doubly linked list. The doubly linked list maintains the order of element use: the most recently used element is at the head, and the least recently used is at the tail. When get is called, the key is looked up in the hash map in O(1), its node is moved to the head of the list in O(1), and its value is returned. When put is called with a new key, a new node is added at the head in O(1) and the hash map is updated.
If the cache is at capacity, the tail node (least recently used) is removed in O(1) and its key is deleted from the hash map. This design is a canonical example of combining data structures to achieve time complexities that neither alone could provide.
Sorting, Searching, and Algorithm Interview Questions (Q17 to Q24)
Sorting and searching questions test both your knowledge of algorithms and your ability to analyse time complexity. Always state complexity when answering these questions.
Q17. What is the difference between merge sort and quicksort?
Answer: Both are divide-and-conquer sorting algorithms with O(n log n) average time complexity, but they differ in their approach, stability, and worst-case behaviour.
Merge sort divides the array into two halves, recursively sorts each half, then merges the two sorted halves. The merge step is what does the actual sorting. Merge sort is a stable sort, meaning it preserves the relative order of equal elements. It always runs in O(n log n) time in all cases: best, average, and worst. Its major downside is space: it requires O(n) additional memory for the temporary arrays used during merging. Merge sort is preferred for sorting linked lists (where random access is expensive) and for large datasets where stability is required.
Quicksort selects a pivot element and partitions the array into two subarrays: elements less than the pivot and elements greater than the pivot. It then recursively sorts both subarrays. Average time complexity is O(n log n) but the worst case is O(n squared) when the pivot is consistently the smallest or largest element (a sorted array with naive pivot selection).
This is mitigated using randomised pivot selection or median-of-three. Quicksort is an in-place sort requiring only O(log n) stack space on average, making it more memory-efficient than merge sort. It is generally faster in practice due to better cache locality. Most standard library sort implementations use a hybrid of quicksort and other algorithms.
Q18. What is binary search and what are its requirements?
Answer: Binary search is the most efficient searching algorithm for sorted data, achieving O(log n) time by halving the search space at each step.
The algorithm initialises two pointers, low at index 0 and high at the last index. It computes the midpoint as (low + high) / 2, checks whether the target equals the middle element, and if so returns the index. If the target is less than the middle element, it sets high to mid minus 1 to search the left half. If the target is greater, it sets low to mid plus 1 to search the right half. This repeats until the target is found or low exceeds high.
Binary search requires that the data is sorted. Attempting binary search on unsorted data produces incorrect results. It also requires random access in O(1), which is why binary search works on arrays but not on linked lists (where accessing the midpoint takes O(n)).
Binary search extends to many interview variants beyond simple target finding: finding the first or last occurrence of a duplicate value, finding the insertion position for a new element, searching in a rotated sorted array, and finding the minimum in a rotated sorted array. All of these use the same core principle of deciding which half to discard at each step.
Q19. What is dynamic programming and how does it differ from recursion?
Answer: Dynamic programming (DP) is an optimisation technique for solving problems that have two key properties: overlapping subproblems and optimal substructure. It avoids redundant computation by storing the results of subproblems.
Pure recursion solves a problem by breaking it into smaller subproblems and solving each independently. When subproblems overlap, meaning the same subproblem is solved multiple times, plain recursion is wasteful. Computing the nth Fibonacci number recursively, for example, recalculates fib(n-2) exponentially many times, giving O(2 to the n) time complexity. Dynamic programming solves this by storing each computed value the first time it is calculated and returning the stored result for subsequent calls. This reduces Fibonacci to O(n) time.
Memoisation (top-down DP) adds a cache to a recursive solution. The recursive function checks the cache before computing and stores results before returning. Tabulation (bottom-up DP) builds the solution iteratively from the smallest subproblems upward, filling a table.
Bottom-up avoids the function call overhead of recursion. The hallmark of DP problems is overlapping subproblems: the knapsack problem, longest common subsequence, coin change, and shortest path algorithms like Floyd-Warshall all fit this pattern. DP is considered one of the hardest interview topics because identifying the subproblem structure requires creative insight.
Q20. What is a trie and what problems does it solve?
Answer: A trie (also called a prefix tree) is a tree-like data structure specifically designed for storing and searching strings. Each node represents a character, and paths from the root to nodes represent prefixes.
In a trie, the root represents an empty string. Each edge represents a character. Following a path from root to a node spells out a prefix. A node is marked as a terminal node when the path to it represents a complete word. Inserting a word involves following (or creating) the appropriate character nodes. Searching for a word follows the character path and checks whether the final node is marked as terminal.
Search and insertion both run in O(m) where m is the length of the string, regardless of how many strings are stored. This makes tries faster than a hash map for prefix-related queries where a hash map has no awareness of shared prefixes. Tries are ideal for autocomplete and search suggestion systems (finding all words with a given prefix), spell checkers, IP routing tables using prefix matching, and word games.
The downside is memory: a naive implementation using arrays of 26 children per node can use significant space. Compressed tries (Patricia trees, radix trees) reduce this by merging nodes with single children.
Q21. What is a graph and how are graphs represented in code?
Answer: A graph is a collection of vertices (nodes) and edges (connections between them) that can represent any network-like relationship. Graphs are the most general of all data structures.
Graphs are characterised by several properties. Directed vs undirected: in a directed graph each edge has a specific direction while in an undirected graph edges go both ways. Weighted vs unweighted: edges can carry numeric weights representing cost or distance. Connected vs disconnected: a connected graph has a path between every pair of vertices. Cyclic vs acyclic: a graph with no cycles is called a DAG (Directed Acyclic Graph), used for dependency resolution and topological sorting.
Two standard representations are used in code. An adjacency list stores each vertex mapped to a list of its neighbours. It is memory-efficient for sparse graphs (few edges) because it only stores existing edges. Lookup of whether an edge exists takes O(degree) time.
An adjacency matrix is an n by n grid where the value at row i column j indicates whether an edge exists from vertex i to vertex j. It uses O(n squared) space regardless of edge count and provides O(1) edge existence checks. Adjacency lists are preferred for most interview problems and real-world applications because graphs are typically sparse. Adjacency matrices are used when dense graphs need fast edge queries.
Q22. What is topological sorting and when is it used?
Answer: Topological sorting is an ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge from vertex U to vertex V, U appears before V in the ordering. It only applies to DAGs as cyclic graphs have no valid topological order.
There are two standard algorithms. Kahn’s algorithm (BFS-based) computes the in-degree of every vertex, enqueues all vertices with in-degree zero, then repeatedly dequeues a vertex, adds it to the result, and decrements the in-degree of its neighbours, enqueuing any that reach zero. If the result contains all vertices, the graph is a valid DAG. If any vertices remain, a cycle exists. DFS-based topological sort performs a post-order DFS and reverses the result. A vertex is added to the output after all its descendants have been fully explored.
Real-world applications of topological sorting are pervasive. Build systems and package managers use it to determine the order in which to compile or install dependencies (tasks that depend on other tasks come later).
Course prerequisite systems schedule courses so prerequisites are always taken first. Spreadsheet calculation engines use it to determine which cells to recompute and in what order. Any system with dependencies that must be resolved in order is a topological sorting problem.
Q23. What is the difference between a greedy algorithm and dynamic programming?
Answer: Both are algorithm design paradigms for optimisation problems, but they differ fundamentally in whether they guarantee optimal solutions and how they approach subproblems.
A greedy algorithm makes the locally optimal choice at each step, with the hope that a sequence of local optima produces a global optimum. It never reconsiders previous choices. Greedy algorithms are fast and simple but do not always produce the optimal solution.
They work correctly for problems with the greedy-choice property, where a local optimum leads to a global optimum. Classic examples include activity selection (always pick the task that ends earliest), Huffman encoding, and Dijkstra’s shortest path algorithm on non-negative weighted graphs.
Dynamic programming solves problems by breaking them into overlapping subproblems, solving each subproblem optimally, and combining results. DP always guarantees the globally optimal solution for problems with optimal substructure. It is more powerful but more complex to design and typically uses more memory. The key distinction: greedy does not look back and does not store subproblem results. DP explores all possibilities systematically and caches results.
When deciding which to use: if you can prove the greedy choice is always safe, greedy is faster. Otherwise, DP is the safer choice for guaranteed optimality.
Q24. What is recursion and what are its trade-offs versus iteration?
Answer: Recursion is a technique where a function calls itself with a smaller subproblem until it reaches a base case that stops the recursion. It is a natural fit for problems that have a recursive structure, such as tree traversal, divide-and-conquer algorithms, and backtracking.
The call stack is the key resource consumed by recursion. Every recursive call adds a new stack frame containing the function’s local variables and return address. For deep recursion, this can exhaust stack memory and cause a stack overflow. The maximum safe recursion depth varies by language and environment but is typically in the range of thousands to tens of thousands of calls.
Iteration uses loops instead of recursive calls and avoids stack frame overhead. Iterative solutions are generally faster and more memory-efficient. Tail call recursion, a pattern where the recursive call is the very last operation, can be optimised by some compilers into iteration, avoiding stack growth. For tree problems, DFS recursion is elegant but can overflow on very deep trees; an explicit stack-based iterative implementation handles arbitrary depth safely.
The trade-off summary: recursion is more readable and natural for inherently recursive problems; iteration is safer for deep inputs and uses less memory.
Advanced Data Structure Interview Questions (Q25 to Q30)
These questions are asked at mid to senior level. They test your ability to combine multiple data structures, reason about trade-offs, and apply concepts to real problem design.
Q25. How would you find the first non-repeating character in a string?
Answer: This is a classic hash map application problem that appears frequently in both beginner and intermediate interviews. The optimal solution uses a hash map for frequency counting combined with a second pass for ordering.
The approach uses two passes through the string. In the first pass, iterate through every character and use a hash map to count the frequency of each character. This takes O(n) time and O(k) space where k is the number of distinct characters (at most 26 for lowercase English letters, so effectively O(1) space).
In the second pass, iterate through the string again in order. For each character, check its frequency in the hash map. The first character with a frequency of exactly one is the answer. This also takes O(n) time. The total time complexity is O(n) and space is O(1) for bounded character sets.
An alternative using a frequency array of size 26 instead of a hash map is slightly faster in practice for lowercase letters. This problem is a template for the broader category of frequency-counting problems where a hash map is combined with array traversal.
Q26. How do you detect a cycle in a linked list?
Answer: Cycle detection in a linked list is solved using Floyd’s Cycle Detection Algorithm, also known as the Tortoise and Hare algorithm. This is a classic pointer manipulation problem.
The algorithm uses two pointers that traverse the list at different speeds. The slow pointer moves one node per step. The fast pointer moves two nodes per step. If the list has no cycle, the fast pointer reaches the end (null) and the algorithm terminates. If the list has a cycle, the fast pointer will eventually lap the slow pointer and they will meet at the same node within the cycle.
The meeting is guaranteed because in each iteration the fast pointer gains one position on the slow pointer. If the cycle has length c, they will meet within c iterations after the slow pointer enters the cycle. This algorithm uses O(1) space (just two pointers) and O(n) time, making it optimal.
A hash set alternative stores visited node addresses and checks for revisits, using O(n) space. The follow-up question in interviews is often to find the start of the cycle, which requires resetting one pointer to the head and advancing both one step at a time until they meet again.
Q27. What is the difference between a min-heap and a max-heap, and when would you use each?
Answer: A min-heap and a max-heap are both complete binary trees satisfying the heap property, but they differ in which extreme value is maintained at the root and therefore which extreme element can be retrieved in O(1).
In a min-heap, the root always contains the minimum value in the entire heap. Every parent is less than or equal to its children. Extracting the minimum takes O(log n). A min-heap is the right choice whenever you need fast access to the smallest element repeatedly: Dijkstra’s shortest path algorithm, Prim’s minimum spanning tree, and implementations of priority queues where lower values have higher priority use min-heaps.
In a max-heap, the root always contains the maximum value. Every parent is greater than or equal to its children. A max-heap is the right choice when you need fast access to the largest element: heap sort uses a max-heap to sort in place, and finding the k largest elements from a stream uses a min-heap of size k (counterintuitively, maintaining a min-heap of the k largest seen elements allows quickly discarding smaller values).
A common interview problem asks to find the kth largest element efficiently: maintain a min-heap of size k, iterate through the array, and push each element, removing the minimum if heap size exceeds k. The root of the min-heap at the end is the kth largest.
Q28. How would you implement a stack using two queues?
Answer: This is a classic data structure implementation problem that tests your understanding of both stacks and queues and your ability to simulate one using the other.
The key challenge is that a stack is LIFO and a queue is FIFO, so you need to reverse the order somehow using the queues. There are two standard approaches, each making one operation costly.
In the push-costly approach: to push a new element, enqueue it into the empty secondary queue, then dequeue all elements from the primary queue into the secondary queue. This reverses the order so the new element ends up at the front. Finally, swap the references so the secondary queue becomes the primary.
Push is O(n) and pop is O(1). In the pop-costly approach: push always enqueues into the primary queue in O(1). To pop, dequeue all but the last element from the primary queue into the secondary queue, then dequeue and return the last element. Swap the references. Pop is O(n) and push is O(1). Interviews often ask for both approaches and a discussion of which is preferable depending on whether push or pop is the more frequent operation.
Q29. Explain how a hash map handles collisions and what determines its performance.
Answer: Hash map performance depends on three factors working together: the quality of the hash function, the collision resolution strategy, and the load factor.
A hash function maps keys to array indices. A good hash function distributes keys uniformly across all available indices, minimising collisions. A poor hash function clusters many keys at the same index, degrading performance.
When two different keys hash to the same index, a collision occurs and must be resolved. Chaining stores a linked list (or balanced BST in modern Java HashMap) at each array index. All entries that hash to the same index are stored in the list. Lookup traverses the list in O(k) where k is the number of entries at that index. Open addressing places the colliding entry into another slot using a probing sequence: linear probing checks the next slot, quadratic probing checks slots at quadratic intervals, and double hashing uses a second hash function.
The load factor is the ratio of stored entries to total array slots. A high load factor means more collisions and slower performance. When the load factor exceeds a threshold (typically 0.75 in Java’s HashMap), the hash table is resized: a new larger array is allocated, typically doubling the size, and all entries are rehashed into the new array. This resizing is O(n) but happens infrequently enough that the amortised cost of insertion remains O(1). The load factor is the key knob for trading memory efficiency against lookup speed.
Q30. When would you choose a graph over a tree to model a problem?
Answer: This question tests your ability to reason about what structural properties your data actually has and which data structure most faithfully represents those relationships.
A tree enforces specific constraints: it is connected, acyclic, and has exactly n-1 edges for n nodes with exactly one path between any two nodes. You should choose a tree when your data naturally has a strict hierarchical structure with no loops: file system directories, HTML document object model, organisational charts, binary decision trees in machine learning, and compiler abstract syntax trees all have exactly one parent per node and no cycles.
A graph should be chosen whenever these tree constraints do not hold: when entities can have multiple predecessors (not just one parent), when cycles are possible or even meaningful, or when the data is not connected. Social networks where any person can be connected to any other are graphs. Road networks where you can drive in circles are graphs.
Dependency graphs where a package can depend on multiple other packages are graphs. Recommendation systems modelling relationships between users and items are bipartite graphs. The general rule: if your domain has hierarchical data with one clear root and parent-child relationships, use a tree. If your domain has arbitrary relationships, multiple predecessors, cycles, or disconnected components, use a graph.
Data Structure Interview Questions by Experience Level
Freshers and Entry-Level
Focus areas: definitions and properties of arrays, linked lists, stacks, and queues; the difference between linear and non-linear structures; hash table operations and collision concepts; basic binary tree traversals (in-order, pre-order, post-order); Big O notation for standard operations on each structure; and simple implementation problems like reversing a linked list or implementing a stack using an array.
Mid-Level Developers (2 to 4 years)
Focus areas: BST properties and operations; heap structure and priority queue applications; graph representations (adjacency list vs matrix); DFS and BFS with their appropriate use cases; sorting algorithm trade-offs between merge sort and quicksort; binary search and its variants; hash map internals including load factor and rehashing; dynamic programming fundamentals with classic problems like Fibonacci and coin change.
Senior Developers (5 or more years)
Focus areas: advanced graph algorithms (topological sort, cycle detection, Dijkstra’s); trie design for prefix-based problems; LRU cache combining hash map and doubly linked list; choosing between data structures for system design contexts; reasoning about cache performance and memory layout trade-offs; and designing custom data structures to meet specific time and space complexity requirements.
How to Prepare for Data Structure Interview Questions
Must-Study Topics in Order
- Arrays and strings: indexing, sliding window, two-pointer, prefix sum patterns
- Linked lists: singly, doubly, cycle detection, reversal, merge operations
- Stacks and queues: LIFO vs FIFO, implementation, expression evaluation, BFS/DFS
- Hash tables: hash functions, collision resolution, load factor, frequency counting
- Binary trees: traversals, height, balanced trees, BST properties and operations
- Heaps: min-heap vs max-heap, priority queues, k-th largest/smallest problems
- Graphs: representations, DFS, BFS, cycle detection, topological sort
- Sorting algorithms: merge sort, quicksort, time/space trade-offs
- Binary search: standard and variant patterns on sorted arrays
- Dynamic programming: memoisation, tabulation, overlapping subproblems
Best Practice Resources
- InterviewBit Data Structure Interview Questions: Comprehensive coverage with coding problems mapped to each structure type.
- Jobaaj Learnings Algorithms Guide: Practical approach to top 10 algorithm and data structure questions with clear explanations.
- LeetCode: The standard platform for data structure practice, organised by topic and difficulty.
- GeeksforGeeks DSA Interview Questions: Topic-wise question banks with detailed explanations for every structure.
- “Introduction to Algorithms” by Cormen (CLRS): The definitive textbook for rigorous understanding of algorithms and data structures.
Interview Day Tips
- Before writing any code, state the data structure you are choosing and explain why it is the right fit for the problem
- Always state the time and space complexity of your solution before the interviewer asks
- Start with a brute-force approach, then discuss optimisations rather than jumping to the optimal solution
- Talk through edge cases out loud: empty input, single element, all duplicates, maximum possible size
- If you get stuck, enumerate the common data structures and ask which one’s properties match what the problem requires
Frequently Asked Questions (FAQ)
What data structures are most commonly tested in technical interviews?
Arrays and strings are the single most frequently tested category. Hash maps follow very closely because they solve frequency counting and lookup problems across almost every domain. Linked lists, stacks, queues, binary trees, and graphs round out the core set. Google explicitly lists arrays, linked lists, stacks, queues, hash sets, hash maps, trees, and graphs as the most frequently tested structures in its hiring guidance. Sorting algorithms, binary search, and dynamic programming are the most frequently tested algorithm topics.
How important is Big O notation in data structure interviews?
It is non-negotiable. Every solution you propose should be followed immediately by its time and space complexity. Interviewers will ask if you do not provide it. More importantly, candidates who can reason about why their solution has a particular complexity, and who can identify improvements, stand out significantly. Know the complexities of standard operations for every major data structure cold before your interview.
Should I memorise data structure implementations?
You should understand implementations thoroughly enough to write them from scratch if asked, but rote memorisation is less valuable than conceptual understanding. Being able to explain why a linked list node needs a next pointer, why a heap uses array indexing instead of explicit pointers, or why a hash table resizes at a certain load factor demonstrates genuine understanding. Interviewers are more impressed by clear reasoning than flawless syntax.
Is dynamic programming a data structure or an algorithm?
Dynamic programming is an algorithm design technique, not a data structure itself. However, DP problems almost always involve choosing the right data structure to store subproblem results, typically an array for one-dimensional DP or a two-dimensional matrix for problems with two varying parameters. DP questions fall under algorithm interview categories, but they require strong data structure reasoning to implement correctly.
How long does it take to prepare for data structure interviews?
With focused daily practice of two to three hours, most candidates feel prepared for entry-level data structure questions within four to six weeks. For mid-level interviews covering graphs, dynamic programming, and advanced tree problems, plan for eight to twelve weeks. For senior roles at top companies where harder LeetCode-style problems are expected, plan for three to four months. Consistent daily practice on a platform like LeetCode, working by topic rather than randomly, is significantly more effective than cramming.
Conclusion
This guide has covered 30 carefully selected data structure interview questions spanning the complete topic landscape: foundational concepts, arrays, linked lists, stacks, queues, hash tables, binary trees, BSTs, heaps, graphs, sorting algorithms, binary search, dynamic programming, tries, and advanced design problems. The questions are chosen not for volume but for depth, reflecting what consistently appears in real technical interviews and what genuinely tests understanding rather than memorisation.
Data structures are not abstract theory. They are the decisions that determine whether your code handles ten million requests per second or ten. The ability to choose the right structure, reason about its trade-offs, and communicate that reasoning clearly is what technical interviewers are evaluating in every question they ask. Build that ability through consistent practice and deep conceptual understanding.
