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
You are given two strings `str1` and `str2`. The operations listed below can be performed on `str1`. Find the min number of edits (operations) required to convert `str1` to `str2`.
1. Insert
2. Remove 
3. Replace

All the above operations are of equal cost.

Let us look at the following two examples: 
* We have two strings, **str1 = cat** and **str2 = cut**. To convert **cat** to **cut**, we just need to replace **a** with **u** and the minimum number of edits is **1**.
* We have two strings, **str1 = sunday** and **str2 = saturday**. The last **3** characters are the same, and we only need to replace **un** with **atur**. We need to replace **n** with **r** and insert **a** and **t** before **u**. The minimum number of edits is **3**.
# Solution: **Recursive approach**
Let's discuss the approach used in this solution.

* If the last characters of the two strings are the same, there is nothing much to do. Ignore the last characters and get the count for the remaining strings. Thus, we recur for lengths **m-1** and **n-1**.
* Else (if the last characters are not the same), we consider all operations on `str1`, consider all three operations on the last character of the first string, recursively compute the minimum cost for all three operations, and take a minimum of three values. 
   * **Insert**: Recur for `m` and `n-1`
   * **Remove**: Recur for `m-1` and `n`
   * **Replace**: Recur for `m-1` and `n-1`

Once the approach is clear, we can write some pseudocode that will also help us understand the recurrence relation.
* If str1[m] = str2[n]
   * **editDist(str1, str2, m, n) = editDist(str1, str2, m-1, n-1)**
* Else
   * **editDist(str1, str2, m, n) = 1 + min{editDist(str1, str2, m-1, n)** (*Remove operation*)
   * **editDist(str1, str2, m, n-1)** (*Insert operation*)
    * **editDist(str1, str2, m-1, n-1)** (*Replace operation*)

Instead of writing a recursive solution, we will write an iterative one because of overlapping subproblem. You can take an exercise to write a recursive solution. It would be very easy as we already discussed the pseudocode for the recursive approach above. Let's move to the implementation now.

Solve an interesting example taken from the SPOJ online contest based on strings and dynamic programming.

Overview

Number Theory

Number Theory

Divide and Conquer

Greedy Algorithms

Greedy Algorithms

Recursion and Backtracking

Recursion and Backtracking

Dynamic Programming

Graphs

Bonus Lessons

Edit Distance Problem

Problem statement