100 DSA interview question and answer

Here’s a list of common 100 DSA interview question and answer. This should help you prepare for technical interviews.

Array

1. What is an array?
   • A collection of elements identified by index or key.
2. How do you find the largest and smallest element in an array?
   • Traverse the array, keeping track of the largest and smallest elements.
3. How do you reverse an array in place?
   • Swap the first element with the last, the second with the second last, and so on.
4. How do you find duplicates in an array?
   • Use a hash set to track elements you’ve seen before.
5. How do you find the maximum subarray sum (Kadane’s Algorithm)?
   • Iterate through the array, maintaining the maximum sum of the subarray ending at each position.

Linked List

6. What is a linked list?
   • A sequence of nodes where each node contains data and a reference to the next node.
7. How do you reverse a linked list?
   • Change the next pointers of each node to point to the previous node.
8. How do you detect a cycle in a linked list?
   • Use Floyd’s Cycle-Finding Algorithm (Tortoise and Hare).
9. How do you find the middle of a linked list?
   • Use two pointers, one moving twice as fast as the other.
10. How do you merge two sorted linked lists?
    • Iterate through both lists, inserting nodes in sorted order into a new list.

Stack

11. What is a stack?
    • A collection of elements that follows the Last-In-First-Out (LIFO) principle.
12. How do you implement a stack using arrays?
    • Use an array with a variable to track the index of the top element.
13. How do you implement a stack using linked lists?
    • Use a linked list where insertions and deletions happen at the head.
14. What is the purpose of the stack in function calls?
    • To store return addresses, local variables, and manage function calls.
15. How do you evaluate a postfix expression using a stack?
    • Traverse the expression, using the stack to store operands and applying operators as encountered.

Queue

16. What is a queue?
    • A collection of elements that follows the First-In-First-Out (FIFO) principle.
17. How do you implement a queue using arrays?
    • Use an array with two indices to track the front and rear of the queue.
18. How do you implement a queue using linked lists?
    • Use a linked list where insertions happen at the tail and deletions at the head.
19. What is a priority queue?
    • A type of queue where each element has a priority, and elements are served based on priority.
20. How do you implement a circular queue?
    • Use an array where the end wraps around to the beginning using modulo operations.

Tree

21. What is a binary tree?
    • A tree where each node has at most two children.
22. How do you perform in-order traversal of a binary tree?
    • Traverse the left subtree, visit the root, traverse the right subtree.
23. How do you perform pre-order traversal of a binary tree?
    • Visit the root, traverse the left subtree, traverse the right subtree.
24. How do you perform post-order traversal of a binary tree?
    • Traverse the left subtree, traverse the right subtree, visit the root.
25. What is a binary search tree (BST)?
    • A binary tree where for each node, the left children are less than the node and the right children are greater.
26. How do you insert a node in a BST?
    • Compare the new value with the root and recursively insert it in the left or right subtree.
27. How do you delete a node in a BST?
    • Handle three cases: node is a leaf, node has one child, node has two children (replace with in-order successor).
28. How do you find the height of a binary tree?
    • Recursively find the height of left and right subtrees and return the maximum of the two plus one.
29. How do you check if a binary tree is balanced?
    • Ensure the height difference between left and right subtrees of every node is at most one.
30. What is a balanced binary tree?
    • A binary tree where the height of the two subtrees of any node differ by at most one.

Graph

31. What is a graph?
    • A collection of nodes (vertices) and edges connecting them.
32. What is a directed graph?
    • A graph where edges have a direction.
33. What is an undirected graph?
    • A graph where edges do not have a direction.
34. How do you represent a graph using an adjacency matrix?
    • Use a 2D array where matrix[i][j] is true if there is an edge from node i to node j.
35. How do you represent a graph using an adjacency list?
    • Use an array of lists where each list contains the neighbors of a node.
