✅ Top DSA Interview Questions with Answers: Part-3 🧠

21. What is the Sliding Window technique?
It’s an optimization method used to reduce time complexity in problems involving arrays or strings. You create a "window" over a subset of data and slide it as needed, updating results on the go.
Example use case: Find the maximum sum of any k consecutive elements in an array.

22. Explain the Two-Pointer technique.
This involves using two indices (pointers) to traverse a data structure, usually from opposite ends or the same direction. It's helpful for searching pairs or reversing sequences efficiently.
Common problems: Two-sum, palindrome check, sorted array partitioning.

23. What is the Binary Search algorithm?
It’s an efficient algorithm to find an element in a sorted array by repeatedly dividing the search range in half.
Time Complexity: O(log n)
Key idea: Compare the target with the middle element and eliminate half the array each step.

24. What is the Merge Sort algorithm?
A divide-and-conquer sorting algorithm that splits the array into halves, sorts them recursively, and then merges them.
Time Complexity: O(n log n)
Stable? Yes
Extra space? Yes, due to merging.

25. What is the Quick Sort algorithm?
It chooses a pivot, partitions the array so elements < pivot are left, and > pivot are right, then recursively sorts both sides.
Time Complexity: Avg – O(n log n), Worst – O(n²)
Fast in practice, but not stable.

26. Difference between Merge Sort and Quick Sort
• Merge Sort is stable, consistent in performance (O(n log n)), but uses extra space.
• Quick Sort is faster in practice and works in-place, but may degrade to O(n²) if pivot is poorly chosen.

27. What is Insertion Sort and how does it work?
It builds the sorted list one item at a time by comparing and inserting items into their correct position.
Time Complexity: O(n²)
Best Case (nearly sorted): O(n)
Stable? Yes
Space: O(1)

28. What is Selection Sort?
It finds the smallest element from the unsorted part and swaps it with the beginning.
Time Complexity: O(n²)
Space: O(1)
Stable? No
Rarely used due to inefficiency.

29. What is Bubble Sort and its drawbacks?
It repeatedly compares and swaps adjacent elements if out of order.
Time Complexity: O(n²)
Space: O(1)
Drawback: Extremely slow for large data. Educational, not practical.

30. What is the time and space complexity of common sorting algorithms?
• Bubble Sort → Time: O(n²), Space: O(1), Stable: Yes
• Selection Sort → Time: O(n²), Space: O(1), Stable: No
• Insertion Sort → Time: O(n²), Space: O(1), Stable: Yes
• Merge Sort → Time: O(n log n), Space: O(n), Stable: Yes
• Quick Sort → Avg Time: O(n log n), Worst: O(n²), Space: O(log n), Stable: No

Double Tap ♥️ For Part-4