Data Structures Interview Questions
Data structures are the backbone of almost every coding interview and system-design discussion. These are the questions interviewers actually ask, with concise answers you can speak confidently.
17 questions with concise, interview-ready answers.
1. What is a data structure, and why does the choice matter?
A data structure is a way of organizing and storing data so it can be accessed and modified efficiently. The right choice determines the time and space cost of operations like search, insert, and delete, which can be the difference between an algorithm that runs in milliseconds and one that times out. Interviewers care because picking the correct structure is often the core of solving a problem efficiently.
2. What is Big-O notation, and what do time and space complexity mean?
Big-O notation describes how an algorithm's running time or memory usage grows as the input size n grows, focusing on the dominant term and ignoring constants. Time complexity measures the number of operations performed, while space complexity measures the extra memory used beyond the input. Common classes from fastest to slowest are O(1), O(log n), O(n), O(n log n), O(n^2), and O(2^n).
3. What is the difference between an array and a linked list?
An array stores elements in contiguous memory, giving O(1) access by index but O(n) cost to insert or delete in the middle because elements must shift. A linked list stores elements as nodes connected by pointers, so inserting or deleting at a known position is O(1), but accessing an element requires walking the list in O(n) and it uses extra memory for the pointers. Use arrays when you need fast random access and linked lists when you do frequent insertions and deletions.
4. What are the time complexities of common array operations?
Accessing an element by index is O(1) because the address is computed directly. Searching an unsorted array is O(n), while inserting or deleting at the end of a dynamic array is amortized O(1). Inserting or deleting at the beginning or middle is O(n) because the remaining elements must be shifted.
5. What is a dynamic array, and what is amortized O(1) append?
A dynamic array, such as a Python list or Java ArrayList, automatically grows when it runs out of capacity by allocating a larger block and copying the elements over. Most appends are O(1), but the occasional resize is O(n); spread across many appends the average cost per append is still constant, which is called amortized O(1). Doubling the capacity on each resize is what keeps the amortized cost constant.
6. What is a stack, and where is it used?
A stack is a last-in, first-out (LIFO) structure where you push items onto the top and pop them off the top, both in O(1). It is used for function call management (the call stack), undo features, expression evaluation, and depth-first search. You can implement it with either an array or a linked list.
7. What is a queue, and how does it differ from a stack?
A queue is a first-in, first-out (FIFO) structure where you enqueue at the back and dequeue from the front, both in O(1). Unlike a stack, which removes the most recently added item, a queue removes the oldest item first. Queues are used for breadth-first search, task scheduling, and buffering; variants include the deque (double-ended) and the circular queue.
8. How does a hash table work, and what is its average lookup time?
A hash table stores key-value pairs by passing the key through a hash function that maps it to an index in an underlying array. This gives average O(1) time for insert, delete, and lookup. In the worst case, when many keys collide into the same bucket, operations can degrade to O(n), which is why a good hash function and resizing matter.
9. What is a hash collision, and how is it handled?
A collision occurs when two different keys hash to the same index. The two common resolution strategies are separate chaining, where each bucket holds a linked list (or tree) of entries that share the index, and open addressing, where the table probes for the next free slot using methods like linear or quadratic probing. Keeping the load factor low and resizing the table helps keep collisions rare.
10. What is a binary tree, and how does it differ from a binary search tree?
A binary tree is a hierarchical structure where each node has at most two children, called left and right. A binary search tree (BST) adds an ordering rule: every node's left subtree contains only smaller keys and its right subtree only larger keys. That ordering makes search, insert, and delete run in O(log n) on a balanced tree, versus O(n) for an unordered binary tree.
11. Why can a binary search tree degrade to O(n), and how is that fixed?
If keys are inserted in sorted order, a plain BST becomes a long chain resembling a linked list, so operations degrade from O(log n) to O(n). Self-balancing trees fix this by restructuring after insertions and deletions to keep the height around log n. Common examples are AVL trees and red-black trees, the latter being used in many standard library map and set implementations.
12. What are the tree traversal methods?
Depth-first traversals visit nodes recursively in three orders: in-order (left, node, right), which yields sorted output for a BST; pre-order (node, left, right), useful for copying a tree; and post-order (left, right, node), useful for deleting a tree. Breadth-first traversal, also called level-order, visits nodes level by level using a queue. All four visit every node once, so they run in O(n).
13. What is a heap, and what is it used for?
A heap is a complete binary tree that satisfies the heap property: in a min-heap every parent is smaller than its children, and in a max-heap every parent is larger. This lets you find the minimum or maximum in O(1) and insert or remove the root in O(log n). Heaps are the standard implementation behind priority queues and are used in algorithms like Dijkstra's shortest path and heap sort.
14. What is a graph, and what are the two main ways to represent one?
A graph is a set of vertices (nodes) connected by edges, which may be directed or undirected and weighted or unweighted. The two common representations are an adjacency list, which stores for each vertex a list of its neighbors and is memory-efficient for sparse graphs, and an adjacency matrix, a two-dimensional array that gives O(1) edge lookups but uses O(V^2) space. Choose the list for sparse graphs and the matrix for dense graphs or frequent edge queries.
15. What is the difference between BFS and DFS on a graph?
Breadth-first search (BFS) explores a graph level by level using a queue, and on an unweighted graph it finds the shortest path in terms of number of edges. Depth-first search (DFS) explores as far as possible along each branch before backtracking, using a stack or recursion, and is well suited to detecting cycles, topological sorting, and exploring connected components. Both run in O(V + E) time using an adjacency list.
16. How do you decide which data structure to use for a problem?
Match the structure to the operations you do most often. If you need fast key-based lookups, reach for a hash table; if you need sorted order with fast search, a balanced BST or sorted array; if you repeatedly need the smallest or largest item, a heap; and if you need LIFO or FIFO processing, a stack or queue. Always weigh the time complexity of the critical operations against the memory the structure consumes.
17. What is the difference between a stack and a heap in memory?
In the context of program memory, the stack is a region that stores function call frames, local variables, and return addresses, managed automatically in LIFO order and very fast to allocate. The heap is a larger region for dynamically allocated memory that lives beyond a single function call and must be managed manually or by a garbage collector. This memory heap is unrelated to the heap data structure, which is a tree-based priority queue, and interviewers sometimes ask the question to check that you know the difference.
Get these answered live in your real interview
NostrobeAI is a real-time AI interview copilot — it hears the question and drafts a strong answer on your screen, invisible on Zoom, Meet, and Teams. One-time pricing, no subscription.
Try NostrobeAI free