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

**Imagine you have a collection of `N` wines placed next to each other on a shelf. For simplicity, let us
number the wines from left to right as they are standing on the shelf with integers from `1 to N`,
respectively. The price of the $i^{th}$ wine is $p_{i}$ (prices of different wines can be different). Because the wines get better every year, supposing today is the year 1, on year `y` the price of the $i^{th}$ wine will be `y*pi`, i.e., y-times the value of that current year.**

**You want to sell all the wines you have, but you want to sell exactly one wine per year, starting this year. One more constraint is that each year you are allowed to sell only either the leftmost or the rightmost wine on the shelf and you are not allowed to reorder the wines on the shelf (i.e., they must stay in the same order as they were in the beginning).**

**You want to find the maximum profit you can get if you sell the wines in optimal order.**

For example, suppose that the prices of the wines are the following (in the order as they are
placed on the shelf, from left to right): 
```
p1 = 1, p2 = 4, p3 = 2, p4 = 3
``` 
The optimal solution would be to sell
the wines in the order *p1, p4, p3, p2* for a total profit *1 * 1 + 3 * 2 + 2 * 3 + 4 * 4 = 29*.

Now let's take a look at why this is not a Greedy problem. If we were assuming this to be a greedy problem, we could sell the cheaper wine from the two (leftmost and rightmost) available wines every year.

Let the prices of 4 wines be: 2, 3, 5, 1, 4.
* At year = 1: {2,3,5,1,4} sell p1 = 2 to get cost = 2
* At year = 2: {3,5,1,4} sell p2 = 3 to get cost = 2 + 2*3 = 8
* At year = 3: {5,1,4} sell p5 = 4 to get cost = 8 + 4*3 = 20
* At year = 4: {5,1} sell p4 = 1 to get cost = 20 + 1*4 = 24
* At year = 5: {5} sell p3 = 5 to get cost = 24 + 5*5 = 49

The Greedy approach gives an optimal answer of `49`, but if we sell in the order of *p1, p5, p4, p2, p3* for a
total profit *2 * 1 + 4 * 2 + 1 * 3 + 3 * 4 + 5 * 5 = 50*, it would mean that the Greedy approach fails.

Think of a possible solution before moving forward.

# Solution: **Recursive approach**
Let us first define the recurrence relation for this problem. 

**answer = max{price[
start] * year + maxPrice(price, start+1, end, year + 1),
price[end] * year + maxPrice(price, start, end - 1,year + 1)}**

Let's see how that works in the code.

For each endpoint at every function call, we 
either take this endpoint in the solution, increment/decrement the endpoint index, or we do not take this endpoint in the solution.

We are doing this for each and every `n` endpoint (`n` is the number of wines on the table).
So, T = O($2^{n}$), which is exponential time complexity.

Let's see the code now.

Build a recursive solution for an interesting problem.

Overview

Number Theory

Number Theory

Divide and Conquer

Greedy Algorithms

Greedy Algorithms

Recursion and Backtracking

Recursion and Backtracking

Dynamic Programming

Graphs

Bonus Lessons

Wine and Maximum Price Problem

Problem statement