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 a rod of size `n > 1`, it can be cut into any number of pieces `k`. The price for each piece of size `i` is represented as `price(i)` and the maximum revenue from a rod of size `i` is `r(i)` (could be split into multiple pieces). Find `r(n)` for the rod of size `n`.**

Consider that the length of the rod is `6`.
The price of size is given below:

<table>
<tr>
<th>
<b>Length
</th>
<td>
1
</td>
<td>
2
</td>
<td>
3
</td>
<td>
4
</td>
<td>
5
</td>
<td>
6
</td>
</tr>
<tr>
<th>
<b>Price(p)
</th>
<td>
2
</td>
<td>
5
</td>
<td>
8
</td>
<td>
9
</td>
<td>
10
</td>
<td>
11
</td>
</table>

The possible number of rods after cutting can give the following price:

<table>
<tr>
<th>
<b>Rod(6)
</th>
<td>
1*6
</td>
<td>
1*4, 2
</td>
<td>
1*3, 3
</td>
<td>
1, 2, 3
</td>
<td>
1*2, 4
</td>
<td>
1, 5
</td>

<td>
2*3
</td>

<td>
2, 4
</td>

<td>
3, 3
</td>
</tr>
<tr>
<th>
<b>Price(p)
</th>
<td>
12
</td>
<td>
13
</td>
<td>
14
</td>
<td>
15
</td>
<td>
13
</td>
<td>
12
</td>
<td>
15
</td>
<td>
13
</td>
<td>
16
</td>

</table>

So the maximum revenue is `16` for the rod that can be cut in `(3,3)`, i.e., `2` pieces.

# Solution: **Recursive Approach**
Here we have to generate all the configurations of different pieces and find the highest priced configuration. We can get the best price (*maximum revenue*) by making a cut at different positions and comparing the values obtained after a cut.

If `RodCut(n)` is the function that gives the value of `r(n)`, then
`RodCut(n) = max(p(i) + RodCut(i))`.

Let's move to the implementation now. In this lesson, we will build a solution using the recursive approach, and then in the next lesson, we will implement a more optimized approach to solve this problem.



Build a recursive solution for a commonly asked coding interview problem.

Overview

Number Theory

Number Theory

Divide and Conquer

Greedy Algorithms

Greedy Algorithms

Recursion and Backtracking

Recursion and Backtracking

Dynamic Programming

Graphs

Bonus Lessons

Rod Cutting Problem

Problem statement

Rod(6)	1*6	1*4, 2	1*3, 3	1, 2, 3	1*2, 4	1, 5	2*3	2, 4	3, 3
Price(p)	12

Length	1	2	3	4	5	6
Price(p)	2	5	8	9	10	11