## SumoLogic Interview Question for SDE-3s

• 0

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
1
of 1 vote

I believe it can be solved using dynamic programming.

First 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

Comment hidden because of low score. Click to expand.
0
of 0 vote

what is the output required? total diamonds or path also?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/*
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,ans;
pair<long long,long long> prev;
void solve()
{
long long i,j;
if(d!=-1)
{
ans=d;
prev=make_pair(-1,-1);
}
for(i=1;i<n;i++)
{
if(d[i]==-1)
break;
ans[i]=ans[i-1]+d[i];
prev[i]=make_pair(0,i-1);
}
while(i<n)
{
ans[i]=-1;
i++;
}
for(i=1;i<n;i++)
{
if(d[i]==-1)
break;
ans[i]=ans[i-1]+d[i];
prev[i]=make_pair(i-1,0);
}
while(i<n)
{
ans[i]=-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;
}``````

Comment hidden because of low score. Click to expand.
0

If both ans[i-1][j] and ans[i][j-1] is -1 then we should not do ans[i][j]=max(ans[i][j-1],ans[i-1][j])+d[i][j], because if d[i][j] will be 1, ans[i][j]=0 but ans[i][j] should be -1

Comment hidden because of low score. Click to expand.
0
of 0 vote

0 1 -1 1
1 0 -1 1
1 1 1 0
1 0 1 0

Comment hidden because of low score. Click to expand.
0
of 0 vote

LeetCode 741. Cherry Pickup

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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 = mat;
for(int i=1;i<n;i++)	{
if(mat[i][i] != -1)
table[i] = table[i-1] + mat[i];
else
table[i] = -1;
}
for(int j=1;j<n;j++)	{
if(mat[[j] != -1)
table[j] = table[j-1] + mat[j];
else
table[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;
}``````

Comment hidden because of low score. Click to expand.
0

Man atleast run your code atleast one time ...

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.