To ace your coding interview for a software engineering job, you’ll need to understand divide and conquer. It is a problem solving approach that divides a problem into smaller subproblems that are easier to solve, then combines the subproblem solutions into the solution for the original problem. Divide and conquer comes up frequently in coding interviews and is fundamental to many other algorithms such as binary search and mergesort.
Let’s take a look at some typical divide and conquer questions.
5 typical divide and conquer interview questions

You are given an array of k linkedlists lists, each linkedlist is sorted in ascending order. Merge all the linkedlists into one sorted linkedlist and return it.

Write an efficient algorithm that searches for a target value in an m x n integer matrix.

Given the head of a linked list, return the list after sorting it in ascending order.

Given an integer array nums and an integer k, return the kth largest element in the array.

Given an integer array nums, return the number of reverse pairs in the array. A reverse pair is a pair (i, j) where 0 <= i < j < nums.length and nums[i] > 2 * nums[j]
Below, we take a look at 50 divide and conquer questions and provide you with links to high quality solutions to them.
This is an overview of what we’ll cover:

Easy divide and conquer interview questions
 Medium divide and conquer interview questions
 Hard divide and conquer interview questions
 Divide and conquer basics
 Divide and conquer cheat sheet
 How to prepare for a coding interview
Let's get started.
1. Easy divide and conquer interview questions
You might be tempted to try to read all of the possible questions and memorize the solutions, but this is not feasible. Interviewers will always try to find new questions, or ones that are not available online. Instead, you should use these questions to practice the fundamental concepts of divide and conquer.
As you consider each question, try to replicate the conditions you’ll encounter in your interview. Begin by writing your own solution without external resources in a fixed amount of time.
If you get stuck, go ahead and look at the solution, but then try the next one alone again. Don’t get stuck in a loop of reading as many solutions as possible! We’ve analysed dozens of questions and selected ones that are commonly asked and have clear and high quality answers.
Here are some of the easiest questions you might get asked in a coding interview. These questions are often asked during the “phone screen” stage, so you should be comfortable answering them without being able to write code or use a whiteboard.
Question 1: Maximum subarray
 Text guide (Techie Delight)
 Video guide (Ghassan Shobaki)
 Code example (jianchaoli)
Question 2: Majority element
 Text guide (enjoy algorithms)
 Video guide (Nideesh Terapalli)
 Code example (coderoath)
Question 3: First bad version
 Text guide (Studytonight)
 Video guide (TECH DOSE)
 Video guide (Kevin Naughton Jr.)
 Code example (RainbowSecret)
Question 4: Binary search
 Text guide (Medium/Arpit)
 Video guide (Nick White)
 Code example (AminiCK)
Question 5: Search insert position
 Text guide (Medium/Sam)
 Video guide (NeetCode)
 Video guide (TECH DOSE)
 Code example (algorithmatic)
Question 6: Arranging coins
 Text guide (just4once)
 Video guide (Timothy H Chang)
 Code example (AlexanderTarn)
Question 7: Valid perfect square
 Text guide (Dev.to/Aroup)
 Video guide (TECH DOSE)
 Video guide (Terrible Whiteboard)
 Code example (LeetCode)
Question 8: Sqrt(x)
 Text guide (Medium/Len Chen)
 Video guide (Nideesh Terapalli)
 Video guide (Terrible Whiteboard)
 Code example (AlexTheGreat)
Question 9: Find smallest letter greater than target
 Text guide (tutorialspoint)
 Video guide (Eric Programming)
 Code example (LeetCode)
2. Medium divide and conquer interview questions
Here are some moderatelevel questions that are often asked in a video call or onsite interview. You should be prepared to write code or sketch out the solutions on a whiteboard if asked.
Question 10: Kth largest element in an array
 Text guide (Coder’s Cat)
 Video guide (NeetCode)
 Code example (jmnarloch)
Question 11: Search a 2D matrix II
 Text guide (Medium/Nerd for tech)
 Video guide (Back to Back SWE)
 Code example (LeetCode)
Question 12: Longest substring with at least K repeating characters
 Text guide (Medium/dume0011)
 Video guide (Knowledge Center)
 Code example (cdpiano)
Question 13: Construct binary tree from preorder and postorder traversal
 Text guide (Techie Delight)
 Video guide (Jenny’s lectures)
 Code example (GraceMeng)
