SumoLogic Interview Question
SDE-3sCountry: India
Interview Type: In-Person
/*
Given a matrix of n*n. Each cell contain 0, 1, -1.
0 denotes there is no diamond but there is a path.
1 denotes there is diamond at that location with a path
-1 denotes that the path is blocked.
Now you have start from 0,0 and reach to last cell & then return back to 0,0 collecting maximum no of diamonds.
While going to last cell you can move only right and down.
While returning back you can move only left and up.
*/
#include<bits/stdc++.h>
using namespace std;
long long n,d[1000][1000],ans[1000][1000];
pair<long long,long long> prev[1000][1000];
void solve()
{
long long i,j;
if(d[0][0]!=-1)
{
ans[0][0]=d[0][0];
prev[0][0]=make_pair(-1,-1);
}
for(i=1;i<n;i++)
{
if(d[0][i]==-1)
break;
ans[0][i]=ans[0][i-1]+d[0][i];
prev[0][i]=make_pair(0,i-1);
}
while(i<n)
{
ans[0][i]=-1;
i++;
}
for(i=1;i<n;i++)
{
if(d[i][0]==-1)
break;
ans[i][0]=ans[i-1][0]+d[i][0];
prev[i][0]=make_pair(i-1,0);
}
while(i<n)
{
ans[i][0]=-1;
i++;
}
for(i=1;i<n;i++)
{
for(j=1;j<n;j++)
{
if(d[i][j]==-1)
{
ans[i][j]=-1;
continue;
}
if(ans[i-1][j]>ans[i][j-1])
{
ans[i][j]=ans[i-1][j]+d[i][j];
prev[i][j]=make_pair(i-1,j);
}
else
{
ans[i][j]=ans[i][j-1]+d[i][j];
prev[i][j]=make_pair(i,j-1);
}
}
}
}
void update()
{
long long i,j;
pair<long long,long long> node;
i=n-1;
j=n-1;
while(i!=-1&&j!=-1)
{
node=prev[i][j];
d[i][j]=0;
i=node.first;
j=node.second;
}
}
void init()
{
long long i,j;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
ans[i][j]=0;
}
}
}
int main()
{
long long i,j,res;
res=0LL;
cin>>n;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
cin>>d[i][j];
}
}
solve();
res=res+ans[n-1][n-1];
update();
init();
solve();
res=res+ans[n-1][n-1];
cout<<"Max Path Diamonds : "<<res;
return 0;
}
I think the maximum number of collected diamonds can be the best two paths to reach the last cell. Probably, the following logic can work.
int fun(int mat[][N] ) {
int table[N][N];
table[0][0] = mat[0][0];
for(int i=1;i<n;i++) {
if(mat[i][i] != -1)
table[i][0] = table[i-1][0] + mat[i][0];
else
table[i][0] = -1;
}
for(int j=1;j<n;j++) {
if(mat[[0][j] != -1)
table[0][j] = table[0][j-1] + mat[0][j];
else
table[0][j] = -1;
}
for(int i=1;i<n;i++) {
for(int j=0;j<n;j++) {
if(mat[i][j] != -1)
table[i][j] = max(table[i][j-1],table[i-1][j]) + mat[i][j];
else
table[i][j] = -1;
}
}
if(table[n-1][n-2] < 0 || table[n-2][n-1] < 0) {
cout<<"No Roundtrip path possible";
return -1;
}
return table[n-2][n-1] + table[n-1][n-2] + mat[n-1][n-1] - mat[0][0];
}
I believe it can be solved using dynamic programming.
- Ankit August 10, 2015First of all, starting from (0,0) and reaching the last cell, using right and down movements only, and then coming back using left and up movements only is same as starting from (0,0) and reaching last cell twice.
In first iteration we will start from 0,0 and reach last cell while collecting the diamonds
in second iteration, we will use the modified matrix (in which the diamonds have been collected on the path followed in the first step) and again use the same algorithm to find max-diamond-path.
To find optimal path in an iteration, we will use the following logic to build the matrix
- For first row, only left moves can reach a cell. Simply add the diamonds before a cell till a -1 is encountered
- For first column, only down moves can reach a cell. Add the diamonds before a cell till -1 is encountered
- For all other cells, either it can be reached from the cell above it or cell to the left of it. Depending on which cell has a higher diamond count, take that path
Here is my code for the solution described above: www[DOT]edufyme[DOT]com/code/?id=c20ad4d76fe97759aa27a0c99bff6710