## Adobe Interview Question for SDE1s

Country: India

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

if I understood this then,
here 1 means blocked
and 2/0 means gold with values 2/0

You need the shortest path with max gold count

it simply dfs/bfs problem I think

set<int> paths_sum;
int r,c;
bool isSafe(int sx,int sy,vector<vector<int>> &grid){
if(sx<0 || sy<0 || sx>=r || sy>=c || grid[sx][sy]==1)return 0;
return 1;
}
void dfs(int sx,int sy,int dx,int dy,vector<vector<int>> &grid,int sum){
if(sx<0 || sy<0 || sx>=r || sy>=c || grid[sx][sy]==1)return;
if(sx==dx && sy==dy){paths_sum.insert(sum); sum=0; }
int temp= grid[sx][sy];
grid[sx][sy]=1;
if(isSafe(sx+1,sy,grid)) dfs(sx+1,sy,dx,dy,grid,sum+grid[sx+1][sy]);
if(isSafe(sx,sy+1,grid)) dfs(sx,sy+1,dx,dy,grid,sum+grid[sx][sy+1]);
if(isSafe(sx,sy-1,grid)) dfs(sx,sy-1,dx,dy,grid,sum+grid[sx][sy-1]);
if(isSafe(sx-1,sy,grid)) dfs(sx-1,sy,dx,dy,grid,sum+grid[sx-1][sy]);

grid[sx][sy]=temp;
}

int min_path(int n,int m,int dx,int dy,vector<vector<int>> grid){
r=n;
c=m;
paths_sum.clear();
dfs(0,0,dx,dy,grid,0);
if(paths_sum.size()<1) return -1;
return *paths_sum.end();
}

Also there can be DP solution

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

if I understood this then,
here 1 means blocked
and 2/0 means gold with values 2/0

You need the shortest path with max gold count

it simply dfs/bfs problem I think

``````set<int> paths_sum;
int r,c;
bool isSafe(int sx,int sy,vector<vector<int>> &grid){
if(sx<0 || sy<0 || sx>=r || sy>=c || grid[sx][sy]==1)return 0;
return 1;
}
void dfs(int sx,int sy,int dx,int dy,vector<vector<int>> &grid,int sum){
if(sx<0 || sy<0 || sx>=r || sy>=c || grid[sx][sy]==1)return;
if(sx==dx && sy==dy){paths_sum.insert(sum); sum=0; }
int temp= grid[sx][sy];
grid[sx][sy]=1;
if(isSafe(sx+1,sy,grid)) dfs(sx+1,sy,dx,dy,grid,sum+grid[sx+1][sy]);
if(isSafe(sx,sy+1,grid)) dfs(sx,sy+1,dx,dy,grid,sum+grid[sx][sy+1]);
if(isSafe(sx,sy-1,grid)) dfs(sx,sy-1,dx,dy,grid,sum+grid[sx][sy-1]);
if(isSafe(sx-1,sy,grid)) dfs(sx-1,sy,dx,dy,grid,sum+grid[sx-1][sy]);

grid[sx][sy]=temp;
}

int min_path(int n,int m,int dx,int dy,vector<vector<int>> grid){
r=n;
c=m;
paths_sum.clear();
dfs(0,0,dx,dy,grid,0);
if(paths_sum.size()<1) return -1;
return *paths_sum.end();
}``````

Also there can be DP solution

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

You need the shortest path with max gold count

it simply dfs/bfs problem I think

``````set<int> paths_sum;
int r,c;
bool isSafe(int sx,int sy,vector<vector<int>> &grid){
if(sx<0 || sy<0 || sx>=r || sy>=c || grid[sx][sy]==1)return 0;
return 1;
}
void dfs(int sx,int sy,int dx,int dy,vector<vector<int>> &grid,int sum){
if(sx<0 || sy<0 || sx>=r || sy>=c || grid[sx][sy]==1)return;
if(sx==dx && sy==dy){paths_sum.insert(sum); sum=0; }
int temp= grid[sx][sy];
grid[sx][sy]=1;
if(isSafe(sx+1,sy,grid)) dfs(sx+1,sy,dx,dy,grid,sum+grid[sx+1][sy]);
if(isSafe(sx,sy+1,grid)) dfs(sx,sy+1,dx,dy,grid,sum+grid[sx][sy+1]);
if(isSafe(sx,sy-1,grid)) dfs(sx,sy-1,dx,dy,grid,sum+grid[sx][sy-1]);
if(isSafe(sx-1,sy,grid)) dfs(sx-1,sy,dx,dy,grid,sum+grid[sx-1][sy]);

grid[sx][sy]=temp;
}