Question 14: Convert sorted list to binary search tree
 Text guide (Dev.to/seanpgallivan)
 Video guide (Nick White)
 Code example (JosephTao)
Question 15: Sort list
 Text guide (LeetCode)
 Video guide (NeetCode)
 Code example (jeantimex)
Question 16: Maximum sum circular subarray
 Text guide (Techie Delight)
 Video guide (TECHDOSE)
 Code example (logan138)
Question 17: Sort an array
 Text guide (hezhigang)
 Video guide (leetuition)
 Code example (RohanPark)
Question 18: K closest points to origin
 Text guide (Learnbay)
 Video guide (Deepti Talesra)
 Code example (Frimish)
Question 19: Balance a binary search tree
 Video guide (Nideesh Terapalli)
 Video guide (Lead Coding by FRAZ)
 Code example (richamishra)
Question 20: Beautiful array
 Text guide (Tutorialspoint)
 Video guide (Coding Decoded)
 Code example (lee215)
Question 21: Find peak element
 Text guide (Techie Delight)
 Video guide (Kevin Naughton Jr.)
 Code example (gangan)
Question 22: Find first and last position of element in sorted array
 Text guide (Dev.to/seanpgallivan)
 Video guide (NeetCode)
 Video guide (Errichto)
 Code example (StefanPochmann)
Question 23: Find peak element II
 Text guide (walkccc)
 Video guide (Java Coding Insight)
 Code example (000Prime)
Question 24: Heaters
 Text guide (just4once)
 Video guide (happygirlzt)
 Code example (shawngao)
Question 25: Find right interval
 Text guide (just4once)
 Video guide (Knowledge Center)
 Code example (suman_buie)
Question 26: Hindex II
 Text guide (shareablecode)
 Video guide (TECH DOSE)
 Code example (LeJas)
Question 27: Random pick with weight
 Text guide (just4once)
 Video guide (TECH DOSE)
 Code example (LATTES)
Question 28: Find K closest elements
 Text guide (Techie Delight)
 Video guide (Coders Camp)
 Code example (lee215)
Question 29: Single element in a sorted array
 Text guide (Dev.to/Subramanya)
 Video guide (take U forward)
 Code example (zaynesiew)
Question 30: Time based keyvalue store
 Text guide (Tutorialspoint)
 Video guide (NeetCode)
 Video guide (Michael Muinos)
 Code example (yidong_w)
Question 31: Snapshot array
 Text guide (sarthasehgal)
 Video guide (happygirlzt)
 Code example (lee215)
Question 32: Koko eating bananas
 Text guide (TutorialCup)
 Video guide (NeetCode)
 Video guide (Michael Muinos)
 Code example (GraceMeng)
Question 33: Capacity to ship packages within D days
 Text guide (csharpcorner)
 Video guide (code Explainer)
 Code example (lee215)
Question 34: Sum of mutated array closest to target
 Text guide (walkccc)
 Video guide (Sai Anish Malla)
 Video guide (babybear4812)
 Code example (lee215)
Question 35: Find the smallest divisor given a threshold
 Text guide (Dev.to/codingpineapple)
 Video guide (Naresh Gupta)
 Code example (lee215)
3. Hard divide and conquer interview questions
Similar to the medium section, these more difficult questions may be asked in an onsite or video call interview. You will likely be given more time if you are expected to create a full solution.
Question 36: Median of two sorted arrays
 Text guide (Medium/hamid)
 Video guide (NeetCode)
 Code example (MissMary)
Question 37: Reverse pairs
 Text guide (Tutorialhorizon)
 Video guide (take U forward)
 Code example (fun4LeetCode)
Question 38: Count of smaller numbers after self
 Text guide (Programmerall)
 Video guide (happygirlzt)
 Code example (confiscate)
Question 39: Count of range sum
 Text guide (Medium/dume0011)
 Video guide (happygirlzt)
 Code example (dietpepsi)
Question 40: Merge K sorted lists
 Text guide (Techie Delight)
 Video guide (NeetCode)
 Code example (zxyperfect)
Question 41: The skyline problem
 Text guide (Brian Gordon)
 Video guide (Tushar Roy)
 Video guide (mCoding)
 Code example (Medium/Dimka Maleev)
