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
Let's discuss one more complex problem based on grids. It is another variant of the grid problems that we discussed earlier. The problem statement is given below.
**You are given a 2-D matrix A of `n` rows and `m` columns where `A[i][j]` denotes the calories burnt. Two persons, a boy and a girl start from two corners of this matrix. The boy starts from the cell (1, 1) and needs to reach the cell (n, m). On the other hand, the girl starts from the cell (n, 1) and needs to reach (1, m). The boy can move right and down. The girl can move right and up. As they visit a cell, the amount in the cell `A[i][j]` is added to their total of calories burnt. You have to maximize the sum of total calories burnt by both of them under the condition that they shall meet only in one cell and the cost of this cell shall not be included in either of their totals.**

## Solution: **Dynamic programming approach**
Let us analyze this problem in steps:
* The boy can meet the girl in only one cell. Let's assume they meet at cell `(i, j)`.
* The boy can come in from the left or the top, i.e., `(i, j-1)` or `(i-1, j)`. He can move right or down. The sequence for the boy can be:
  ```
  (i, j-1) —> (i, j) —> (i, j+1)
  (i, j-1) —> (i, j) —> (i+1, 1)
  (i-1, j) —> (i, j) —> (i, j+1)
  (i-1, j) —> (i, j) —> (i+1, j)
  ```
* Similarly, the girl can come in from the left or bottom, i.e., `(i, j-1)` or `(i+1, j)` and she can go up or right. The sequence for the girl’s movement can be:
   ```
   (i, j-1) —> (i, j) —> (i, j+1)
   (i, j-1) —> (i, j) —> (i-1, j)
   (i+1, j) —> (i, j) —> (i, j+1)
   (i+1, j) —> (i, j) —> (i-1, j)
   ```
* Comparing the `4` sequences of the boy and the girl, the boy and girl meet only at one position `(i, j)` if and only if:
   ```
   Boy: (i, j-1) —> (i, j) —>(i, j+1) 
   Girl: (i+1, j) —> (i, j) —>(i-1, j)
   ```
   or
   ```
   Boy: (i-1, j) —> (i, j) —>(i+1, j) 
   Girl: (i, j-1) —> (i, j) —>(i, j+1)
   ```
* Now, we can solve the problem by creating 4 tables:
   * Boy’s journey from `(1, 1)` to meeting cell `(i, j)`.
   * Boy’s journey from meeting cell `(i, j)` to end `(n, m)`.
   * Girl’s journey from start `(n, 1)` to meeting cell `(i, j)`.
   * Girl’s journey from meeting cell `(i, j)` to end `(1, n)`
* The meeting cell can range from `2 <= i <= n - 1` and `2 <= j <= m - 1`.


Let's now move on to the implementation to better understand the logic that we discussed above.

# Problem statement
Let's discuss one more complex problem based on grids. It is another variant of the grid problems that we discussed earlier. The problem statement is given below.
**You are given a 2-D matrix A of `n` rows and `m` columns where `A[i][j]` denotes the calories burnt. Two persons, a boy and a girl start from two corners of this matrix. The boy starts from the cell (1, 1) and needs to reach the cell (n, m). On the other hand, the girl starts from the cell (n, 1) and needs to reach (1, m). The boy can move right and down. The girl can move right and up. As they visit a cell, the amount in the cell `A[i][j]` is added to their total of calories burnt. You have to maximize the sum of total calories burnt by both of them under the condition that they shall meet only in one cell and the cost of this cell shall not be included in either of their totals.**

# Solution: **Dynamic programming approach**
Let us analyze this problem in steps:
* The boy can meet the girl in only one cell. Let's assume they meet at cell `(i, j)`.
* The boy can come in from the left or the top, i.e., `(i, j-1)` or `(i-1, j)`. He can move right or down. The sequence for the boy can be:
  ```
  (i, j-1) —> (i, j) —> (i, j+1)
  (i, j-1) —> (i, j) —> (i+1, 1)
  (i-1, j) —> (i, j) —> (i, j+1)
  (i-1, j) —> (i, j) —> (i+1, j)
  ```
* Similarly, the girl can come in from the left or bottom, i.e., `(i, j-1)` or `(i+1, j)` and she can go up or right. The sequence for the girl’s movement can be:
   ```
   (i, j-1) —> (i, j) —> (i, j+1)
   (i, j-1) —> (i, j) —> (i-1, j)
   (i+1, j) —> (i, j) —> (i, j+1)
   (i+1, j) —> (i, j) —> (i-1, j)
   ```
* Comparing the `4` sequences of the boy and the girl, the boy and girl meet only at one position `(i, j)` if and only if:
   ```
   Boy: (i, j-1) —> (i, j) —>(i, j+1) 
   Girl: (i+1, j) —> (i, j) —>(i-1, j)
   ```
   or
   ```
   Boy: (i-1, j) —> (i, j) —>(i+1, j) 
   Girl: (i, j-1) —> (i, j) —>(i, j+1)
   ```
* Now, we can solve the problem by creating 4 tables:
   * Boy’s journey from `(1, 1)` to meeting cell `(i, j)`.
   * Boy’s journey from meeting cell `(i, j)` to end `(n, m)`.
   * Girl’s journey from start `(n, 1)` to meeting cell `(i, j)`.
   * Girl’s journey from meeting cell `(i, j)` to end `(1, n)`
* The meeting cell can range from `2 <= i <= n - 1` and `2 <= j <= m - 1`.


Let's now move on to the implementation to better understand the logic that we discussed above.

Use dynamic programming to solve a real-world interview problem based on grids.

Overview

Number Theory

Number Theory

Divide and Conquer

Greedy Algorithms

Greedy Algorithms

Recursion and Backtracking

Recursion and Backtracking

Dynamic Programming

Graphs

Bonus Lessons

Problem Involving Grids - 4

Problem statement

Solution: