50 divide and conquer interview questions [easy, medium, hard]

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 linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list 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:

  1. Easy divide and conquer interview questions
  2. Medium divide and conquer interview questions
  3. Hard divide and conquer interview questions
  4. 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
Question 2: Majority element
Question 3: First bad version
Question 4: Binary search
Question 5: Search insert position
Question 6: Arranging coins
Question 7: Valid perfect square
Question 8: Sqrt(x)
Question 9: Find smallest letter greater than target

2. Medium divide and conquer interview questions

Here are some moderate-level 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 
Question 11: Search a 2D matrix II
Question 12: Longest substring with at least K repeating characters
Question 13: Construct binary tree from preorder and postorder traversal
Question 14: Convert sorted list to binary search tree
Question 15: Sort list
Question 16: Maximum sum circular subarray
Question 17: Sort an array
Question 18: K closest points to origin
Question 19: Balance a binary search tree
Question 20: Beautiful array
Question 21: Find peak element
Question 22: Find first and last position of element in sorted array
Question 23: Find peak element II
Question 24: Heaters
Question 25: Find right interval
Question 26: H-index II
Question 27: Random pick with weight
Question 28: Find K closest elements
Question 29: Single element in a sorted array
Question 30: Time based key-value store
Question 31: Snapshot array
Question 32: Koko eating bananas
Question 33: Capacity to ship packages within D days
Question 34: Sum of mutated array closest to target
Question 35: Find the smallest divisor given a threshold

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
Question 37: Reverse pairs
Question 38: Count of smaller numbers after self
Question 39: Count of range sum
Question 40: Merge K sorted lists
Question 41: The skyline problem
Question 42: Create sorted array through instructions
Question 43: Number of ways to reorder array to get same BST
Question 44: Max sum of rectangle no larger than K
Question 45: Split array largest sum
Question 46: Find minimum in rotated sorted array II
Question 47: Longest duplicate substring
Question 48: Kth smallest number in multiplication table
Question 49: Find K-th smallest pair distance
Question 50: Minimum space wasted from packaging

4. How to prepare for a coding interview

4.1 Refresh your knowledge

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. Check out our guides for detailed explanations and useful cheat sheets.

Algorithms explained:

Data structure guides:

4.2 Practice on your own

Once you’re confident in all of these, you’ll want to start working through lots of coding problems.

For divide and conquer you can obviously use the questions we’ve listed above. For the other algorithms you need to know, check out the rest of this series:

We also recommend working through our list of 73 data structure interview questions.

One of the main challenges of coding interviews is that you have to communicate what you are doing as you are doing it. Talking through your solution out loud is therefore very helpful. This may sound strange to do on your own, but it will significantly improve the way you communicate your answers during an interview.

It's also a good idea to work on a piece of paper or google doc, given that in the real interview you'll have to code on a whiteboard or virtual equivalent.

4.3 Practice with others

Of course, if you can practice with someone else playing the role of the interviewer, that's really helpful. But 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 ex-interviewers 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 1-on-1 with ex-interviewers from leading tech companies. Learn more and start scheduling sessions today.

cta_illustration arrow_left Browse FAANG ex-interviewers

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!