Question 42: Create sorted array through instructions
 Text guide (Dev.to/Ruairi)
 Video guide (Lead Coding by FRAZ)
 Code example (DBabichev)
Question 43: Number of ways to reorder array to get same BST
 Text guide (walkccc)
 Video guide (Abrar Sher)
 Code example (AincradLyu)
Question 44: Max sum of rectangle no larger than K
 Text guide (Programcreek)
 Video guide (Coding Decoded)
 Code example (javachao)
Question 45: Split array largest sum
 Text guide (just4once)
 Text guide (Medium/Nitish Chandra)
 Video guide (happygirlzt)
 Code example (dax1ng)
Question 46: Find minimum in rotated sorted array II
 Text guide (GeeksForGeeks)
 Video guide (Knowledge Center)
 Code example (sheehan)
Question 47: Longest duplicate substring
 Text guide (Medium/Anshika Bhargava)
 Video guide (TECH DOSE)
 Code example (DBabichev)
Question 48: Kth smallest number in multiplication table
 Text guide (Tutorialspoint)
 Video guide (Coders Camp)
 Video guide (Coding Decoded)
 Code example (zaynesiew)
Question 49: Find Kth smallest pair distance
 Text guide (just4once)
 Video guide (code Explainer)
 Code example (shawngao)
Question 50: Minimum space wasted from packaging
 Text guide (walkccc)
 Video guide (Sandip Jana)
 Code example (lee215)
4. Divide and conquer basics
In order to crack questions about divide and conquer, you’ll need to have a strong understanding of the algorithm, how it works, and when to use it.
4.1 What is divide and conquer?
Divide and conquer (DAC) is an algorithmic paradigm used to solve problems by continually dividing the problem into smaller parts until a part is easy enough to solve (conquer) on its own. The solutions to the solved parts are then combined to give the solution for the original problem. For optimization problems, being able to build an optimal solution based on the optimal solution of smaller parts is known as an optimal substructure.
Let’s solve an accumulation count problem using DAC. Suppose we are given the following list of musical notes and need to establish how many times each note appears in the list.
The simplest solution is to use a serial approach to build a frequency table while looping over the list. The DAC approach instead divides the list into two recursively until only one note is left in each sublist, and then returns the frequency table for the one note only, illustrated by the conquer layer in the diagram.
In the next step, the onenote tables are combined in the reverse of the divide action, then those combined tables are combined again, and so it continues until one big table is formed with the note count for the entire list. Combining two tables means adding them together, so combining the A1;D1 table to the A1;E1 table gives us the A2;E1;D1 table.
The benefit this offers over the serial solution is that the subproblems can be solved in parallel. In summary, a DAC algorithm will consist of the following steps:
 Divide – the problem is divided into two or more smaller subproblems in a serial fashion using recursion.
 Conquer – each subproblem is solved serially or in parallel.
 Combine – the solutions of the subproblems are combined in a serial fashion.
4.1.1 Use cases for divide and conquer
Most problems and operations using lists can be solved using DAC, but some problems not related to lists can also be solved using DAC:
 Sorting – both Mergesort and Quicksort are DAC implementations
 Finding the maximum and/or smallest element in a list
 Strassen’s matrix multiplication algorithm
 Karatsuba’s multiplication algorithm
 CooleyTukey’s fast Fourier transform algorithm
 Solving the nth Fibonacci number
 Finding the closest pair of points in a matrix
