Most 100 Data Structure and Algorithm Interview Quetion and Answer For Fresher | DSA

A list of 100 data structure and algorithm interview questions with answers |

1. What is a data structure?

• Answer: A data structure is a way of organizing and storing data in a computer so that it can be accessed and modified efficiently.

1. What is an algorithm?

• Answer: An algorithm is a step-by-step procedure or formula for solving a problem, typically in terms of input data and desired output.

1. What is the time complexity of the linear search algorithm?

• Answer: O(n)

1. What is the time complexity of the binary search algorithm?

• Answer: O(log n)

1. Explain the concept of Big O notation.

• Answer: Big O notation is used to describe the upper bound of the time or space complexity of an algorithm in terms of the size of the input.

1. What is a linked list?

• Answer: A linked list is a data structure consisting of a sequence of elements, where each element points to the next element in the sequence.

1. What is the difference between an array and a linked list?

• Answer: An array stores elements in contiguous memory locations, while a linked list stores elements in non-contiguous memory locations and uses pointers to link them together.

1. What is a stack?

• Answer: A stack is a data structure that follows the Last In, First Out (LIFO) principle, where elements are inserted and removed from the same end.

1. What is a queue?

• Answer: A queue is a data structure that follows the First In, First Out (FIFO) principle, where elements are inserted at the rear and removed from the front.

1. What is a tree?
   • Answer: A tree is a hierarchical data structure consisting of nodes connected by edges, where each node has a parent node and zero or more child nodes.
2. What is a binary tree?
   • Answer: A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child.
3. What is a binary search tree (BST)?
   • Answer: A binary search tree is a binary tree in which the value of each node’s left child is less than the value of the node, and the value of each node’s right child is greater than the value of the node.
4. What is a heap?
   • Answer: A heap is a specialized tree-based data structure that satisfies the heap property, where the value of each node is greater than or equal to (or less than or equal to) the values of its children.
5. What is a hash table?
   • Answer: A hash table is a data structure that maps keys to values using a hash function, allowing for efficient retrieval, insertion, and deletion operations.
6. What is a graph?
   • Answer: A graph is a data structure consisting of a set of vertices (nodes) and a set of edges that connect pairs of vertices.
7. What is breadth-first search (BFS)?
   • Answer: Breadth-first search is a graph traversal algorithm that explores all the vertices of a graph at the same level before moving to the next level.
8. What is depth-first search (DFS)?
   • Answer: Depth-first search is a graph traversal algorithm that explores as far as possible along each branch before backtracking.
9. What is dynamic programming?
   • Answer: Dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems and solving each subproblem only once, storing the results for future use.
10. Explain the concept of recursion.
    • Answer: Recursion is a programming technique in which a function calls itself in order to solve smaller instances of the same problem.
11. What is memoization?
    • Answer: Memoization is an optimization technique used in dynamic programming to store the results of expensive function calls and reuse them when the same inputs occur again.
12. What is the time complexity of bubble sort?
    • Answer: O(n^2)
13. What is the time complexity of insertion sort?
    • Answer: O(n^2)
14. What is the time complexity of selection sort?
    • Answer: O(n^2)
15. What is the time complexity of merge sort?
    • Answer: O(n log n)
16. What is the time complexity of quick sort?
    • Answer: O(n log n)
17. What is the time complexity of heap sort?
    • Answer: O(n log n)
18. What is the time complexity of radix sort?
    • Answer: O(nk)
19. What is the time complexity of counting sort?
    • Answer: O(n + k)
20. What is the time complexity of shell sort?
    • Answer: O(n log n) in the worst case
21. What is the time complexity of bucket sort?
    • Answer: O(n + k)
22. What is the time complexity of the Dijkstra’s algorithm?
    • Answer: O((V + E) log V), where V is the number of vertices and E is the number of edges
23. What is the time complexity of the Bellman-Ford algorithm?
    • Answer: O(VE), where V is the number of vertices and E is the number of edges
24. What is the time complexity of the Floyd-Warshall algorithm?
    • Answer: O(V^3), where V is the number of vertices
25. What is the time complexity of the Kruskal’s algorithm?
    • Answer: O(E log E), where E is the number of edges
26. What is the time complexity of the Prim’s algorithm?
    • Answer: O(V^2), with an adjacency matrix representation; O(E log V), with an adjacency list representation
27. What is the time complexity of the A* algorithm?
    • Answer: It depends on the heuristic function used.
28. What is the time complexity of the Boyer-Moore algorithm?
    • Answer: O(n + m), where n is the length of the text and m is the length of the pattern
29. What is the time complexity of the Rabin-Karp algorithm?
    • Answer: O(nm), where n is the length of the text and m is the length of the pattern
30. What is the time complexity of the Knuth-Morris-Pratt algorithm?
    • Answer: O(n + m), where n is the length of the text and m is the length of the pattern
31. What is the time complexity of the Floyd’s cycle detection algorithm?
    • Answer: O(n), where n is the number of elements in the linked list
32. What is the time complexity of the topological sort algorithm?
    • Answer: O(V + E), where V is the number of vertices and E is the number of edges
33. What is the time complexity of the breadth-first search (BFS) algorithm?
    • Answer: O(V + E), where V is the number of vertices and E is the number of edges
34. What is the time complexity of the depth-first search (DFS) algorithm?
    • Answer: O(V + E), where V is the number of vertices and E is the number of edges

44.

What is the time complexity of the Floyd-Warshall algorithm for finding all-pairs shortest paths?
– Answer: O(V^3), where V is the number of vertices

45. What is the time complexity of the Ford-Fulkerson algorithm for finding the maximum flow in a flow network?
    • Answer: O(Ef), where E is the number of edges and f is the maximum flow
46. What is the time complexity of the Edmonds-Karp algorithm for finding the maximum flow in a flow network?
    • Answer: O(VE^2), where V is the number of vertices and E is the number of edges
47. What is the time complexity of the Kosaraju’s algorithm for finding strongly connected components in a directed graph?
    • Answer: O(V + E), where V is the number of vertices and E is the number of edges
48. What is the time complexity of the Tarjan’s algorithm for finding strongly connected components in a directed graph?
    • Answer: O(V + E), where V is the number of vertices and E is the number of edges
49. What is the time complexity of the Hopcroft-Karp algorithm for finding maximum cardinality matching in a bipartite graph?
    • Answer: O(sqrt(V) * E), where V is the number of vertices and E is the number of edges
50. What is the time complexity of the Hungarian algorithm for finding maximum cardinality matching in a bipartite graph?
    • Answer: O(V^3), where V is the number of vertices
51. What is the time complexity of the Viterbi algorithm for finding the most likely sequence of hidden states in a hidden Markov model?
    • Answer: O(T * N^2), where T is the length of the observed sequence and N is the number of hidden states
52. What is the time complexity of the Smith-Waterman algorithm for finding the optimal local alignment of two sequences?
    • Answer: O(m * n), where m and n are the lengths of the sequences
53. What is the time complexity of the Needleman-Wunsch algorithm for finding the optimal global alignment of two sequences?
    • Answer: O(m * n), where m and n are the lengths of the sequences
54. What is the time complexity of the Levenshtein distance algorithm for finding the minimum number of edits required to transform one string into another?
    • Answer: O(m * n), where m and n are the lengths of the strings
55. What is the time complexity of the Longest Common Subsequence (LCS) algorithm for finding the length of the longest common subsequence of two sequences?
    • Answer: O(m * n), where m and n are the lengths of the sequences
56. What is the time complexity of the Longest Increasing Subsequence (LIS) algorithm for finding the length of the longest increasing subsequence of a sequence?
    • Answer: O(n^2) or O(n log n), depending on the implementation
57. What is the time complexity of the Maximum Subarray Sum algorithm for finding the maximum sum of a contiguous subarray of a sequence?
    • Answer: O(n)
