Position: L3 at Google India
YOE : New Grad
Thank you Leetcode Community! Yesterday I had my first telephonic interview with Google India. Only 1 question was asked.
Given a gird of MxN cells, with Integer cell values, we can define a path effort of a path from source (0,0) to the destination (M-1, N-1) as the max of the absolute differences of the adjacent cell values. While traversing, you can move up, down, left and right — 4 moves from the current cell in the grid. For a given Threshold value, find if it is possible to have a path in such a matrix with the effort not greater than the threshold value, from source to destination.
Example:
If we have a 3x3 matrix as follows -
[[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]
Threshold = 4
Result: YES
As, 1->2->3->6->9 or 1->2->5->6->9 or ...
#include<bits/stdc++.h>
using namespace std;
int dir[4][2] = {{-1,0},{1,0},{0,1},{0,-1}};
bool isPossible(int x,int y,int rows,int cols){
if(x < 0 or x >= rows or y < 0 or y >= cols) return 0;
return 1;
}
bool dfs(vector<vector<int> > &grid,int x,int y,int &rows,int &cols,int threshold,vector<vector<int> > &visited){
if(x == rows-1 and y == cols-1){
return 1;
}
visited[x][y] = 1;
for(int k = 0;k < 4;k++){
int nx = x + dir[k][0];
int ny = y + dir[k][1];
if(isPossible(nx,ny,rows,cols) and abs(grid[nx][ny]-grid[x][y]) <= threshold and !visited[nx][ny]){
int ans = dfs(grid,nx,ny,rows,cols,threshold,visited);
if(ans) return 1;
}
}
return 0;
}
int main(){
int rows,cols,threshold;
cin>>rows>>cols>>threshold;
vector<vector<int> > grid(rows,vector<int>(cols));
vector<vector<int> > visited(rows,vector<int>(cols,0));
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
cin>>grid[i][j];
}
}
bool ans = dfs(grid,0,0,rows,cols,threshold,visited);
if(ans) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
} TC : O(n^2)
SC : O(n^2)
I wrote a code similar to this, Is my approach correct.
I was also thinking of using dp to store the answer at any given x,y.
Similar to this
#include<bits/stdc++.h>
using namespace std;
int dir[4][2] = {{-1,0},{1,0},{0,1},{0,-1}};
bool isPossible(int x,int y,int rows,int cols){
if(x < 0 or x >= rows or y < 0 or y >= cols) return 0;
return 1;
}
bool visited[105][105];
bool dfs(vector<vector<int> > &grid,int x,int y,int &rows,int &cols,int threshold,vector<vector<int> > dp){
if(x == rows-1 and y == cols-1){
return 1;
}
if(dp[x][y] != -1){
return dp[x][y];
}
visited[x][y] = 1;
int ans = 0;
for(int k = 0;k < 4;k++){
int nx = x + dir[k][0];
int ny = y + dir[k][1];
if(isPossible(nx,ny,rows,cols) and abs(grid[nx][ny]-grid[x][y]) <= threshold and !visited[nx][ny]){
ans |= dfs(grid,nx,ny,rows,cols,threshold,dp);
}
}
return dp[x][y] = ans;
}
int main(){
int rows,cols,threshold;
cin>>rows>>cols>>threshold;
vector<vector<int> > grid(rows,vector<int>(cols));
vector<vector<int> > dp(rows,vector<int>(cols,-1));
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
cin>>grid[i][j];
}
}
bool ans = dfs(grid,0,0,rows,cols,threshold,dp);
if(ans) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}Which approach is better.
TC : O(n^2)
SC : O(n^2)
Also interviewer asked which approach is better dfs or bfs? I said dfs as, as soon we get the result we will return true, while in bfs we may have to explore a lot of options as it is level wise so only at the end level we will reach m-1,n-1.
I gave the 1st approach as solution in the interview, 2nd approach is just for my own knowledge.
Waiting for the telephonic result.
**Edit: **
I cleared the telephonic rounds. But the recruiter said work on your communication a little. Can someone provide any tips regarding the same?