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

**Given two sequences, find the length of the longest subsequence present in both of them.**

A **subsequence** is a sequence that appears in the same relative order but is not necessarily contiguous.
For example, **abc**, **abg**, **bdf**, **aeg**, **acefg...etc.**, are subsequences of **abcdefg**. So a string of length `n` has ${2^{n}}$ different possible subsequences.

# Solution: **Naïve method**

Let **X** be a sequence of length `m` and **Y** be a sequence of length `n`. Check if every subsequence of **X** is a subsequence of **Y**, and return the longest common subsequence found.

There are ${2^{m}}$ subsequences of **X**. To check whether or not the sequences are a subsequence of **Y** takes *O(n)* time. Thus, the naïve algorithm would take *O(n.${2^{m}}$ )* time.

Let us consider an example to understand this problem better.

* LCS for input Sequences **ABCDGH** and **AEDFHR** is **ADH** of length **3**.

* LCS for input Sequences **AGGTAB** and **GXTXAYB** is **GTAB** of length **4**.

The naïve approach discussed above takes exponential time, which is why we need to find a way to optimize the solution.
This problem can be solved using the dynamic programming approach (using Tabulation or Memoization).
# Solution: **Dynamic programming**

Before moving on to implementation, let's first look at the recurrence relation.

* If m = 0 or n = 0, then **LCS(str1, str2, m, n) = 0**. *(Base case)*
* If the last two characters of both strings are the same, i.e., if str1[m] = str2[n], then **LCS(str1, str2, m, n) = 1 + LCS(str1, str2, m-1, n-1)**. 
* Otherwise, **LCS(str1, str2, m, n) = max{LCS(str1, str2, m-1, n), LCS( str1, str2, m, n-1)}**
* LCS can take a value between 0 and `min(m,n)`.

Finally, let's look at how we will calculate the LCS using the slideshow shown below:

Learn to use dynamic programming in string-based problems.

Overview

Number Theory

Number Theory

Divide and Conquer

Greedy Algorithms

Greedy Algorithms

Recursion and Backtracking

Recursion and Backtracking

Dynamic Programming

Graphs

Bonus Lessons

Longest Common Subsequence

Problem statement