58. What is the time complexity of the Knapsack Problem algorithm for finding the maximum value that can be obtained by selecting a subset of items without exceeding a given weight limit?
    • Answer: O(n * W), where n is the number of items and W is the weight limit
59. What is the time complexity of the Traveling Salesman Problem (TSP) algorithm for finding the shortest possible route that visits each city exactly once and returns to the origin city?
    • Answer: O(n^2 * 2^n), where n is the number of cities
60. What is the time complexity of the Subset Sum Problem algorithm for determining whether there exists a subset of a given set whose sum is equal to a given target value?
    • Answer: O(n * sum), where n is the number of elements in the set and sum is the target value
61. What is the time complexity of the Prim’s algorithm for finding the minimum spanning tree of a weighted graph?
    • Answer: O(V^2), with an adjacency matrix representation; O(E log V), with an adjacency list representation
62. What is the time complexity of the Kruskal’s algorithm for finding the minimum spanning tree of a weighted graph?
    • Answer: O(E log E), where E is the number of edges
63. What is the time complexity of the Bellman-Ford algorithm for finding the shortest paths from a single source vertex to all other vertices in a weighted graph with negative edge weights?
    • Answer: O(VE), where V is the number of vertices and E is the number of edges
64. What is the time complexity of the Dijkstra’s algorithm for finding the shortest paths from a single source vertex to all other vertices in a weighted graph with non-negative edge weights?
    • Answer: O((V + E) log V), where V is the number of vertices and E is the number of edges
65. What is the time complexity of the Floyd-Warshall algorithm for finding the shortest paths between all pairs of vertices in a weighted graph?
    • Answer: O(V^3), where V is the number of vertices
66. What is the time complexity of the Ford-Fulkerson algorithm for finding the maximum flow in a flow network?
    • Answer: O(Ef), where E is the number of edges and f is the maximum flow
67. What is the time complexity of the Edmonds-Karp algorithm for finding the maximum flow in a flow network?
    • Answer: O(VE^2), where V is the number of vertices and E is the number of edges
68. What is the time complexity of the Hopcroft-Karp algorithm for finding the maximum cardinality matching in a bipartite graph?
    • Answer: O(sqrt(V) * E), where V is the number of vertices and E is the number of edges
69. What is the time complexity of the Hungarian algorithm for finding the maximum cardinality matching in a bipartite graph?
    • Answer: O(V^3), where V is the number of vertices
70. What is the time complexity of the Viterbi algorithm for finding the most likely sequence of hidden states in a hidden Markov model?
    • Answer: O(T * N^2), where T is the length of the observed sequence and N is the number of hidden states
71. What is the time complexity of the Smith-Waterman algorithm for finding the optimal local alignment of two sequences?
    • Answer: O(m * n), where m and n are the lengths of the sequences
72. What is the time complexity of the Needleman-Wunsch algorithm for finding the optimal global alignment of two sequences?
    • Answer: O(m * n), where m and n are the lengths of the sequences
73. What is the time complexity of the Levenshtein distance algorithm for finding the minimum number of edits required to transform one string into another?
    • Answer: O(m * n), where m and n are the lengths of the strings
74. What is the time complexity of the Longest Common Subsequence (LCS) algorithm for finding the length of the longest common subsequence of two sequences?
    • Answer: O(m * n), where m and n are the lengths of the
    sequences
75. What is the time complexity of the Longest Increasing Subsequence (LIS) algorithm for finding the length of the longest increasing subsequence of a sequence?
    • Answer: O(n^2) or O(n log n), depending on the implementation
76. What is the time complexity of the Maximum Subarray Sum algorithm for finding the maximum sum of a contiguous subarray of a sequence?
    • Answer: O(n)
77. What is the time complexity of the Knapsack Problem algorithm for finding the maximum value that can be obtained by selecting a subset of items without exceeding a given weight limit?
    • Answer: O(n * W), where n is the number of items and W is the weight limit