36. How do you perform Depth-First Search (DFS) on a graph?
    • Use a stack or recursion to explore as far down one branch as possible before backtracking.
37. How do you perform Breadth-First Search (BFS) on a graph?
    • Use a queue to explore all neighbors of a node before moving to the next level.
38. How do you detect a cycle in a graph?
    • Use DFS and track visited nodes; if a node is visited twice in the current path, there is a cycle.
39. What is a topological sort?
    • A linear ordering of vertices in a directed acyclic graph such that for every directed edge u -> v, u comes before v.
40. How do you find the shortest path in an unweighted graph?
    • Use BFS starting from the source node.

Sorting

41. What is Bubble Sort?
    • A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.
42. What is Selection Sort?
    • A sorting algorithm that divides the input list into two parts: the sublist of items already sorted, and the sublist of items remaining to be sorted.
43. What is Insertion Sort?
    • A sorting algorithm that builds the final sorted array one item at a time by repeatedly picking the next item and inserting it into the sorted portion.
44. What is Merge Sort?
    • A divide-and-conquer algorithm that divides the list into halves, recursively sorts each half, and merges the sorted halves.
45. What is Quick Sort?
    • A divide-and-conquer algorithm that picks a pivot element, partitions the array around the pivot, and recursively sorts the subarrays.
46. What is Heap Sort?
    • A comparison-based sorting technique based on a binary heap data structure.
47. What is Radix Sort?
    • A non-comparative sorting algorithm that sorts integers by processing individual digits.
48. How do you measure the efficiency of a sorting algorithm?
    • Using time complexity (best, average, and worst-case) and space complexity.
49. What is the time complexity of Quick Sort?
    • O(n log n) on average, O(n^2) in the worst case.
50. What is the time complexity of Merge Sort?
    • O(n log n) in all cases.

Searching

51. What is Linear Search?
    • A simple search algorithm that checks every element in the list until the target is found or the list ends.
52. What is Binary Search?
    • A search algorithm that finds the position of a target value within a sorted array by repeatedly dividing the search interval in half.
53. How do you implement Binary Search?
    • Check the middle element; if it is the target, return its index. If it is less than the target, search the right half. Otherwise, search the left half.
54. What is the time complexity of Linear Search?
    • O(n).
55. What is the time complexity of Binary Search?
    • O(log n).

Hashing

56. What is hashing?
    • A technique to convert a range of key values into a range of indexes of an array.
57. What is a hash table?
    • A data structure that implements an associative array abstract data type, a structure that can map keys to values.
58. How do you handle collisions in a hash table?
    • Using techniques like chaining (linked lists) or open addressing (linear probing, quadratic probing, double hashing).
59. What is a hash function?
    • A function that converts an input (or ‘key’) into a fixed-size string of bytes, typically a hash code.
60. What are the properties of a good hash function?
    • It should distribute keys uniformly across the hash table and minimize collisions.

Dynamic Programming

61. What is dynamic programming?
    • A method for solving complex problems by breaking them down into simpler subproblems and storing the results of subproblems to avoid redundant computations.
62. What is memoization?
    • An optimization technique used to store the results of expensive function calls and reuse them when the same inputs occur again.
63. What is the difference between memoization and tabulation?
    • Memoization is top-down (recursion), and tabulation is bottom-up (iterative).
64. How do you solve the Fibonacci sequence using dynamic programming?
    • Use either memoization or tabulation to store previously computed values.
65. What is the time complexity of the dynamic programming solution to the Fibonacci sequence?
    • O(n).
66. How do you solve the Knapsack problem using dynamic programming?
    • Use a table to store the maximum value that can be obtained with a given weight limit.
67. What is the Longest Common Subsequence problem?
    • A problem of finding the longest subsequence common to two sequences.
68. How do you solve the Longest Common Subsequence problem using dynamic programming?
    • Use a 2D array to store the lengths of the longest common subsequences of the prefixes of the input sequences.
