Divide and Conquer: Interview Questions and Practice Problems
Published in
2 min readDec 18, 2018
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:
- Merge Sort Algorithm
- Iterative Merge Sort Algorithm (Bottom-up Merge Sort)
- Quicksort Algorithm
- Hybrid QuickSort Algorithm
- Quicksort using Dutch National Flag Algorithm
- Quicksort algorithm using Hoare’s partitioning scheme
- Inversion count of an array
- Segregate positive and negative integers using merge sort
- Iterative Implementation of Quicksort
- Binary Search Algorithm
- Find the number of rotations in a circularly sorted array
- Search an element in a circularly sorted array
- Find the first or last occurrence of a given number in a sorted array
- Count occurrences of a number in a sorted array with duplicates
- Find the smallest missing element from a sorted array
- Find floor and ceil of a number in a sorted integer array
- Search in a nearly sorted array in logarithmic time
- Find the number of 1’s in a sorted binary array
- Find the peak element in an array
- Maximum Subarray Sum using Divide and Conquer
- Efficiently implement power function
- Find the missing term in a sequence in logarithmic time
- Find floor and ceil of a number in a sorted array (Recursive solution)
- Find the frequency of each element in a sorted array containing duplicates
- Find the square root of a number using a binary search
- Division of two numbers using binary search algorithm
- Find the odd occurring element in an array in logarithmic time
- Find pairs with difference `k` in an array | Constant Space Solution
- Find `k` closest elements to a given value in an array
- Find the minimum and maximum element in an array using Divide and Conquer
- Longest Common Prefix (LCP) Problem
- Binary Search in C++ STL and Java Collections
- Ternary Search vs Binary search
- Exponential search
- Unbounded Binary Search
- Interpolation search
- Introsort Algorithm — Overview and C++ Implementation
- Efficiently merge `k` sorted linked lists
- Merge sort algorithm for a singly linked list
- Sort a doubly-linked list using merge sort
- Find the square of a number without using the multiplication and division operator
Thanks for reading.