Collecting Coins - Amazon Top Interview Questions
Problem Statement :
You are given a two-dimensional integer matrix where each cell represents number of coins in that cell. Assuming we start at matrix[0][0], and can only move right or down, find the maximum number of coins you can collect by the bottom right corner.
Constraints
n, m ≤ 100 where n and m are the number of rows and columns in matrix.
Example 1
Input
matrix = [
[0, 3, 1, 1],
[2, 0, 0, 4]
]
Output
9
Explanation
We take the following path: [0, 3, 1, 1, 4]
Example 2
Input
matrix = [
[0, 3, 1, 1],
[2, 0, 0, 4],
[1, 5, 3, 1]
]
Output
12
Explanation
We take the following path: [0, 2, 1, 5, 3, 1]
Example 3
Input
matrix = [
[0, 2, 1],
[2, 5, 0],
[4, 1, 3]
]
Output
11
Explanation
We take the following path: [0, 2, 5, 1, 3]
Solution :
Solution in C++ :
int solve(vector<vector<int>>& matrix) {
vector<vector<int>> dp(int(matrix.size()), vector<int>(int(matrix[0].size()), 0));
dp[0][0] = matrix[0][0];
for (int j = 0; j < int(matrix.size()); ++j) {
for (int i = 0; i < int(matrix[0].size()); ++i) {
if (i - 1 >= 0) dp[j][i] = max(dp[j][i - 1] + matrix[j][i], dp[j][i]);
if (j - 1 >= 0) dp[j][i] = max(dp[j - 1][i] + matrix[j][i], dp[j][i]);
}
}
return dp[int(matrix.size()) - 1][int(matrix[0].size()) - 1];
}
Solution in Python :
class Solution:
def solve(self, matrix):
for i in range(len(matrix)):
for j in range(len(matrix[0])):
fromLeft = matrix[i][j]
fromAbove = matrix[i][j]
if j > 0:
fromLeft = matrix[i][j] + matrix[i][j - 1]
if i > 0:
fromAbove = matrix[i][j] + matrix[i - 1][j]
matrix[i][j] = max(fromLeft, fromAbove)
return matrix[-1][-1]
View More Similar Problems
Minimum Average Waiting Time
Tieu owns a pizza restaurant and he manages it in his own way. While in a normal restaurant, a customer is served by following the first-come, first-served rule, Tieu simply minimizes the average waiting time of his customers. So he gets to decide who is served first, regardless of how sooner or later a person comes. Different kinds of pizzas take different amounts of time to cook. Also, once h
View Solution →Merging Communities
People connect with each other in a social network. A connection between Person I and Person J is represented as . When two persons belonging to different communities connect, the net effect is the merger of both communities which I and J belongs to. At the beginning, there are N people representing N communities. Suppose person 1 and 2 connected and later 2 and 3 connected, then ,1 , 2 and 3 w
View Solution →Components in a graph
There are 2 * N nodes in an undirected graph, and a number of edges connecting some nodes. In each edge, the first value will be between 1 and N, inclusive. The second node will be between N + 1 and , 2 * N inclusive. Given a list of edges, determine the size of the smallest and largest connected components that have or more nodes. A node can have any number of connections. The highest node valu
View Solution →Kundu and Tree
Kundu is true tree lover. Tree is a connected graph having N vertices and N-1 edges. Today when he got a tree, he colored each edge with one of either red(r) or black(b) color. He is interested in knowing how many triplets(a,b,c) of vertices are there , such that, there is atleast one edge having red color on all the three paths i.e. from vertex a to b, vertex b to c and vertex c to a . Note that
View Solution →Super Maximum Cost Queries
Victoria has a tree, T , consisting of N nodes numbered from 1 to N. Each edge from node Ui to Vi in tree T has an integer weight, Wi. Let's define the cost, C, of a path from some node X to some other node Y as the maximum weight ( W ) for any edge in the unique path from node X to Y node . Victoria wants your help processing Q queries on tree T, where each query contains 2 integers, L and
View Solution →Contacts
We're going to make our own Contacts application! The application must perform two types of operations: 1 . add name, where name is a string denoting a contact name. This must store name as a new contact in the application. find partial, where partial is a string denoting a partial name to search the application for. It must count the number of contacts starting partial with and print the co
View Solution →