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 arrays of numbers that denote the endpoints of bridges. What is the maximum number of bridges that can be built if ${i^{th}}$ point of the first array must be connected to ${i^{th}}$ point of the second array and two bridges cannot overlap each other?**

# Solution: **Longest Increasing Subsequence approach**

In this problem, we will use the concept of LIS. Two bridges will not overlap with each other if both their endpoints are either in non-increasing or non-decreasing order. To find the solution, we will first pair the endpoints, i.e., ${i^{th}}$ point in the ${1^{st}}$ sequence is paired with ${i^{th}}$ point in the ${2^{nd}}$ sequence. Then, we sort the points with respect to the ${1^{st}}$ point in
the pair and apply LIS on the second point of the pair.

Let us take the following example: 

Consider the pairs **(2,6), (5, 4), (8, 1), (10, 2)**. Sort them according to the first element of the pairs (in this case, they are already sorted) and compute the LIS on the second element of the pairs (**6, 4, 1, 2**) that is **1, 2**. Therefore the non-overlapping bridges we are looking for are **(8, 1)** and **(10, 2)**.

Let us now move to the implementation of this solution.

Solve a real interview problem based on the concept of Longest Increasing Subsequence.

Overview

Number Theory

Number Theory

Divide and Conquer

Greedy Algorithms

Greedy Algorithms

Recursion and Backtracking

Recursion and Backtracking

Dynamic Programming

Graphs

Bonus Lessons

Building Bridges Problem - Solution Using LIS

Problem statement