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.

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

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