Top 6 Divide & Conquer Interview Questions And Answers

Question 1

Explain how Merge Sort works

Accepted Answer

**Merge sort** is a _divide-and-conquer_, _comparison-based_ sorting algorithm based on the idea of breaking down a list into several sub-lists until each sublist consists of a single element and merging those sublists in a manner that results into a sorted list. Most implementations produce a _stable_ sort, which means that the order of equal elements is the same in the input and output. Can be used as _external_ sorting (when the data to be sorted is too large to fit into memory).
![](https://cdn.journaldev.com/wp-content/uploads/2019/07/MergeSort.png) There are two methods for implementing a Merge Sort algorithm: * The **Top-Down (recursive)** approach. Given an array of size N, the algorithm recursively breaks the array in half and then merges the results together. * The **Bottom-Up (iterative)** approach. Rather than breaking the overall array into distinct pieces, bottum-up mergesort loops over the array using intervals of varying sizes. Each interval is sorted and merged together; subsequent loops over the array have larger intervals, effectively merging our previously sorted (smaller) intervals together.

Question 2

What is the difference between Divide and Conquer and Dynamic Programming Algorithms?

Accepted Answer

**Dynamic programming** is an extension of **Divide and Conquer** paradigm.

* They both work by recursively breaking down a problem into two or more sub-problems. The solutions to the sub-problems are then combined to give a solution to the original problem.
* In Divide and conquer the sub-problems are _independent_ of each other. Mergesort is a classic example of divide and conquer. The main difference between this example and the Fibonacci example is that in a mergesort, the division can (theoretically) be arbitrary, and no matter how you slice it up, you are still merging and sorting.
* In dynamic programming the sub-problem are not independent. So to calculate new Fib number you have to know two previous values. For Merge sort you don't need to know the sorting order of previously sorted sub-array to sort another one.
* Dynamic programming approach may be applied to the problem only if the problem has certain restrictions or prerequisites:
 * **Optimal substructure** — optimal solution can be constructed from optimal solutions of its subproblems
 * **Overlapping sub-problems** — problem can be broken down into subproblems which are _reused several times_ or a recursive algorithm for the problem solves the same subproblem over and over rather than always generating new subproblems.
* Dynamic programming approach extends divide and conquer approach with two techniques:
  * memoization (top-down cache filling)
 *  tabulation (bottom-up cache filling)

![](https://cdn-images-1.medium.com/max/2000/1*BwuDAdImyK_nZpb-H8h3SA.jpeg)

Question 3

Convert a Binary Tree to a Doubly Linked List

Accepted Answer

This can be achieved by traversing the tree in the **in-order** manner that is, left the `child -> root ->right` node.

![](https://www.techiedelight.com/wp-content/uploads/Inorder-Traversal.png)

In an in\-order traversal, first the left sub\-tree is traversed, then the root is visited, and finally the right sub\-tree is traversed.

One simple way of solving this problem is to start with an empty doubly linked list. While doing the in-order traversal of the binary tree, keep inserting each element output into the doubly linked list. But, if we look at the question carefully, the interviewer wants us to convert the binary tree to a doubly linked list **in-place** i.e. we should not create new nodes for the doubly linked list.

This problem can be solved recursively using a divide and conquer approach. Below is the algorithm specified.
*   Start with the root node and solve left and right sub\-trees recursively
*   At each step, once left and right sub\-trees have been processed:
    *   fuse output of left subtree with root to make the intermediate result
    *   fuse intermediate result (built in the previous step) with output from the right sub\-tree to make the final result of the current recursive call

Question 4

Explain how _QuickSort_ works

Accepted Answer

**Quick Sort** is a _divide and conquer_, _comparison_, _in-place_ algorithm. Efficient implementations of Quicksort are **not a stable** sort. When implemented well, it can be about two or three times faster than its main competitors, merge sort and heapsort.

**Quicksort** determines something called a **pivot**, which is a somewhat _arbitrary_ element in the collection. Using the pivot point, quicksort _partitions_ (or _divides_) the larger unsorted collection into two, smaller lists. It moves all the elements smaller than the pivot to the left (before) the pivot element, and moves all the elements larger than the pivot to the right (after) the pivot element. Even though the list isn’t completely sorted yet, we know that the items are in the correct order in relation to the pivot. This means that we never have to compare elements on the left side of the partition to elements on the right side of the partition. We already know they are in their correct spots in relation to the pivot. The sub-lists are then sorted _recursively_.

![](https://res.cloudinary.com/practicaldev/image/fetch/s--wwfJBPCm--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://dev-to-uploads.s3.amazonaws.com/i/3odpn7gl8myiqx7rto4f.png)

Ideally, partitioning would use the _median_ of the given values (in the array), but the median can only be found by scanning the whole array and this would slow the algorithm down. In that case the two partitions would be of equal size; In the simplest versions of quick sort an arbitrary element, typically the _last (rightmost) element_ is used as an estimate (guess) of the median.

Question 5

Explain what is _Fibonacci Search_ technique?

Accepted Answer

**Fibonacci search** is a search algorithm based on **divide and conquer** principle that can find an element in the given **sorted array** with the help of Fibonacci series in O(log n) time complexity. Compared to binary search where the sorted array is divided into two equal-sized parts, one of which is examined further, Fibonacci search divides the array into two _unequal parts_ that have sizes that are _consecutive Fibonacci numbers_. Some facts to note: * Fibonacci search has the advantage that one only needs addition and subtraction to calculate the indices of the accessed array elements, while classical binary search needs bit-shift, division or multiplication, operations that were less common at the time Fibonacci search was first published * Binary search works by dividing the seek area in equal parts `1:1`. Fibonacci search can divide it into parts approaching `1:1.618` while using the simpler operations. * On average, Fibonacci search requires 4% more comparisons than binary search * Fibonacci Search examines relatively closer elements in subsequent steps. So when input array is big that cannot fit in CPU cache or even in RAM, Fibonacci Search can be useful. Thus Fibonacci search may have the advantage over binary search in slightly reducing the average time needed to access a non-uniform access memory storage. Let the length of given array be `length` and the element to be searched be `key`. Steps of Fibonacci Search: 1. Find the smallest Fibonacci number `F(n)` that `F(n) - 1 >= length` 2. `F(n) = F(n-1) + F(n-2)` => `F(n) - 1 = [ F(n-1) - 1 ] + (1) + [ F(n-2) - 1 ]`, where `(1)` here is for the middle item (the **m** in below figure). ``` // |<--------- p: F(n) - 1 --------->| // |<--- q: F(n-1) - 1 --->| |<-- r: F(n-2) - 1 -->| // +----+---+--------------------+---+---+---+---+ // | | k | | m | | k | | // +----+---+--------------------+---+---+---+---+ // ^ ``` 3. If `key < m`, then search key in `q` = `F(n-1) - 1`: ```sh // |<--- p: F(n-1) - 1 --->| // |<----- q ----->| |<-- r -->| // +----+---+------+---+---------+ // | | k | | m | | // +----+---+------+---+---------+ ``` for that set `p = F(n-1) - 1, q = F(n-2) - 1, r = F(n-3) - 1` and repeat the process. Here Fibonacci numbers go _backward_ **once**. These indicate elimination of approximately one-third of the remaining array. 4. If `key > m`, then repeat then search key in `r = F(n-2) - 1`: ```sh // |<-- p: F(n-2) - 1 -->| // |<--- q --->| |<- r ->| // +---+---+---+ // | | k | | m // +---+---+---+ // ^ ``` For that, set `p = F(n-2) - 1, q = F(n-3) - 1, r = F(n-4) - 1` and repeat the process. Here Fibonacci numbers go _backward_ **twice**, indicating elimination of approximately two-third of the remaining array.

Question 6

Compare Greedy vs Divide & Conquer vs Dynamic Programming Algorithms

Accepted Answer

Consider:

|Greedy|Divide & Conquer|Dynamic Programming|
|--- |--- |--- |
|Optimises by making the best choice at the moment|Optimises by breaking down a subproblem into simpler versions of itself and using multi-threading & recursion to solve|Same as Divide and Conquer, but optimises by caching the answers to each subproblem as not to repeat the calculation twice.|
|Doesn't always find the optimal solution, but is very fast|Always finds the optimal solution, but is slower than Greedy|Always finds the optimal solution, but could be pointless on small datasets.|
|Requires almost no memory|Requires some memory to remember recursive calls|Requires a lot of memory for memoisation / tabulation|

Top 6 Divide & Conquer Interview Questions

What is the difference between Divide and Conquer and Dynamic Programming Algorithms?

Compare Greedy vs Divide & Conquer vs Dynamic Programming Algorithms

Explain how Merge Sort works

Convert a Binary Tree to a Doubly Linked List

Explain how QuickSort works

Explain what is Fibonacci Search technique?