3️⃣1️⃣ What is Backtracking?
Backtracking is a recursive technique used to solve problems by trying all possible paths and undoing (backtracking) if a solution fails.
Examples: N-Queens, Sudoku Solver, Subsets, Permutations.
3️⃣2️⃣ Explain the N-Queens Problem.
Place N queens on an N×N chessboard so no two queens attack each other.
Use backtracking to try placing queens row by row, checking column diagonal safety.
3️⃣3️⃣ What is Kadane's Algorithm?
Used to find the maximum subarray sum in an array.
It maintains a running sum and resets it if it becomes negative.
Time Complexity: O(n)
def maxSubArray(arr):
max_sum = curr_sum = arr[0]
for num in arr[1:]:
curr_sum = max(num, curr_sum + num)
max_sum = max(max_sum, curr_sum)
return max_sum
3️⃣4️⃣ What is Floyd’s Cycle Detection Algorithm?
Also called Tortoise and Hare Algorithm.
Used to detect loops in linked lists.
Two pointers move at different speeds; if they meet, there’s a cycle.
3️⃣5️⃣ What is the Union-Find (Disjoint Set) Algorithm?
A data structure that keeps track of disjoint sets.
Used in Kruskal's Algorithm and cycle detection in graphs.
Supports find() and union() operations efficiently with path compression.
3️⃣6️⃣ What is Topological Sorting?
Linear ordering of vertices in a DAG (Directed Acyclic Graph) such that for every directed edge u → v, u comes before v.
Used in: Task scheduling, build systems.
Algorithms: DFS-based or Kahn’s algorithm (BFS).
3️⃣7️⃣ What is Dijkstra’s Algorithm?
Used to find shortest path from a source node to all other nodes in a graph (non-negative weights).
Uses a priority queue (min-heap) to pick the closest node.
Time Complexity: O(V + E log V)
3️⃣8️⃣ What is Bellman-Ford Algorithm?
Also finds shortest paths, but handles negative weights.
Can detect negative cycles.
Time Complexity: O(V × E)
3️⃣9️⃣ What is Kruskal’s Algorithm?
Used to find a Minimum Spanning Tree (MST).
• Sort all edges by weight
• Add edge if it doesn't create a cycle (using Union-Find)
Time Complexity: O(E log E)
4️⃣0️⃣ What is Prim’s Algorithm?
Also finds MST.
• Start from any node
• Add smallest edge connecting tree to an unvisited node
Uses min-heap for efficiency.
Time Complexity: O(E log V)
💬 Double Tap ♥️ For Part-5!