# Collecting Disappearing Coins - Amazon Top Interview Questions

### Problem Statement :

```You are given a two-dimensional list of integers matrix where each matrix[r][c] represents the number of coins in that cell. When you pick up coins on matrix[r][c], all the coins on row r - 1 and r + 1 disappear, as well as the coins at the two cells matrix[r][c + 1] and matrix[r][c - 1]. Return the maximum number of coins that you can collect.

Constraints

n, m ≤ 250 where n and m are the number of rows and columns in matrix

Example 1

Input

matrix = [
[1, 7, 6, 5],
[9, 9, 3, 1],
[4, 8, 1, 2]
]

Output

22

Explanation

We can pick cells with the coins 7, 5, and 8 and 2.```

### Solution :

```                        ```Solution in C++ :

int best(vector<int>& v) {
// return the maximum sum of elements given that you can't choose adjacent elements
int n = v.size();
// dp[i] is the maximum sum you can get considering exactly the first i elements
vector<int> dp(n + 1);
for (int i = 0; i < n; i++) {
// don't choose element i
dp[i + 1] = max(dp[i + 1], dp[i]);
// choose element i
dp[i + 1] = max(dp[i + 1], v[i] + (i == 0 ? 0 : dp[i - 1]));
}
return dp[n];
}

int solve(vector<vector<int>>& matrix) {
vector<int> rows;
for (auto& row : matrix) {
rows.push_back(best(row));
}
return best(rows);
}```
```

```                        ```Solution in Java :

import java.util.*;

class Solution {
public int solve(int[][] matrix) {
if (matrix == null || matrix.length == 0)
return 0;
int[] arr = new int[matrix.length];

for (int i = 0; i < matrix.length; i++) arr[i] = getMaximumNonAdjacentSum(matrix[i]);

}

if (arr.length == 0)
return 0;
if (arr.length == 1)
return arr[0];
if (arr.length == 2)
return Math.max(arr[0], arr[1]);

int[] dp = new int[arr.length];
dp[0] = arr[0];
dp[1] = Math.max(arr[0], arr[1]);

for (int i = 2; i < arr.length; i++) dp[i] = Math.max(dp[i - 1], arr[i] + dp[i - 2]);
return dp[arr.length - 1];
}
}```
```

```                        ```Solution in Python :

class Solution:
def best(self, l):
for elem in l:
if isinstance(elem, list):
elem = self.best(elem)

def solve(self, matrix):
return self.best(matrix)```
```

## Truck Tour

Suppose there is a circle. There are N petrol pumps on that circle. Petrol pumps are numbered 0 to (N-1) (both inclusive). You have two pieces of information corresponding to each of the petrol pump: (1) the amount of petrol that particular petrol pump will give, and (2) the distance from that petrol pump to the next petrol pump. Initially, you have a tank of infinite capacity carrying no petr

## Queries with Fixed Length

Consider an -integer sequence, . We perform a query on by using an integer, , to calculate the result of the following expression: In other words, if we let , then you need to calculate . Given and queries, return a list of answers to each query. Example The first query uses all of the subarrays of length : . The maxima of the subarrays are . The minimum of these is . The secon

## QHEAP1

This question is designed to help you get a better understanding of basic heap operations. You will be given queries of types: " 1 v " - Add an element to the heap. " 2 v " - Delete the element from the heap. "3" - Print the minimum of all the elements in the heap. NOTE: It is guaranteed that the element to be deleted will be there in the heap. Also, at any instant, only distinct element