69. What is the time complexity of the Longest Common Subsequence problem using dynamic programming?
    • O(m*n), where m and n are the lengths of the input sequences.
70. What is the Coin Change problem?
    • A problem to find the minimum number of coins that make up a given amount.
71. How do you solve the Coin Change problem using dynamic programming?
    • Use a table to store the minimum number of coins needed for each amount from 0 to the target amount.
72. What is the time complexity of the Coin Change problem using dynamic programming?
    • O(n*k), where n is the target amount and k is the number of coin denominations.

String

73. What is the Knuth-Morris-Pratt (KMP) algorithm?
    • A string-matching algorithm that uses a prefix function to avoid redundant comparisons.
74. What is the Rabin-Karp algorithm?
    • A string-matching algorithm that uses hashing to find any one of a set of pattern strings in a text.
75. What is the time complexity of the KMP algorithm?
    • O(n + m), where n is the length of the text and m is the length of the pattern.
76. What is the time complexity of the Rabin-Karp algorithm?
    • O(n*m) in the worst case, O(n + m) on average.
77. How do you reverse a string?
    • Swap characters from the beginning and end moving towards the center.
78. How do you check if a string is a palindrome?
    • Compare characters from the beginning and end moving towards the center.
79. How do you find the first non-repeating character in a string?
    • Use a hash map to count character occurrences, then iterate through the string.
80. How do you find all permutations of a string?
    • Use backtracking to generate all possible arrangements of the characters.

Miscellaneous

81. What is a trie?
    • A tree-like data structure used to store a dynamic set or associative array where the keys are usually strings.
82. How do you insert a word into a trie?
    • Traverse the trie and insert characters of the word at each level.
83. How do you search for a word in a trie?
    • Traverse the trie according to the characters of the word.
84. What is a segment tree?
    • A tree data structure used for storing intervals or segments and allowing querying which of the stored segments contain a given point.
85. What is a Fenwick tree (Binary Indexed Tree)?
    • A data structure that provides efficient methods for calculation and manipulation of the prefix sums of a table of values.
86. What is a disjoint-set (union-find) data structure?
    • A data structure that keeps track of a partition of a set into disjoint (non-overlapping) subsets.
87. How do you implement union by rank and path compression in a disjoint-set?
    • Union by rank attaches the smaller tree under the root of the larger tree. Path compression flattens the structure of the tree whenever Find is called.
88. What is a Bloom filter?
    • A space-efficient probabilistic data structure used to test whether an element is a member of a set.
89. How do you handle collisions in a Bloom filter?
    • Bloom filters do not handle collisions directly; they may give false positives.
90. What is a heap?
    • A special tree-based data structure that satisfies the heap property (min-heap or max-heap).
91. How do you implement a min-heap?
    • Use an array where each parent node is less than or equal to its child nodes.
92. How do you insert an element into a heap?
    • Add the element at the end and bubble it up to maintain the heap property.
93. How do you delete the minimum element from a min-heap?
    • Replace the root with the last element, remove the last element, and bubble down the new root to maintain the heap property.
94. What is a priority queue?
    • A type of queue where each element is associated with a priority, and elements are served according to their priority.
95. How do you implement a priority queue using a heap?
    • Use a heap to maintain the order of elements based on priority.
96. What is the difference between a stack and a queue?
    • Stack follows LIFO, while queue follows FIFO.
97. What is the difference between an array and a linked list?
    • An array has fixed size and allows random access, while a linked list has dynamic size and allows efficient insertions/deletions.
98. How do you find the intersection of two arrays?
    • Use a hash set to store elements of one array and check for each element of the other array in the set.
99. What is a Deque (Double-ended queue)?
    • A data structure that allows insertions and deletions from both ends.
100. How do you implement a Deque using arrays? – Use a circular array with two indices to track the front and rear of the deque.

This comprehensive list covers a wide range of topics and should provide a strong foundation for DSA interviews.