SumoLogic Interview Question for SDE-3s


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

- Ankit August 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- test August 10, 2015 | Flag Reply
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[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;
}

- coffeewithkaran007 May 27, 2016 | Flag Reply
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

- this matrix canot work, we have to conside forward and back as a whole process October 22, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

LeetCode 741. Cherry Pickup

- Sithis April 06, 2019 | Flag Reply
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[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];
	}

- amit August 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Man atleast run your code atleast one time ...

- PUSHKAR August 10, 2015 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More