Divide and Conquer: Interview Questions and Practice Problems

Divide and conquer (D&C) is an algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more subproblems of the same or related type until these become simple enough to be solved directly. The solutions to the subproblems are then combined to give a solution to the original problem.

Merge Sort Algorithm using Divide & Conquer

In this post, we have listed out commonly asked interview questions that can be solved with the Divide and conquer technique:

1. Merge Sort Algorithm
2. Iterative Merge Sort Algorithm (Bottom-up Merge Sort)
3. Quicksort Algorithm
4. Hybrid QuickSort Algorithm
5. Quicksort using Dutch National Flag Algorithm
6. Quicksort algorithm using Hoare’s partitioning scheme
7. Inversion count of an array
8. Segregate positive and negative integers using merge sort
9. Iterative Implementation of Quicksort
10. Binary Search Algorithm
11. Find the number of rotations in a circularly sorted array
12. Search an element in a circularly sorted array
13. Find the first or last occurrence of a given number in a sorted array
14. Count occurrences of a number in a sorted array with duplicates
15. Find the smallest missing element from a sorted array
16. Find floor and ceil of a number in a sorted integer array
17. Search in a nearly sorted array in logarithmic time
18. Find the number of 1’s in a sorted binary array
19. Find the peak element in an array
20. Maximum Subarray Sum using Divide and Conquer
21. Efficiently implement power function
22. Find the missing term in a sequence in logarithmic time
23. Find floor and ceil of a number in a sorted array (Recursive solution)
24. Find the frequency of each element in a sorted array containing duplicates
25. Find the square root of a number using a binary search
26. Division of two numbers using binary search algorithm
27. Find the odd occurring element in an array in logarithmic time
28. Find pairs with difference `k` in an array | Constant Space Solution
29. Find `k` closest elements to a given value in an array
30. Find the minimum and maximum element in an array using Divide and Conquer
31. Longest Common Prefix (LCP) Problem
32. Binary Search in C++ STL and Java Collections
33. Ternary Search vs Binary search
34. Exponential search
35. Unbounded Binary Search
36. Interpolation search
37. Introsort Algorithm — Overview and C++ Implementation
38. Efficiently merge `k` sorted linked lists
39. Merge sort algorithm for a singly linked list
40. Sort a doubly-linked list using merge sort
41. Find the square of a number without using the multiplication and division operator

Thanks for reading.