If you are preparing for a coding round at a product company or a startup in India, mastering DSA interview questions is the single highest-leverage thing you can do. Data Structures and Algorithms form the backbone of almost every technical interview, from campus placements to senior engineering roles at companies like Amazon, Google, Flipkart, Swiggy, Razorpay, and countless well-funded startups. This guide collects 45+ of the most commonly asked DSA interview questions, grouped by topic, with concise and correct answers, approaches, complexity analysis, and short code where it helps.
Whether you are a fresher walking into your first placement drive or an experienced engineer targeting a switch, this article covers the full spectrum: Big-O and complexity, arrays, strings, linked lists, stacks and queues, trees and BSTs, heaps, hashing, graphs, sorting, searching, recursion and backtracking, and dynamic programming. At the end you will find a Big-O cheat sheet, a must-solve problem list, a preparation plan, and a FAQ.
Let us get into it.
DSA Basics, Complexity, and Big-O
Interviewers almost always open with fundamentals to check whether you actually understand what you are optimizing. Nail these and you set a confident tone.
1. What is a data structure and why do we need it?
A data structure is a way of organizing and storing data so that it can be accessed and modified efficiently. We need them because the right structure reduces time and space costs for the operations we perform most often. For example, a hash table gives near constant-time lookups, while a balanced tree keeps data sorted with logarithmic operations. Choosing the correct structure is often the difference between a solution that passes and one that times out.
2. What is the difference between linear and non-linear data structures?
In a linear structure, elements are arranged sequentially and each element has a single predecessor and successor. Examples: arrays, linked lists, stacks, queues. In a non-linear structure, elements are arranged hierarchically or as a network, so an element can connect to multiple others. Examples: trees and graphs.
3. What is Big-O notation?
Big-O notation describes the upper bound on the growth rate of an algorithm's running time or space as the input size grows. It expresses the worst-case behavior while ignoring constants and lower-order terms. For example, O(n) means the work grows linearly with input size, while O(log n) means it grows very slowly. Interviewers care about Big-O because it predicts how your code behaves at scale, not on tiny test cases.
4. What is the difference between Big-O, Big-Omega, and Big-Theta?
- Big-O is the upper bound (worst case).
- Big-Omega is the lower bound (best case).
- Big-Theta is a tight bound, meaning the algorithm's growth is bounded above and below by the same function.
In interviews, unless asked otherwise, always analyze worst-case Big-O.
5. What is time complexity versus space complexity?
Time complexity measures how the number of operations grows with input size. Space complexity measures how much extra memory an algorithm uses relative to input size, excluding the input itself. A good answer weighs both: a faster algorithm that uses too much memory can fail on constrained systems.
6. What is amortized time complexity?
Amortized complexity is the average time per operation over a sequence of operations, even if a single operation is occasionally expensive. The classic example is a dynamic array (like Java's ArrayList or Python's list): most appends are O(1), but when it needs to resize it copies all elements in O(n). Averaged across many appends, each append is O(1) amortized.
Arrays
Arrays are the most fundamental structure and dominate coding rounds, especially two-pointer and sliding-window questions.
7. What is an array and what are its advantages and limitations?
An array stores elements of the same type in contiguous memory, giving O(1) random access by index. Advantages: fast indexed access and cache-friendliness. Limitations: fixed size in static arrays, and insertion or deletion in the middle is O(n) because elements must shift.
8. How do you find the maximum subarray sum? (Kadane's Algorithm)
Approach: Track a running sum and reset it to the current element whenever it drops below that element. Keep the best sum seen so far.
maxSoFar = maxHere = arr[0]
for i from 1 to n-1:
maxHere = max(arr[i], maxHere + arr[i])
maxSoFar = max(maxSoFar, maxHere)
return maxSoFar
Complexity: O(n) time, O(1) space.
9. How do you remove duplicates from a sorted array in place?
Approach: Use two pointers. A slow pointer marks the position of the last unique element, and a fast pointer scans ahead. When the fast pointer finds a new value, write it just after the slow pointer.
Complexity: O(n) time, O(1) space.
10. What is the two-pointer technique?
The two-pointer technique uses two indices moving through the array (from both ends, or one slow and one fast) to solve problems in O(n) instead of O(n squared). It is ideal for sorted arrays: pair-sum, container-with-most-water, and removing duplicates. Interviewers love it because it shows you can avoid brute force.
11. What is the sliding-window technique?
Sliding window maintains a contiguous range of elements and slides it across the array while updating an aggregate (sum, count, max). It converts many O(n squared) subarray problems into O(n). Use it for "longest substring without repeating characters" or "maximum sum subarray of size k."
Strings
String problems test pattern recognition, hashing, and careful index handling.
12. How do you check if two strings are anagrams?
Approach: Count the frequency of each character in both strings and compare the counts, or sort both strings and compare. The counting approach is O(n); sorting is O(n log n).
13. How do you check if a string is a palindrome?
Approach: Use two pointers, one at each end, moving inward and comparing characters. If all pairs match, it is a palindrome.
Complexity: O(n) time, O(1) space.
14. How do you find the longest substring without repeating characters?
Approach: Sliding window with a hash set or map. Expand the right boundary and add characters; when a duplicate appears, shrink from the left until the duplicate is removed. Track the maximum window length.
Complexity: O(n) time.
15. What are the KMP and Rabin-Karp algorithms?
Both are pattern-matching algorithms. KMP (Knuth-Morris-Pratt) precomputes a prefix table so that on a mismatch it skips ahead without re-checking characters, giving O(n + m) time. Rabin-Karp uses a rolling hash to compare the pattern's hash with each window's hash, giving average O(n + m) but O(n times m) in the worst case due to hash collisions.
Linked Lists
Pointer manipulation questions are a staple, and they separate people who truly understand references from those who memorized.
16. What is a linked list and how does it differ from an array?
A linked list is a linear structure where each node holds data and a pointer to the next node. Unlike arrays, nodes are not contiguous, so there is no O(1) random access; you traverse from the head. However, insertion and deletion at a known position are O(1) because you only rewire pointers, without shifting elements.
17. What are the types of linked lists?
- Singly linked list: each node points to the next only.
- Doubly linked list: each node points to both next and previous.
- Circular linked list: the last node points back to the head, forming a loop.
18. How do you reverse a linked list?
Approach: Iterate through the list, reversing the next pointer of each node while keeping track of the previous node.
prev = null
curr = head
while curr != null:
nextNode = curr.next
curr.next = prev
prev = curr
curr = nextNode
return prev
Complexity: O(n) time, O(1) space.
19. How do you detect a cycle in a linked list?
Approach: Use Floyd's cycle-detection (tortoise and hare). Move one pointer one step and another two steps. If they meet, there is a cycle. If the fast pointer reaches null, there is no cycle.
Complexity: O(n) time, O(1) space.
20. How do you find the middle of a linked list?
Approach: Use slow and fast pointers. Move slow one step and fast two steps. When fast reaches the end, slow is at the middle. O(n) time, O(1) space.
21. How do you merge two sorted linked lists?
Approach: Use a dummy head node and compare the front nodes of both lists, attaching the smaller one each time, then advancing that list. Append the remaining nodes at the end. O(n + m) time.
Stacks and Queues
These test whether you can pick the right LIFO or FIFO structure for a problem.
22. What is a stack and what are its main operations?
A stack is a Last-In-First-Out (LIFO) structure. Main operations: push (add to top), pop (remove from top), and peek or top (view the top element). All are O(1). Stacks power function-call management, undo features, and expression evaluation.
23. What is a queue and how does it differ from a stack?
A queue is a First-In-First-Out (FIFO) structure with enqueue (add at rear) and dequeue (remove from front). The difference is order: a stack removes the most recently added element, while a queue removes the oldest. Queues are used in BFS, scheduling, and buffering.
24. How do you check for balanced parentheses?
Approach: Push every opening bracket onto a stack. For each closing bracket, pop and check that it matches the expected opening type. The string is balanced if the stack is empty at the end.
Complexity: O(n) time, O(n) space.
25. What is the next-greater-element problem and how do you solve it?
For each element, find the next element to its right that is larger. Approach: Use a monotonic decreasing stack. Traverse the array; while the current element is greater than the stack's top, that current element is the answer for the popped index. This gives O(n) instead of O(n squared).
26. How do you implement a queue using two stacks?
Approach: Use an input stack and an output stack. On enqueue, push to the input stack. On dequeue, if the output stack is empty, pour all elements from input to output (reversing order), then pop from output. Each element moves at most twice, so operations are amortized O(1).
27. What is a deque and a priority queue?
A deque (double-ended queue) allows insertion and deletion at both ends. A priority queue returns elements by priority rather than insertion order, and it is typically implemented with a heap, giving O(log n) insertion and removal of the highest or lowest priority element.
Trees and Binary Search Trees
Tree questions appear in almost every product-company interview in India.
28. What is a binary tree and a binary search tree?
A binary tree is a tree where each node has at most two children. A binary search tree (BST) is a binary tree with an ordering property: every node's left subtree contains smaller values and its right subtree contains larger values. This ordering enables O(log n) search, insert, and delete on a balanced BST.
29. What are the tree traversal methods?
- Inorder (Left, Root, Right): for a BST, visits nodes in sorted order.
- Preorder (Root, Left, Right): used to copy a tree or build prefix expressions.
- Postorder (Left, Right, Root): used to delete a tree or build postfix expressions.
- Level-order (BFS): visits nodes level by level using a queue.
30. How do you find the height of a binary tree?
Approach: Recursively compute the height of the left and right subtrees and return one plus the maximum of the two. Height of an empty tree is defined as -1 (or 0 for node count).
height(node):
if node is null: return -1
return 1 + max(height(node.left), height(node.right))
Complexity: O(n) time.
31. How do you check if a binary tree is a valid BST?
Approach: Do an inorder traversal and verify the values come out strictly increasing, or recurse while passing down a valid (min, max) range for each node. O(n) time.
32. What is a balanced tree, and what are AVL and Red-Black trees?
A balanced tree keeps its height close to log n so operations stay logarithmic. An AVL tree is a self-balancing BST that maintains a height difference of at most one between subtrees, using rotations. A Red-Black tree is a self-balancing BST that uses node coloring rules to guarantee the longest path is at most twice the shortest, offering faster insertions than AVL at the cost of slightly slower lookups. Red-Black trees back many standard library maps.
33. What is the lowest common ancestor (LCA)?
The LCA of two nodes is the deepest node that has both as descendants. In a BST, walk down from the root: if both target values are smaller, go left; if both are larger, go right; otherwise the current node is the LCA. O(h) time where h is the height.
Heaps
34. What is a heap and what is it used for?
A heap is a complete binary tree satisfying the heap property: in a min-heap, every parent is smaller than its children; in a max-heap, every parent is larger. It supports finding the min or max in O(1) and inserting or removing it in O(log n). Heaps power priority queues, heap sort, and problems like "find the k largest elements" or "merge k sorted lists."
35. How do you find the kth largest element in an array?
Approach: Maintain a min-heap of size k. Push elements; when the heap exceeds size k, pop the smallest. After processing all elements, the heap's root is the kth largest. Complexity: O(n log k) time. (Quickselect is an alternative averaging O(n).)
Hashing
Hashing questions test both concept and practical trade-offs.
36. What is hashing and how does a hash table work?
Hashing maps keys to indices in an array using a hash function, enabling average O(1) insertion, deletion, and lookup. A hash table stores key-value pairs at those computed indices. The efficiency depends on a good hash function that spreads keys evenly to minimize collisions.
37. What is a hash collision and how is it resolved?
A collision happens when two different keys map to the same index. The two common resolutions are: chaining (each bucket holds a linked list or tree of entries) and open addressing (probe for the next free slot using linear probing, quadratic probing, or double hashing). In the worst case, poor hashing degrades lookups to O(n).
38. How do you implement an LRU cache?
Approach: Combine a hash map with a doubly linked list. The hash map gives O(1) lookup of nodes, and the doubly linked list maintains usage order, with the most recently used at the front. On access, move the node to the front; on insertion beyond capacity, evict the node at the back. All operations are O(1). This is one of the most frequently asked design-flavored DSA problems in Indian product-company interviews.
Graphs
Graph questions show up often for mid and senior roles.
39. How is a graph represented?
Two common ways: an adjacency matrix (a V by V grid where cell [i][j] marks an edge, using O(V squared) space, good for dense graphs) and an adjacency list (each vertex stores a list of its neighbors, using O(V + E) space, good for sparse graphs). Adjacency lists are the default choice in most interviews.
40. What is the difference between BFS and DFS?
BFS (Breadth-First Search) explores level by level using a queue and finds the shortest path in an unweighted graph. DFS (Depth-First Search) explores as deep as possible using recursion or a stack and is used for cycle detection, topological sorting, and connected components. Both run in O(V + E).
41. How do you detect a cycle in a graph?
In an undirected graph, run DFS and if you reach an already-visited node that is not the parent, there is a cycle. In a directed graph, use DFS with a recursion stack (three-color marking); reaching a node currently in the recursion stack means a back edge and therefore a cycle.
42. What is topological sorting?
Topological sort orders the vertices of a directed acyclic graph (DAG) so that every edge goes from an earlier vertex to a later one. It is used for scheduling tasks with dependencies, like build systems or course prerequisites. It is computed via DFS finishing times or Kahn's algorithm (repeatedly removing zero in-degree nodes). O(V + E).
43. What is Dijkstra's algorithm?
Dijkstra's algorithm finds the shortest path from a source to all vertices in a weighted graph with non-negative edges. It greedily picks the closest unvisited vertex using a min-heap and relaxes its neighbors. Complexity: O((V + E) log V) with a binary heap. For graphs with negative edges, use Bellman-Ford instead.
Sorting Algorithms
44. Compare the common sorting algorithms.
- Bubble, Selection, Insertion Sort: simple, O(n squared), fine for tiny or nearly sorted inputs.
- Merge Sort: stable, O(n log n) always, but O(n) extra space. Divide and conquer.
- Quick Sort: O(n log n) average, O(n squared) worst case (bad pivots), in-place, and usually fastest in practice.
- Heap Sort: O(n log n), in-place, not stable.
- Counting and Radix Sort: non-comparison sorts that reach O(n) or O(nk) for integers in a bounded range.
45. What is a stable sort?
A stable sort preserves the relative order of elements that compare equal. This matters when sorting records by multiple keys. Merge sort and counting sort are stable; quick sort and heap sort are not (unless modified).
46. When would you prefer merge sort over quick sort?
Prefer merge sort when you need guaranteed O(n log n) worst-case time, when stability is required, or when sorting linked lists (where merge sort works without random access). Prefer quick sort for in-memory arrays where average speed and low memory matter most.
Searching
47. How does binary search work?
Binary search finds a target in a sorted array by repeatedly halving the search range: compare the middle element, then search the left or right half. Complexity: O(log n). It requires the data to be sorted.
low = 0, high = n-1
while low <= high:
mid = low + (high - low) / 2
if arr[mid] == target: return mid
else if arr[mid] < target: low = mid + 1
else: high = mid - 1
return -1
48. How do you search in a rotated sorted array?
Approach: Modified binary search. At each step, one half of the array is guaranteed to be sorted. Determine which half is sorted, check whether the target lies within that sorted half's range, and discard the other half. Complexity: O(log n).
Recursion and Backtracking
49. What is recursion and what are its components?
Recursion is when a function calls itself to solve smaller instances of a problem. Every recursion needs a base case (a condition to stop) and a recursive case (the self-call on a smaller input). Missing or wrong base cases cause stack overflow. Recursion trades clarity for extra stack space of O(depth).
50. What is backtracking?
Backtracking is a refined brute force that builds a solution incrementally and abandons a partial candidate ("backtracks") as soon as it cannot lead to a valid solution. It is used for constraint problems: N-Queens, Sudoku, generating permutations and combinations, and maze solving.
51. How do you solve the N-Queens problem?
Approach: Place queens row by row. For each row, try each column; if the position is not attacked by any previously placed queen (check column and both diagonals), place the queen and recurse to the next row. If no column works, backtrack. It explores the solution space using depth-first search with pruning.
Dynamic Programming Basics
DP separates strong candidates from average ones and is heavily weighted at top product companies.
52. What is dynamic programming?
Dynamic programming (DP) 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 (the optimal solution is built from optimal subsolutions) and overlapping subproblems (the same subproblems recur).
53. What is the difference between memoization and tabulation?
Memoization is top-down: you write the natural recursion and cache results as you go. Tabulation is bottom-up: you fill a table iteratively from the smallest subproblems upward. Memoization is easier to write from a recursive idea; tabulation avoids recursion overhead and stack limits.
54. What is the difference between greedy and dynamic programming?
A greedy algorithm makes the locally optimal choice at each step and never reconsiders, which is fast but only correct when local choices lead to a global optimum (like Dijkstra or Huffman coding). DP explores all relevant choices and combines subproblem solutions, so it is correct for problems where greedy fails, such as 0/1 knapsack.
55. What is the 0/1 knapsack problem?
Given items with weights and values and a capacity, select a subset that maximizes total value without exceeding capacity, where each item is either taken or not. Approach: Build a DP table where dp[i][w] is the best value using the first i items with capacity w. Complexity: O(n times W) time and space.
56. What is the longest common subsequence (LCS)?
Given two strings, find the length of the longest subsequence present in both (not necessarily contiguous). Approach: DP table where dp[i][j] is the LCS length of the first i and first j characters; if characters match, add one to the diagonal, else take the max of the neighbors. Complexity: O(m times n).
Common Coding-Round Problems With Approach
These are the exact patterns that recur across placement drives and product-company loops in India. Practicing the pattern matters more than memorizing any one problem.
- Two Sum: Use a hash map to store seen values and check for the complement in O(n).
- Trapping Rain Water: Two-pointer or precomputed max-left and max-right arrays, O(n).
- Merge Intervals: Sort by start time, then merge overlapping intervals, O(n log n).
- Number of Islands: BFS or DFS flood fill over a grid, O(rows times cols).
- Coin Change: DP over amounts, O(amount times coins).
- Word Break: DP over string prefixes with a dictionary set.
- Level-order and Zigzag traversal: BFS with a queue, reversing alternate levels.
- Infix to Postfix conversion: Stack-based using operator precedence.
- Detect and remove loop in a linked list: Floyd's algorithm, then reset one pointer.
Practicing these under time pressure is what separates a confident interview from a shaky one. Running a few timed sessions with the Goodspace AI Mock Interview helps you rehearse explaining your approach out loud, which is exactly what interviewers score you on.
Big-O Cheat Sheet
Average-case complexity for common operations. Keep this in your head.
| Data Structure | Access | Search | Insertion | Deletion |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) |
| Dynamic Array | O(1) | O(n) | O(1) amortized | O(n) |
| Stack | O(n) | O(n) | O(1) | O(1) |
| Queue | O(n) | O(n) | O(1) | O(1) |
| Singly Linked List | O(n) | O(n) | O(1) | O(1) |
| Hash Table | N/A | O(1) | O(1) | O(1) |
| Binary Search Tree (balanced) | O(log n) | O(log n) | O(log n) | O(log n) |
| Binary Search Tree (worst) | O(n) | O(n) | O(n) | O(n) |
| Heap | O(1) find-min/max | O(n) | O(log n) | O(log n) |
Sorting algorithm complexity:
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes |
| Insertion Sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick Sort | O(n log n) | O(n log n) | O(n^2) | O(log n) | No |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(k) | Yes |
Must-Solve Problems Before Any DSA Interview
If you are short on time, solve these high-frequency problems across the core patterns first:
- Two Sum (hashing)
- Maximum Subarray, Kadane's (arrays)
- Longest Substring Without Repeating Characters (sliding window)
- Valid Parentheses (stack)
- Reverse a Linked List (linked list)
- Detect Cycle in a Linked List (two pointers)
- Merge Two Sorted Lists (linked list)
- Binary Tree Level-Order Traversal (BFS)
- Validate BST (trees)
- Lowest Common Ancestor (trees)
- Kth Largest Element (heap)
- Number of Islands (graph, DFS or BFS)
- Course Schedule, topological sort (graph)
- Coin Change (DP)
- Longest Common Subsequence (DP)
- Climbing Stairs (DP intro)
- Search in Rotated Sorted Array (binary search)
- Trapping Rain Water (two pointers)
- Merge Intervals (sorting)
- Implement an LRU Cache (design plus hashing)
How to Prepare for a DSA Interview
1. Build the foundation topic by topic. Do not jump straight to hard problems. Learn each data structure, implement it once yourself, then solve five to ten problems per topic before moving on. Follow roughly this order: arrays and strings, hashing, two pointers and sliding window, linked lists, stacks and queues, trees, heaps, graphs, then DP.
2. Learn patterns, not problems. There are around 15 recurring patterns (sliding window, two pointers, fast and slow pointers, BFS or DFS, backtracking, top-k with heaps, binary search on answer, DP subsets). Recognizing the pattern from the problem statement is the real skill.
3. Solve consistently and time yourself. Aim for two to four problems a day over several weeks rather than cramming. Simulate the real constraint: 30 to 45 minutes per medium problem. Indian coding rounds on platforms like HackerRank, HackerEarth, and CodeSignal are strictly timed, so speed matters.
4. Practice explaining out loud. In an interview you must think aloud, state your approach, discuss complexity, and handle follow-ups before coding. This communication is scored as heavily as correctness, and it is the part most self-study skips. Rehearsing with a Goodspace AI Mock Interview lets you practice narrating your reasoning and get feedback on both your solution and your delivery.
5. Revisit and revise. Keep a sheet of problems you got wrong and redo them after a week. Spaced repetition on your weak patterns beats endless new problems.
6. Always analyze complexity. For every problem you solve, state the time and space complexity and ask whether it can be improved. Interviewers frequently push you from a brute-force O(n squared) toward an optimal O(n) solution.
Frequently Asked Questions
How many DSA questions should I solve before interviews? Quality beats quantity. Roughly 150 to 250 well-chosen problems covering all core patterns is enough for most roles, as long as you understand each deeply rather than just passing test cases. Focus on the must-solve list above first.
Which DSA topics are most important for coding rounds in India? Arrays and strings, hashing, two pointers and sliding window, trees, graphs (BFS or DFS), and dynamic programming appear most often. Product companies weight trees, graphs, and DP more heavily, while many startup and service-company rounds lean on arrays, strings, and hashing.
Are DSA interviews only for freshers? No. Experienced engineers face DSA rounds too, often alongside system design. The bar can be higher, with an expectation of clean code, optimal complexity, and clear trade-off discussion, but the core topics are the same.
Which programming language is best for DSA interviews? Use the language you are most fluent in. C++, Java, and Python are all widely accepted. Python is concise for interviews, C++ is fast and has strong standard library containers, and Java is common in enterprise settings. What matters is fluency with your language's standard data structures.
How long does it take to prepare for DSA interviews? With consistent daily practice, most people need eight to twelve weeks to go from basics to interview-ready. If you already know the fundamentals, a focused four to six week revision of patterns and mock interviews is often enough.
Is it enough to just memorize solutions? No. Interviewers change constraints and ask follow-ups, so memorized code breaks quickly. Understand why an approach works, what its complexity is, and how to adapt it. That understanding is what lets you handle a problem you have never seen.
Final Thoughts
DSA interviews reward structured preparation far more than raw talent. Cover each topic in this guide, drill the must-solve list, internalize the Big-O cheat sheet, and practice explaining your reasoning under time pressure. Do that consistently and you will walk into your next coding round genuinely ready. Good luck.