78. What is the time complexity of the Traveling Salesman Problem (TSP) algorithm for finding the shortest possible route that visits each city exactly once and returns to the origin city?
    • Answer: O(n^2 * 2^n), where n is the number of cities
79. What is the time complexity of the Subset Sum Problem algorithm for determining whether there exists a subset of a given set whose sum is equal to a given target value?
    • Answer: O(n * sum), where n is the number of elements in the set and sum is the target value
80. What is the time complexity of the Longest Palindromic Subsequence (LPS) algorithm for finding the length of the longest palindromic subsequence of a sequence?
    • Answer: O(n^2)
81. What is the time complexity of the Longest Palindromic Substring (LPS) algorithm for finding the length of the longest palindromic substring of a string?
    • Answer: O(n^2)
82. What is the time complexity of the Manacher’s algorithm for finding the length of the longest palindromic substring of a string?
    • Answer: O(n)
83. What is the time complexity of the Counting Sort algorithm for sorting integers in a given range?
    • Answer: O(n + k), where n is the number of elements and k is the range of the input
84. What is the time complexity of the Radix Sort algorithm for sorting integers?
    • Answer: O(nk), where n is the number of elements and k is the number of digits in the maximum number
85. What is the time complexity of the Shell Sort algorithm for sorting integers?
    • Answer: O(n log n) in the worst case
86. What is the time complexity of the Bucket Sort algorithm for sorting floating-point numbers?
    • Answer: O(n + k), where n is the number of elements and k is the number of buckets
87. What is the time complexity of the Topological Sort algorithm for sorting vertices in a directed acyclic graph (DAG)?
    • Answer: O(V + E), where V is the number of vertices and E is the number of edges
88. What is the time complexity of the Breadth-First Search (BFS) algorithm for traversing a graph?
    • Answer: O(V + E), where V is the number of vertices and E is the number of edges
89. What is the time complexity of the Depth-First Search (DFS) algorithm for traversing a graph?
    • Answer: O(V + E), where V is the number of vertices and E is the number of edges
90. What is the time complexity of the Floyd-Warshall algorithm for finding the shortest paths between all pairs of vertices in a weighted graph?
    • Answer: O(V^3), where V is the number of vertices
91. What is the time complexity of the Ford-Fulkerson algorithm for finding the maximum flow in a flow network?
    • Answer: O(Ef), where E is the number of edges and f is the maximum flow
92. What is the time complexity of the Edmonds-Karp algorithm for finding the maximum flow in a flow network?
    • Answer: O(VE^2), where V is the number of vertices and E is the number of edges
93. What is the time complexity of the Hopcroft-Karp algorithm for finding the maximum cardinality matching in a bipartite graph?
    • Answer: O(sqrt(V) * E), where V is the number of vertices and E is the number of edges
94. What is the time complexity of the Hungarian algorithm for finding the maximum cardinality matching in a bipartite graph?
    • Answer: O(V^3), where V is the number of vertices
95. What is the time complexity of the Viterbi algorithm for finding the most likely sequence of hidden states in a hidden Markov model?
    • Answer: O(T * N^2), where T is the length of the observed sequence and N is the number of hidden states
96. What is the time complexity of the Smith-Waterman algorithm for finding the optimal local alignment of two sequences?
    • Answer: O(m * n), where m and n are the lengths of the sequences
97. What is the time complexity of the Needleman-Wunsch algorithm for finding the optimal global alignment of two sequences?
    • Answer: O(m * n), where m and n are the lengths of the sequences
98. What is the time complexity of the Levenshtein distance algorithm for finding the minimum number of edits required to transform one string into another?
    • Answer: O(m * n), where m and n are the lengths of the strings
99. What is the time complexity of the Longest Common Subsequence (LCS) algorithm for finding the length of the longest common subsequence of two sequences?
    • Answer: O(m * n), where m and n are the lengths of the sequences
100. What is the time complexity of the Longest Increasing Subsequence (LIS) algorithm for finding the length of the longest increasing subsequence of a sequence?
     • Answer: O(n^2) or O(n log n), depending on the implementation