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
**For each item, you are given its weight and its value. You want to maximize the total value of all the
items you are going to put in the knapsack such that the total weight of the items is less than the knapsack’s
capacity. What is this maximum total value?**

The only condition is to consider all subsets of items. There can be two cases for every item: 
1. The item is included in the
optimal subset.
2. The item is not included in the optimal set.

Therefore, the maximum value that can be obtained from `n` items is the maximum of the following two values:
1. Maximum value obtained by `n - 1` items and `W` weight (excluding ${n^{th}}$ item)
2. Value of ${n^{th}}$ item plus maximum value obtained by `n - 1` items and `W` minus weight of the ${n^{th}}$ item (*including ${n^{th}}$ item*). If the weight of the ${n^{th}}$ item is greater than `W`, the ${n^{th}}$ item cannot be included and case 1 is the only possibility.

Let’s look at the recurrence relation:
* **Base case**: If we have explored all the items or if we have reached the maximum capacity of Knapsack,
   ```
   if (n=0 or W=0)
       return 0
   ```
* If the weight of the ${n^{th}}$ item is greater than the capacity of the knapsack, we cannot include this item:
   ```
   if (weight[n] > W)
      return solve(n-1, W)
   ```
* Otherwise, we can,
   ```
   return max{solve(n-1, W), solve(n-1, W-weight[n])}
   ```   
   Here, the expression `solve(n - 1, W)` means that we have not included the item and the expression `solve(n - 1, W - weight[n])` means that we have included that item in the knapsack.

If we build the recursion tree for the above relation, we can see that the property of overlapping sub-problems is satisfied. So, let’s try to solve it using dynamic programming.


Use dynamic programming to implement the solution of a problem.

Overview

Number Theory

Number Theory

Divide and Conquer

Greedy Algorithms

Greedy Algorithms

Recursion and Backtracking

Recursion and Backtracking

Dynamic Programming

Graphs

Bonus Lessons

0 - 1 Knapsack Problem

Problem statement