4.1.2 Example implementation
Since DACs are recursive functions, they require at least one base condition which is followed by the divide, conquer, and combine steps. For our frequency count problem, this results in the following implementation:
The base condition stops the recursion when the array only has one note, and will return the frequency table for this single note. Next, the algorithm divides the list into two sublists, and conquers each sublist separately. The results of the two sublists are finally combined into one table which is returned.
4.1.3 How divide and conquer compares to other algorithms
Decreaseandconquer algorithms are similar to DACs in that they also reduce problems into smaller subproblems that are easier to solve. However, decreaseandconquer algorithms will only focus on one of the subproblems and discard the others. A classic example is binary searching, which divides a list into two but will only continue searching in one of the two sublists. A DAC on the other hand always conquers two or more subproblems.
Dynamic programming can also be applied to problems with optimal substructures when they have overlapping subproblems. An example of this is finding the nth Fibonacci number, which is a problem that has an optimal substructure (because it requires finding the n1 and n2 Fibonacci number) and has overlapping subproblems (since finding n1 will again find n2). Here, dynamic programming will solve the problem in polynomial time while DAC will take exponential time.
Greedy algorithms can be applied to problems with optimal substructure that also have the greedy property. The greedy property guarantees the optimal solution of subproblems will result in the optimal solution of the global problem. Few problems have this property and proving a solution makes use of it is tricky, but when a greedy algorithm can be used, the average run time can be better.
MapReduce is a programming paradigm that is an example of DAC. First data is mapped or divided into components, and then reduced or "conquered" to the desired solution. Hadoop is a framework that implements the MapReduce paradigm and allows for massive parallelism on big data.
5. Divide and conquer cheat sheet
You can download the cheat sheet here.
5.1 Related algorithms and techniques
5.2 Cheat sheet explained
The cheat sheet above is a summary of information you might need to know for an interview, but it’s usually not enough to simply memorize it. Instead, aim to understand each result so that you can give the answer in context.
The cheat sheet is broken into time complexity and space complexity (the processing time and memory requirements for divide and conquer). Divide and conquer is related to several data structures, which are also included in the cheat sheet.
For more information about time and space requirements of different algorithms, read our complete guide to bigO notation and complexity analysis.
5.2.1 Time complexity
In our frequency problem, the list is divided in two for a total of log_2(n) + 1 divide and combine iterations. Each combine operation only loops over half the elements (n/2) at each iteration to give a total time complexity of O(n log_2(n)). The serial solution is better at linear time, but cannot run in parallel like the DAC solution does. Not all problems solved with a DAC algorithm have a serial solution too, however.
In the general case, a DAC algorithm will take more than linear time but less than exponential time, like brute forcing. Mergesort and Quicksort illustrate this: Mergesort worstcase time complexity is O(n log(n)) and Quicksort O(n^2), but both have an averagecase time complexity of O(n log(n)).
5.2.2 Space complexity
The only extra space used by our divideandconquer algorithm is the frequency table. In the worst case, each element only appears once, and the table will need an entry for every element, giving a space complexity of O(n). The serial solution would use the same table to keep track of the frequency of notes.
In general, the space complexity is not the same for all DAC algorithms. For example, the space complexity of Mergesort is O(n), while that of Quicksort is O(log n).
5.2.3 Related algorithms and data structures: maps and lists
Almost any data structure is used across the various DAC implementations to problems. For our notefrequency problem we used a map, which offers constant insertion and updating times. Mergesort uses a list, but only adds to the end of the list when merging, to achieve constant time insertions. Quicksort does not use any extra data structures but moves items on the list it is operating on, with each move having a time complexity of O(n) in the worst case.
6. How to prepare for a coding interview
6.1 Practice on your own
Before you start practicing interviews, you’ll want to make sure you have a strong understanding of not only divide and conquer but also the rest of the relevant algorithms and data structures. You’ll also want to start working through lots of coding problems.
Check out the guides below for lists of questions organized by difficulty level, links to highquality answers, and cheat sheets.
Algorithm guides
 Depthfirst search
 Breadthfirst search
 Binary search
 Sorting
 Dynamic programming
 Greedy algorithm
 Backtracking
Data structure guides
To get used to an interview situation, where you’ll have to code on a whiteboard, we recommend solving the problems in the guides above on a piece of paper or google doc.
6.2 Practice with others
However, sooner or later you’re probably going to want some expert interventions and feedback to really improve your coding interview skills.
That’s why we recommend practicing with exinterviewers from top tech companies. If you know a software engineer who has experience running interviews at a big tech company, then that's fantastic. But for most of us, it's tough to find the right connections to make this happen. And it might also be difficult to practice multiple hours with that person unless you know them really well.
Here's the good news. We've already made the connections for you. We’ve created a coaching service where you can practice 1on1 with exinterviewers from leading tech companies. Learn more and start scheduling sessions today.
Any questions about divide and conquer interview questions?
If you have any questions about divide and conquer or coding interviews in general, don't hesitate to ask them in the comments below. All questions are good questions, so go ahead!