Adobe Interview Question
Software Engineer / DevelopersWorking code:
Use the function
a[i][j]+max(a[i-1][j],a[i][j+1]);
public class CoinsCollect {
static int[][] coins={{1,5,3},{4,5,2}};
static int rows=2;
static int columns=3;
private static int max(int i,int j)
{
if(i<0 || j>=columns)
return 0;
else
return coins[i][j]+Math.max(max(i-1,j),max(i,j+1));
}
public static void main(String[] args)
{
System.out.println(max(rows-1,0));
}
}
Mathematical formula for this type of problem could be the number of ways of reaching from bottom right to the top left. Allowed directions are two, that is up and right.
For M rows, N columns, number of ways:
(M + N)! /( M! * N!)
It of course, doesn't consider the constraint of picking maximum gold coins. It is just the number of ways possible.
dict={}
for i in range(n-1,-1,-1):
for j in range(n-1,-1,-1):
left_neighbor = (dict[(i,j+1)] if dict.has_key((i,j+1)) else 0)
down_neighbor = (dict[(i+1,j)] if dict.has_key((i+1,j)) else 0)
# last row & last col
if i == (n-1) and j == (n-1): dict[(i,j)] = A[i][j]
# last row
elif i == (n-1):
dict[(i,j)] = A[i][j] + left_neighbor
# last col
elif j == (n-1):
dict[(i,j)] = A[i][j] + down_neighbor
# general case
else:
dict[(i,j)] = A[i][j] + max(left_neighbor,down_neighbor)
print "max possible coins =", dict[0,0]
dynamic programming solution in o(n^2) - without using a recursive function:
dict={}
for i in range(n-1,-1,-1):
for j in range(n-1,-1,-1):
left_neighbor = (dict[(i,j+1)] if dict.has_key((i,j+1)) else 0)
down_neighbor = (dict[(i+1,j)] if dict.has_key((i+1,j)) else 0)
# last row & last col
if i == (n-1) and j == (n-1): dict[(i,j)] = A[i][j]
# last row
elif i == (n-1):
dict[(i,j)] = A[i][j] + left_neighbor
# last col
elif j == (n-1):
dict[(i,j)] = A[i][j] + down_neighbor
# general case
else:
dict[(i,j)] = A[i][j] + max(left_neighbor,down_neighbor)
print "max possible coins =", dict[0,0]
Use Dynamic Programming.
- Anil August 10, 2011Let say the given matrix is A, where A[i,j] is the # of coins at [i,j] position and S[i,j] is the maximum number of points for the part of matrix A which is in right-top of [i,j].
Then we have
S[i,j] = A[i,j] + max(S[i+1,j], S[i,j+1])
start from i=1,j=1 and take care of boundary conditions.
That will give a O(n^2) solution.
Without using DP it is O(2^n).