Data Structures & Algorithms (DSA) interview questions & answers
Data Structures & Algorithms is the study of how to organize data in memory (data structures) and the step-by-step procedures that operate on that data (algorithms). Interviewers use DSA to gauge how you reason about correctness, efficiency, and trade-offs in time and space. Mastery means choosing the right structure for a problem and analyzing the cost of your solution.
Updated 2026-06-18 · 16 real, commonly-asked questions with answers.
Key takeaways
- Data Structures & Algorithms is the study of how to organize data in memory (data structures) and the step-by-step procedures that operate on that data (algorithms).
- Core areas to revise for Data Structures & Algorithms (DSA): Arrays & strings, Linked lists, Trees & graphs, Hashing, Sorting & searching.
- This guide answers 16 of the most-asked Data Structures & Algorithms (DSA) interview questions — rehearse them in OnJob's free AI mock interview.
Top 16 Data Structures & Algorithms (DSA) interview questions
Q1.What is the difference between an array and a linked list?
An array stores elements in contiguous memory, giving O(1) indexed access but O(n) insertion or deletion in the middle due to shifting. A linked list stores nodes with pointers, giving O(1) insertion or deletion at a known node but O(n) access because you must traverse from the head. Arrays have better cache locality, while linked lists waste memory on pointers but grow without reallocation.
Q2.What is Big O notation and why does it matter?
Big O notation describes the asymptotic upper bound on how an algorithm's running time or space grows as input size increases. It lets you compare algorithms independent of hardware by focusing on the dominant term and ignoring constants. For example, O(n log n) sorting scales far better than O(n squared) for large inputs.
Q3.Explain the difference between a stack and a queue.
A stack is a LIFO (last-in, first-out) structure where the most recently added element is removed first, supporting push and pop. A queue is a FIFO (first-in, first-out) structure where the oldest element is removed first, supporting enqueue and dequeue. Stacks suit recursion and backtracking, while queues suit scheduling and breadth-first traversal.
Q4.How does a hash table work and what is its time complexity?
A hash table maps keys to values by applying a hash function that converts a key into an array index. Lookups, insertions, and deletions average O(1) but can degrade to O(n) when many keys collide into one bucket. Good hash functions and collision strategies like chaining or open addressing keep performance near constant time.
Q5.What is a binary search tree and when does it perform poorly?
A binary search tree keeps each node's left subtree smaller and right subtree larger than the node, enabling O(log n) search, insert, and delete when balanced. It degrades to O(n) when inserted in sorted order, because it becomes a linked list. Self-balancing variants like AVL or red-black trees keep height logarithmic.
Q6.Explain the difference between BFS and DFS.
Breadth-first search explores a graph level by level using a queue, finding the shortest path in unweighted graphs. Depth-first search explores as far as possible along one branch before backtracking, typically using recursion or a stack. BFS uses more memory for wide graphs, while DFS uses less but can go very deep.
Q7.What is dynamic programming?
Dynamic programming solves problems by breaking them into overlapping subproblems and storing each subproblem's result to avoid recomputation. It applies when a problem has optimal substructure and overlapping subproblems, such as the Fibonacci sequence or the knapsack problem. Memoization (top-down) and tabulation (bottom-up) are the two standard implementation styles.
Q8.How does quicksort work and what is its time complexity?
Quicksort picks a pivot, partitions the array so smaller elements go left and larger go right, then recursively sorts each partition. Its average time is O(n log n), but a poor pivot choice on already-sorted data gives O(n squared) worst case. It sorts in place with O(log n) stack space and is usually faster in practice than mergesort.
Q9.What is the difference between mergesort and quicksort?
Mergesort always runs in O(n log n) and is stable, but it needs O(n) extra space for merging. Quicksort averages O(n log n), sorts in place, and is often faster due to cache friendliness, but its worst case is O(n squared) and it is not stable. Mergesort is preferred when stability or guaranteed performance matters.
Q10.Explain what a heap is and its main use.
A heap is a complete binary tree where every parent is ordered relative to its children: a min-heap keeps the smallest at the root, a max-heap the largest. It supports O(log n) insertion and removal of the root and O(1) peek at the extreme element. Heaps power priority queues and the heapsort algorithm.
Q11.What is a graph and how can it be represented?
A graph is a set of vertices connected by edges, which may be directed or undirected and weighted or unweighted. Two common representations are an adjacency matrix, which uses O(V squared) space and gives O(1) edge lookup, and an adjacency list, which uses O(V plus E) space and is better for sparse graphs. The choice depends on graph density and the operations needed.
Q12.What is recursion and what are its risks?
Recursion is when a function calls itself to solve smaller instances of a problem until reaching a base case. It can express tree and divide-and-conquer algorithms cleanly. The risks are stack overflow from too-deep calls and redundant work when subproblems overlap, which memoization or an iterative rewrite can fix.
Q13.Explain the two-pointer technique.
The two-pointer technique uses two indices that move through a data structure to solve a problem in a single pass. It commonly works on sorted arrays, such as finding a pair that sums to a target by moving pointers inward from both ends. It reduces many brute-force O(n squared) solutions to O(n).
Q14.What is the time complexity of binary search and what does it require?
Binary search runs in O(log n) time by repeatedly halving the search range. It requires the data to be sorted, because it compares the target to the middle element and discards half the range each step. On unsorted data you must sort first or use linear search instead.
Q15.What is the difference between O(1), O(n), and O(log n) complexity?
O(1) means the running time is constant regardless of input size, like accessing an array index. O(n) means time grows linearly with input, like scanning a list once. O(log n) means time grows very slowly as input doubles, like binary search, because each step eliminates a large fraction of the remaining work.
Q16.What is a trie and when is it useful?
A trie, or prefix tree, stores strings character by character along tree paths, with shared prefixes sharing nodes. It gives O(m) lookup, insert, and prefix search where m is the key length, independent of the number of stored words. Tries excel at autocomplete, spell-checking, and prefix-matching problems.
More interview topics
Practise & prepare
Practise Data Structures & Algorithms (DSA) out loud
Reading answers is step one. Rehearse them in OnJob's free AI mock interview, get instant feedback, then apply to AI-matched jobs in one click.