100 questions and answers related to Algorithms (Computer Science)

1. What is an algorithm?

   • An algorithm is a step-by-step procedure or set of rules to solve a specific problem or perform a task.

2. What are the characteristics of a good algorithm?

   • Correctness, efficiency, finiteness, definiteness, input, and output.

3. What is the difference between an algorithm and a program?

   • An algorithm is a conceptual procedure, while a program is an implementation of an algorithm using a programming language.

4. What are the types of algorithms?

   • Sorting, searching, graph, dynamic programming, greedy, and divide & conquer algorithms.

5. What is algorithm complexity?

   • It is a measure of the performance of an algorithm in terms of time (time complexity) and space (space complexity).

6. What is time complexity?

   • It describes how the running time of an algorithm increases with the input size.

7. What is space complexity?

   • It describes the amount of memory an algorithm uses as a function of input size.

8. What is an asymptotic notation?

   • A notation used to describe the complexity of an algorithm (Big O, Big Theta, Big Omega).

9. What is Big-O notation?

   • It represents the worst-case complexity of an algorithm.

10. What is the best-case and worst-case complexity?

• Best-case: the minimum time an algorithm takes.
• Worst-case: the maximum time an algorithm takes.

11-20: Searching Algorithms

11. What is a searching algorithm?

    • An algorithm used to find an element in a data structure.

12. What is linear search?

    • A simple searching algorithm that checks each element one by one.

13. What is the time complexity of linear search?

    • O(n) in the worst and average cases.

14. What is binary search?

    • A searching algorithm that works on sorted arrays by dividing the search space into halves.

15. What is the time complexity of binary search?

    • O(log n) in the worst case.

16. What is the main difference between linear search and binary search?

    • Linear search works on both sorted and unsorted arrays, while binary search only works on sorted arrays.

17. What is interpolation search?

    • A search algorithm that estimates the position of a target value based on the distribution of data.

18. What is the time complexity of interpolation search?

    • O(log log n) in the best case, but O(n) in the worst case.

19. Which searching algorithm is best for a small dataset?

    • Linear search is efficient for small datasets.

20. Which searching algorithm is best for large sorted datasets?

    • Binary search is efficient for large sorted datasets.

21-30: Sorting Algorithms

21. What is a sorting algorithm?

    • An algorithm that arranges elements in a specific order (ascending or descending).

22. What is Bubble Sort?

    • A simple sorting algorithm that repeatedly swaps adjacent elements if they are in the wrong order.

23. What is the time complexity of Bubble Sort?

    • O(n²) in the worst and average cases.

24. What is Selection Sort?

    • A sorting algorithm that selects the smallest element and places it in its correct position.

25. What is the time complexity of Selection Sort?

    • O(n²) in all cases.

26. What is Insertion Sort?

    • A sorting algorithm that builds the sorted list one element at a time by inserting elements into their correct positions.

27. What is the time complexity of Insertion Sort?

    • O(n²) in the worst case and O(n) in the best case.

28. What is Merge Sort?

    • A divide & conquer sorting algorithm that splits the array into halves and merges them in sorted order.

29. What is the time complexity of Merge Sort?

    • O(n log n) in all cases.

30. What is Quick Sort?

    • A sorting algorithm that selects a pivot and partitions the array around it.

31-40: Graph Algorithms

31. What is a graph?

    • A data structure consisting of vertices (nodes) and edges (connections).

32. What is BFS (Breadth-First Search)?

    • A traversal algorithm that explores all nodes level by level.

33. What is DFS (Depth-First Search)?

    • A traversal algorithm that explores as far as possible along a branch before backtracking.

34. What is Dijkstra’s Algorithm used for?

    • Finding the shortest path between nodes in a weighted graph.

35. What is the time complexity of Dijkstra’s Algorithm?

    • O(V²) using an adjacency matrix and O((V + E) log V) using a priority queue.

36. What is the Bellman-Ford Algorithm?

    • A shortest path algorithm that works with negative weights.

37. What is Prim’s Algorithm?

    • An algorithm used to find the Minimum Spanning Tree (MST).

38. What is Kruskal’s Algorithm?

    • An algorithm that finds the MST by sorting edges and adding them one by one.

39. What is Floyd-Warshall Algorithm?

    • An algorithm used to find the shortest paths between all pairs of vertices.

40. What is Topological Sorting?

    • A linear ordering of vertices in a Directed Acyclic Graph (DAG).

41-50: Divide & Conquer Algorithms

41. What is the Divide & Conquer approach?

    • A technique that breaks a problem into smaller subproblems, solves them, and combines solutions.

42. Which sorting algorithms use Divide & Conquer?

    • Merge Sort and Quick Sort.

43. What is the time complexity of Quick Sort?

    • O(n log n) on average and O(n²) in the worst case.

44. What is the best case for Quick Sort?

    • When the pivot divides the array into nearly equal parts.

45. What is the recurrence relation for Merge Sort?

    • T(n) = 2T(n/2) + O(n)

46. What is Karatsuba Algorithm used for?

    • Fast multiplication of large numbers.

47. What is Strassen’s Algorithm?

    • An algorithm for fast matrix multiplication.

48. What is the time complexity of Strassen’s Algorithm?

    • O(n².81)

49. Why is Merge Sort stable but Quick Sort is not?

    • Merge Sort maintains the relative order of equal elements, while Quick Sort does not always.

50. What is the best-case time complexity of Merge Sort?

    • O(n log n)

