The ultimate guide to coding interviews. Developed by FAANG engineers. Boost problem-solving skills with number theory, dynamic programming, and graph theory. Get interview-ready in just a few hours.

Competitive Programming - Crack Your Coding Interview.png

Whether you’re gearing up for online coding challenges, code-a-thons, or interviews, then this course is for you. With this course, you will solidify your problem-solving skills ensuring a swift sail through any problem. 


You will be tasked with solving some of the most frequently asked questions that are brought up in FAANG interviews. You will start with the concepts of Number Theory and Divide and Conquer, and gradually move towards more complex problems like dynamic programming and graph theory.


With each problem you solve, there will be insightful explanations and full implementation details to really hammer home the concepts. By the time you finish this course, you will have the confidence to solve any problem, no matter the difficulty.

Competitive Programming - Crack Your Coding Interview, C++

# Problem statement
The problem is the same as in the [Bubble Sort](https://www.educative.io/courses/competitive-programming-intvw/bubble-sort) lesson. We are given an input array of numbers and we need to sort them. The only difference will be in the time complexity, which we will discuss later.

# Solution
Suppose we had to sort an array **A**. A subproblem would be to sort a subsection of this array starting at index **p** and ending at index **r**, denoted as **A[p..r]**.

* ***Divide*** — If **q** is the half-way point between **p** and **r**, we can split the subarray **A[p..r]** into two arrays **A[p..q]** and **A[q+1, r]**.

* ***Conquer*** — In the conquer step, we try to sort both the subarrays **A[p..q]** and **A[q+1, r]**. If we haven't yet reached the base case, we again divide both these subarrays and try to sort them.

* ***Combine*** — When the conquer step reaches the base step and we get two sorted subarrays **A[p..q]** and **A[q+1, r]** for array **A[p..r]**, we combine the results by creating a sorted array **A[p..r]** from two sorted subarrays **A[p..q]** and **A[q+1, r]**.

Let us visualize this to understand these operations better.

Now that the technique is clear, let's move on to the implementation and then see the time complexity of this sorting technique.

#include <iostream>
using namespace std;

void Merge(int *a, int s, int e){
    int mid=(s+e)/2;
    int i=s;
    int j = mid + 1;
    int k = s;
    int temp[100];

    while(i<=mid && j<=e){
        if(a[i]<a[j]){
            temp[k++] = a[i++];
        }
        else{
            temp[k++] = a[j++];
        }
    }
    while(i<=mid){
        temp[k++] = a[i++];
    }
    while(j<=e){
        temp[k++] = a[j++];
    }

    for(int i=s;i<=e; i++){
        a[i] = temp[i];
    }
}

void MergeSort(int a[],int s, int e){
    if(s>=e){
        return;
    }
    int mid=(s+e)/2;
    MergeSort(a,s,mid);
    MergeSort(a,mid+1,e);
    Merge(a,s,e);
}

int main() {

    int arr[] = {1,9,4,6,13,74,56,32,41,7,5};
    MergeSort(arr,0,9);
    for(int i=0; i<10; i++)
        cout<<arr[i]<<" ";
    return 0;
}


**Explanation:**
* On line 4, we define our `Merge()` function, which will perform the merging after the array is subdivided into single elements.
* From lines 11 to 18, we run a loop to copy the elements in a `temp` array till the condition is satisfied.
* On line 19, there might be chances that we could have the value of `j` becoming greater than the value of `e` while there are still some elements left that are smaller in the sub-array. We need to copy this to our `temp` array.
* On line 22, again, we could have a case like the value of `i` crossed the value of `mid` while there are still some elements left in the sub-array. We need to copy those in the `temp` array.
* On line 26, we run a loop to merge the results in a sorted manner. We just copy our `temp` array to the original array `arr`.
* On line 31, we define our `MergeSort()` function.
* On line 32, we check for the base case.
* On lines 36 and 37, we call the function recursively on the left and right sub-arrays (dividing the array).
* On line 38, we finally call the `Merge()` function to merge the arrays back to a single array in a sorted manner (We have seen this in the visualization).
* Finally in the `main()` function, we just define our array and call the `MergeSort()` function, and then print the sorted array.
> We passed the array by reference.

Merge Sort is a recursive algorithm and the time complexity can be expressed as the following recurrence relation. 

${T(n)}$ = ${2T}$(${\frac{n}{2}}$) + ${\theta}$${(n)}$

The above recurrence can be solved either using the Recurrence Tree method or the Master method. The solution of the recurrence is ${\theta}$${(nLogn)}$. The time complexity of Merge Sort is  ${O(nLogn)}$ in all 3 cases (worst, average, and best) because merge sort always divides the array into two halves and takes linear time to merge two halves.

Overview

Number Theory

Number Theory

Divide and Conquer

Greedy Algorithms

Greedy Algorithms

Recursion and Backtracking

Recursion and Backtracking

Dynamic Programming

Graphs

Bonus Lessons

Merge Sort

Problem statement

Solution