int min_path(int n,int m,int dx,int dy,vector<vector<int>> grid){
r=n;
c=m;
paths_sum.clear();
dfs(0,0,dx,dy,grid,0);
if(paths_sum.size()<1) return -1;
return *paths_sum.end();
}``````

Also there can be DP solution

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

``````#include<bits/stdc++.h>
using namespace std;
void def(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("inputz.txt","r",stdin);
freopen("error.txt","r",stderr);
freopen("output.txt","w",stdout);
#endif
}

vector<vector<vector<int>>> dist;
vector<vector<int>> dp;
vector<pair<int,int>> coins;
int R;
int C;
int allOnes, numCoins;
int MAXDIST = 1000 * 1000;

bool isInRange(int r, int c) {
return r >= 0 && r < R && c >= 0 && c < C;
}

void extractCoins(vector<vector<int>> &arr) {
for (int r = 0; r < R; r++)
for (int c = 0; c < C; c++)
if (arr[r][c] == 2)
coins.push_back({r,c});
}

void setDistances(vector<vector<int>> &arr, int coin) {
for (int r = 0; r < R; r++)
for (int c = 0; c < C; c++)
dist[r][c][coin] = MAXDIST;

vector<vector<bool>> visited(R,vector<bool>(C,0));
queue<pair<int,int>> q;
pair<int,int> startPoint = coins[coin];
q.push(startPoint);
visited[startPoint.first][startPoint.second] = 1;
dist[startPoint.first][startPoint.second][coin] = 0;

vector<int> dr = {0, -1, 0, 1};
vector<int> dc = {-1, 0, 1, 0};

while (!q.empty()) {
pair<int,int> point = q.front();q.pop();
int oldR = point.first;
int oldC = point.second;

for (int k = 0; k < 4; k++) {
int newR = oldR + dr[k];
int newC = oldC + dc[k];
if (isInRange(newR, newC) && !visited[newR][newC] && arr[newR][newC] != 1) {
pair<int,int> newPoint = {newR, newC};
visited[newR][newC] = true;
dist[newR][newC][coin] = dist[oldR][oldC][coin] + 1;
q.push(newPoint);
}
}
}
}

int getMinDist(int coin, int seq, int Ra, int Ca) {
if (seq == allOnes) return dist[Ra][Ca][coin];
if (dp[coin][seq] != -1) return dp[coin][seq];

int res = INT_MAX;
for (int i = 0; i < numCoins; i++)
if ((seq & (1 << i)) == 0) {
int newSeq = seq | (1 << i);
pair<int,int> pos = coins[i];
res = min(res, getMinDist(i, newSeq, Ra, Ca) + dist[pos.first][pos.second][coin]);
}
return dp[coin][seq] = res;
}

int minMoves1(vector<vector<int>> &arr, int Ra, int Ca) {
R = arr.size();
C = arr[0].size();
pair<int,int> startPoint = {0, 0};
coins.push_back(startPoint);
extractCoins(arr);
numCoins = coins.size();
allOnes = (1 << numCoins) - 1;

int dpR = numCoins;
int dpC = allOnes + 1;
dp.resize(dpR,vector<int>(dpC,-1));

dist.resize(R,vector<vector<int>>(C,vector<int>(numCoins,0)));

for (int i = 0; i < numCoins; i++)
setDistances(arr, i);
int ans = getMinDist(0, 1, Ra, Ca);
return ans >= MAXDIST ? -1 : ans;

}

int main()
{
def();
int n,m;
cin>>n>>m;
vector<vector<int>> a(n,vector<int>(m,0));
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>a[i][j];
int dx,dy;
cin>>dx>>dy;
cout<<minMoves1(a,dx,dy);
}``````

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.