51-60: Greedy Algorithms

51. What is a greedy algorithm?

    • A greedy algorithm makes the locally optimal choice at each step in the hope of finding a global optimum.

52. What is an example of a greedy algorithm?

    • Huffman coding, Kruskal’s algorithm, Prim’s algorithm, and Dijkstra’s algorithm.

53. What is the time complexity of Kruskal’s algorithm?

    • O(E log E), where E is the number of edges.

54. Why does Prim’s algorithm work well with dense graphs?

    • It efficiently selects the minimum-weight edge, and dense graphs have many edges.

55. What is the main difference between Prim’s and Kruskal’s algorithm?

    • Prim’s grows the MST from one node, while Kruskal’s sorts and adds edges.

56. What is Huffman coding used for?

    • Lossless data compression.

57. What is the time complexity of Huffman coding?

    • O(n log n)

58. Is the greedy approach always optimal?

    • No, it only works for problems with the greedy-choice property and optimal substructure.

59. What is an activity selection problem?

    • A problem where activities must be scheduled using the least amount of time.

60. What is the time complexity of the activity selection problem?

    • O(n log n) if sorting is required.

61-70: Dynamic Programming

61. What is dynamic programming (DP)?

    • A technique that solves problems by breaking them into overlapping subproblems and storing solutions.

62. What are the two types of DP approaches?

    • Top-down (memoization) and bottom-up (tabulation).

63. What is memoization?

    • A technique to store already computed results to avoid redundant calculations.

64. What is tabulation?

    • A bottom-up approach that fills a table to find the solution iteratively.

65. What is the time complexity of Fibonacci sequence using DP?

    • O(n)

66. What is the knapsack problem?

    • A problem where items must be selected to maximize value without exceeding weight capacity.

67. What is the time complexity of the 0/1 knapsack problem using DP?

    • O(nW), where n is the number of items and W is the capacity.

68. What is the longest common subsequence (LCS) problem?

    • Finding the longest sequence that appears in the same order in two strings.

69. What is the time complexity of the LCS problem?

    • O(mn), where m and n are the string lengths.

70. What is the traveling salesman problem (TSP)?

    • A problem where a salesman must visit all cities with minimum cost and return to the start.

71-80: Backtracking Algorithms

71. What is backtracking?

    • A recursive technique for solving constraint-based problems by exploring possible solutions and backtracking when needed.

72. What is an example of backtracking?

    • N-Queens problem, Sudoku solver, and Hamiltonian cycle.

73. What is the time complexity of the N-Queens problem?

    • O(N!), where N is the number of queens.

74. What is the subset sum problem?

    • A problem that checks whether a subset exists with a given sum.

75. What is the time complexity of the subset sum problem using backtracking?

    • O(2ⁿ) in the worst case.

76. How is backtracking different from recursion?

    • Backtracking systematically explores and eliminates possibilities, while recursion does not always involve pruning.

77. What is branch and bound?

    • An optimization technique used in problems like the knapsack and traveling salesman problem.

78. What is pruning in backtracking?

    • A technique to stop exploring paths that cannot lead to a solution.

79. What is the difference between backtracking and dynamic programming?

    • Backtracking explores all solutions, while DP stores results to avoid recomputation.

80. What is the Hamiltonian cycle problem?

    • Finding a cycle in a graph that visits every vertex exactly once.

81-90: Advanced Algorithm Concepts

81. What is NP-completeness?

    • A classification of problems that are hard to solve but easy to verify.

82. What is P vs NP problem?

    • The question of whether every problem whose solution can be verified quickly (NP) can also be solved quickly (P).

83. What is an approximation algorithm?

    • An algorithm that finds near-optimal solutions for NP-hard problems.

84. What is an example of an approximation algorithm?

    • The greedy approach to the traveling salesman problem.

85. What is the time complexity of matrix chain multiplication using DP?

    • O(n³)

86. What is the Ford-Fulkerson algorithm used for?

    • Finding the maximum flow in a flow network.

87. What is the time complexity of the Ford-Fulkerson algorithm?

    • O(E * max_flow)

88. What is Tarjan’s algorithm?

    • An algorithm to find strongly connected components in a graph.

89. What is the time complexity of Tarjan’s algorithm?

    • O(V + E)

90. What is the Rabin-Karp algorithm used for?

    • String pattern matching using a rolling hash function.

91-100: Miscellaneous Algorithm Questions

91. What is Boyer-Moore algorithm used for?

    • String searching with a preprocessing step to skip characters.

92. What is KMP (Knuth-Morris-Pratt) algorithm?

    • A string matching algorithm that preprocesses patterns to avoid redundant comparisons.

93. What is the time complexity of KMP?

    • O(n + m), where n is the text length and m is the pattern length.

94. What is AVL tree?

    • A self-balancing binary search tree where heights of subtrees differ by at most 1.

95. What is a trie?

    • A tree-based data structure used for storing strings efficiently.

96. What is heap sort?

    • A sorting algorithm that uses a binary heap structure.

97. What is the time complexity of heap sort?

    • O(n log n) in all cases.

98. What is A algorithm?*

    • A pathfinding algorithm used in AI and game development.

99. What is the time complexity of A search?*

    • O(E) in the worst case.

100. What is the difference between Floyd-Warshall and Dijkstra’s algorithm?
     - Floyd-Warshall finds shortest paths between all pairs of nodes, while Dijkstra finds the shortest path from a single source.