Advice > Software engineering

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

By Gareth Dwyer on December 17, 2021 How we wrote this article
divide and conquer interview questions

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. Divide and conquer basics
  5. Divide and conquer cheat sheet
  6. How to prepare for a coding interview

Let's get started.

Click here to practice coding interviews with ex-FAANG interviewers

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. 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.

divide and conquer accumulation count problem

divide and conquer solution

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 one-note 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 sub-problems can be solved in parallel. In summary, a DAC algorithm will consist of the following steps:

  1. Divide – the problem is divided into two or more smaller sub-problems in a serial fashion using recursion.
  2. Conquer – each sub-problem is solved serially or in parallel.
  3. Combine – the solutions of the sub-problems 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
  • Cooley-Tukey’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

Decrease-and-conquer algorithms are similar to DACs in that they also reduce problems into smaller sub-problems that are easier to solve. However, decrease-and-conquer algorithms will only focus on one of the sub-problems 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 sub-problems.

Dynamic programming can also be applied to problems with optimal substructures when they have overlapping sub-problems. An example of this is finding the nth Fibonacci number, which is a problem that has an optimal substructure (because it requires finding the n-1 and n-2 Fibonacci number) and has overlapping sub-problems (since finding n-1 will again find n-2). 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 sub-problems 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.

Need a boost in your career as a software engineer?

If you want to improve your skills as an engineer or leader, tackle an issue at work, get promoted, or understand the next steps to take in your career, book a session with one of our software engineering coaches.

5. Divide and conquer cheat sheet

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 big-O 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 worst-case time complexity is O(n log(n)) and Quicksort O(n^2), but both have an average-case time complexity of O(n log(n)).

5.2.2 Space complexity

The only extra space used by our divide-and-conquer 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 note-frequency 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 high-quality answers, and cheat sheets.

Algorithm guides

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 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.

 

Related articles:

System design interview prep
Software engineeringJul 11, 2023
System design interview prep (6 steps to an offer at FAANG)
Complete guide to system design interview prep. Learn what to expect, and practice with questions from Facebook, Google, Amazon, etc.
Read more
Hand holding phone displaying Google Maps route
Software engineeringNov 14, 2022
Google system design interview guide (questions, process, prep)
Everything you need to know about Google system design interviews, including the process, 45 sample questions, example answers, and an answer framework.
Read more
The google logo in neon
Software engineeringOct 10, 2023
6 Google resume examples (+ tips on optimizing for Google)
6 real examples of resumes that worked for Google. Plus, all the info you need to optimize your resume/CV for Google, including tips, a checklist and a step-by-step guide.
Read more
tree interview questions and answers
Software engineeringSep 17, 2021
50+ tree questions and solutions (easy, medium, hard)
50+ tree interview questions, all with links to high-quality solutions, plus a tree refresher and cheat sheet. Part 5 of our coding prep series to help you ace your software engineer interview.
Read more
coding interview prep
Software engineeringOct 10, 2023
Coding Interview Prep (7 steps to an offer at FAANG)
Coding interview prep made simpler: follow these seven steps and land an offer at Google, Meta, Amazon, etc. Know what to expect, learn an answer method, refresh your data structure and algorithm knowledge, and see lists of practice coding questions.
Read more
Sorting interview questions
Software engineeringNov 19, 2021
54 sorting interview questions [easy, medium, hard]
54 sorting interview questions, all with links to high-quality solutions, plus an interview preparation guide. Part 4 of our algorithms questions series to help you practice for your software engineer interview.
Read more
sharding system design interview
Software engineeringFeb 14, 2023
Sharding: system design interview concepts (7 of 9)
This guide defines sharding, how it works, and when you should use it in a system. This is the 7th of 9 foundational system design interview concepts that we're covering on our blog.
Read more
LinkedIn software engineer interview
Software engineeringSep 17, 2020
LinkedIn software engineer interview (questions and process)
This is a complete guide to LinkedIn software engineer (SWE) interviews. It covers LinkedIn's interview process, practice questions, and preparation tips.
Read more