## NVIDIA Interview Question

Country: India

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

While traversing the 2d matrix ( a[][] ) row wise.
If ( a[i][j] == first character of given word ) {
search for rest of the letters in 4 directions i.e. right, right diagonally down, down and left diagonally down.
} else if( a[i][j] == last character of the given word ) {
search for remaining characters in reverse order in 4 directions i.e. left, right diagonally up, up, left diagonally up.
}

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

it is a brrute force approach

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

I don't think we can solve it in any better way. If we have multiple queries we can use trie + caching.

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

search for the first char throughout the matrix. If found then search around it for the second. if found then continue in the same direction. If not found then go through the matrix again to find first char. take care of boundary conditions.

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

1) Create a hash table with character as a key and value representing the coordinates of the character present in the matrix.
2) if The search string is "rat",then search for the first character in the hash map and find its coordinates.
3) After this search for the second character in the hash table and find its coordinates and find the relationship("r") between the coordinates of the first char and the second char,whether it lies in the left straight or right straight or diagonal.
3) After this see for the third char and check for the relationship of its coordinate with the coordinate of its last char and if it matches with the "r" ,then continue else return false.
4) Continue this process till the end of the string .

Time complexity :
1) In creating hash table : O(m*n)
2) search for string occurence : O (l) : l is the string length

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

construct four flat arrays out of the matrix: row-wise, col-wise, left-diagonal and right-diagonal (All in O(n)). Then search both the query and the reverse of the query in these four arrays (which can be done again in O(n+k)). The only thing to take care of is to make sure we don't match strings across the rows, cols,... but that doesn't change the complexity.

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

O(n) ??
Consider matrix to be MXN then complexity for array creation itself will be MXN.

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

create HashTable with key as co-ordinate of matrix like (00,01,02.........) and value with the char at that position then search O(n*n){for hash table creation}+O(n)

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

similar to first soultion.

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

#include<stdio.h>

void main()
{
char matrix[10][10],find[10];
int k=0,i1=0,j1=0,size=0,i,j,len,temp,chk=1 ;

printf("Enter the size for char matrix for sizeXsize\n");
scanf("%d",&size);

printf("Enter the elements for char matrix \n");
for(i=0;i<size;i++)
{
for(j=0;j<size;j++)
{
printf("\n Enter %dth row %dth col data\n",i+1,j+1);
fflush(stdin);
scanf("%c",&matrix[i][j]);
}
}
printf("\n");

for(i=0;i<size;i++)
{
for(j=0;j<size;j++)
{
printf("%c ",matrix[i][j]);
}
printf("\n");
}

printf("Word to be found out : \n");
scanf("%s",find);
len=strlen(find);
temp=len;
for(i=0;i<size && chk;i++)
{
for(j=0;j<size && chk;j++)
{
k=0;
if(matrix[i][j]==find[k])
{
i1=i;
j1=j;
printf("\nFOUND\n");
while(temp)
{
if(matrix[i1][j1]==find[k] &&
i1<size &&
j1 < size &&
k <=len )
{
i1++;
j1++;
k++;
}
temp--;
}

if(i==(i1-len) && i1 < size && j1 < size && k <len)
{
printf("\nWORD exists diagonally\n");
chk=0;
break;
}

i1=i;
j1=j;
temp=len;
k=0;
while(temp)
{
if(matrix[i1][j1]==find[k] &&
i1>=0 &&
j1 >=0 &&
k <=len )
{
i1--;
j1--;
k++;
}
temp--;
}
if(i==(i1+len))
{
printf("\nWORD exists diagonally upwards \n");
chk=0;
break;
}

i1=i;
j1=j;
k=0;
temp=len;
while(temp)
{
if(matrix[i1][j1]==find[k] &&
i1<size &&
j1 >=0 &&
k <=len )
{
i1++;
j1--;
k++;
}
temp--;
}

if(i==(i1-len) && j==(j1+len))
{
printf("\nWORD exists across diagonally \n");
chk=0;
break;
}

k=0;
i1=i;
j1=j;
temp=len;
while(temp)
{
if(matrix[i1][j1]==find[k] && i1<size && j1 < size && k <=len)
{
i1++;
k++;
}
temp--;
}
if(i==(i1-len))
{
printf("\nWORD exists vertically\n");
chk=0;
break;
}

k=0;
i1=i;
j1=j;
temp=len;
while(temp)
{
if(matrix[i1][j1]==find[k] && i1<size && j1 < size && k <=len && i1>=0 && j1 >=0 )
{
i1--;
k++;
}
temp--;
}
if(i==(i1+len))
{
printf("\nWORD exists vertically upwards \n");
chk=0;
break;
}

k=0;
i1=i;
j1=j;
temp=len;
while(temp)
{
if(matrix[i1][j1]==find[k] && i1<size && j1 < size && k <=len)
{
j1++;
k++;
}
temp--;
}
if(j==(j1-len))
{
printf("\nWORD exists horizentally\n");
chk=0;
break;
}

k=0;
i1=i;
j1=j;
temp=len;
while(temp)
{
if(matrix[i1][j1]==find[k] && i1<size && j1 < size && k <=len && i1>=0 && j1 >=0 )
{
j1--;
k++;
}
temp--;
}
if(j==(j1+len))
{
printf("\nWORD exists horizentally upwards \n");
chk=0;
break;
}
}
}
}
getch();
}

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

I created an array of ArrayList of each alphabet's position.
To find a word, first locate the position of the word's first alphabet and start to explore 8 directions from it.
O(n) to create the array + 8*O(length of the word to find) to search the matrix.

``````public class JE16 {
public static void main(String[] args) {
// find a word in 2D array
char[][] matrix = {{'p', 'b', 's', 'd'},
{'o', 'o', 'p', 't'},
{'l', 'b', 'a', 'd'},
{'e', 'r', 'l', 'd'}};
char[] word1 = {'r', 'a', 't'};
char[] word2 = {'p', 'o', 'l', 'e'};
char[] word3 = {'d', 'a', 'b'};
char[] word4 = {'l', 'o', 's'};
char[] word5 = {'l', 'a', 'p', 's'};
char[] word6 = {'b', 'o', 'b'};
char[] word7 = {'a', 'b', 'c'};

System.out.println(Arrays.toString(word1) + " : " + (findWord(matrix, word1) ? "Found" : "Not Found") );
System.out.println(Arrays.toString(word2) + " : " + (findWord(matrix, word2) ? "Found" : "Not Found") );
System.out.println(Arrays.toString(word3) + " : " + (findWord(matrix, word3) ? "Found" : "Not Found") );
System.out.println(Arrays.toString(word4) + " : " + (findWord(matrix, word4) ? "Found" : "Not Found") );
System.out.println(Arrays.toString(word5) + " : " + (findWord(matrix, word5) ? "Found" : "Not Found") );
System.out.println(Arrays.toString(word6) + " : " + (findWord(matrix, word6) ? "Found" : "Not Found") );
System.out.println(Arrays.toString(word7) + " : " + (findWord(matrix, word7) ? "Found" : "Not Found") );
}

static boolean findWord(char[][] matrix, char[] word) {
int m = matrix.length, n = matrix[0].length; // m rows, n cols
ArrayList<Coord>[] matrixdata = new ArrayList[26];
for(int i=0; i<26; i++)
matrixdata[i] = new ArrayList<Coord>();

// Create ArrayList
for(int i=0; i<m; i++)
for(int j=0; j<n; j++) {
}

// Find the word
Coord[] unitvector = {new Coord(-1, 0), new Coord(-1, 1), new Coord(0, 1), new Coord(1, 1),
new Coord(1, 0), new Coord(1, -1), new Coord(0, -1), new Coord(-1, -1) };
for(int i=0; i<matrixdata[word[0]-'a'].size(); i++) {
int startx = matrixdata[word[0]-'a'].get(i).x;
int starty = matrixdata[word[0]-'a'].get(i).y;
// explore 8 different directions
for(int j=0; j<8; j++) {
if(boundCheck(unitvector[j], startx, starty, n, m, word.length)) {
boolean bFound = true;
for(int k=1; k<word.length; k++) {
if(matrix[starty+k*unitvector[j].y][startx+k*unitvector[j].x] == word[k])
continue;
else {
bFound = false;
break;
}
}
if(bFound) {
System.out.println("start : (" + startx + "," + starty + ") direction : (" + unitvector[j].x + "," + unitvector[j].y + ")");
return true;
}
}
}
}
return false;
}

public static boolean boundCheck(Coord unitvector, int startx, int starty, int MaxX, int MaxY, int length) {
if(unitvector.x > 0 && MaxX-startx < length || unitvector.x < 0 && startx+1 < length)
return false;
if(unitvector.y > 0 && MaxY-starty < length || unitvector.y < 0 && starty+1 < length)
return false;

return true;
}
}``````

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

Can you use KMP algorithm in this?

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

first add all element of array in a 1D array and then find all the permutation of string using and search for a "RAT" or whatever word u wanna know in that string .. like if u r using c then ---> strstr("rat",permutation of string)..if it is true break the further process and return true

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

C++ implementation

``````#include <iostream>
using namespace std;
bool isSafe(int i,int j,int n)
{
if(i>=0&&i<n&&j>=0&&j<n)return true;
return false;
}
bool findStrUtill(char mat[][100],int n,string str,int l,int r,int k)
{
if(k>=str.size())return true;
int x[]={-1,-1,-1,0,0,1,1,1};
int y[]={-1,0,1,-1,1,-1,0,1};
for(int i=0;i<8;i++)
{
int ll=l+x[i],rr=r+y[i];
if(isSafe(ll,rr,n)&&mat[ll][rr]==str[k])
{
char c=mat[ll][rr];	mat[ll][rr]='.';
if(findStrUtill(mat,n,str,ll,rr,k+1)) return true;
mat[ll][rr]=c;
}
}
return false;
}

bool findStr(char mat[][100],int n,string str)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(mat[i][j]==str[0])
{
char c=str[0]; mat[i][j]='.';
if(findStrUtill(mat,n,str,i,j,1))return true;
mat[i][j]=c;
}
}
}
return false;
}
int main() {
int n;
cin>>n;
char mat[100][100];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>mat[i][j];
string str;
cin>>str;
if(findStr(mat,n,str))cout<<"YES"<<endl;
else cout<<"NO"<<endl;
return 0;
}``````

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

What's the time complexity

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

Your code will produce Incorrect o/p, if it's being used for more than 1 test cases.
While returning true, Matrix needs to be updated(mat[ll][rr]=c).

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

``````#include <iostream>
#include <cstring>
#include <unordered_map> // for hashing
using namespace std;

//define directions
const int NW = 1;
const int NN = 2;
const int NE = 3;
const int WW = 4;
const int EE = 5;
const int SW = 6;
const int SS = 7;
const int SE = 8;

/*
N*N matrix having various alphabets in different cells is given. Also a word is given. You have to find the position of this word in the given matrix.

Approach:
1. set up double for loop to traverse the matrix, looking for the 1st char of target word
2. once found, search the rest chars from each of 8 possible directions, if mismatch or border condition happens, discard that direction and continue with the other one; if successfully locate all the chars, the function return true and stores the coordinate of 1st char and the direction info to array.
3. if all nxn trials failed, we return false to indicate non-existance of the word.
*/

int xof(int dir)
{
if (dir == NW || dir == NN || dir == NE)
return -1;
else if (dir == WW || dir == EE)
return 0;
else
return 1;
}
int yof(int dir)
{
if (dir == NW || dir == WW || dir == SW)
return -1;
else if (dir == NN || dir == SS)
return 0;
else
return 1;
}

// function takes matrix and target word and size n, stores the location of found word to res array
bool findWord(char** matrix, char* word, int n, int* res)
{
// set up double for loop to search for 1st char
for (int i =0; i<n; i++)
{
for (int j=0; j<n;j++)
{
//if found, go through all 8 directions to search for the rest
if (matrix[i][j] == word[0])
{
cout<< "find char "<<word[0]<<" at ("<< i<<", "<<j<<") "<<endl;
//number 1-8 indicates direction NW, N, NE, W, E, SW, S, SE
for (int k=1; k<=8; k++)
{
int x = i;
int y = j;
char* tmp_word = word; //local copy of word
tmp_word++; // delete first char
int count = strlen(tmp_word); //count = total_char - 1
bool canFind = false; //check condition
//search for rest chars; count decrements 1 each time a subsequent char is found, or instantly becomes 0 to indicate nonexistance in current direction, canFind will indicate the result of search
while(count)
{
x = x + xof(k);
y = y + yof(k);
//cout<< "(x,y) = ("<<x<<", "<<y<<") "<<endl;
//if find the next char, we gonna continue search for next char until tmp_word has no char
if (x>=0 && x<n && y>=0 && y<n && matrix[x][y] == tmp_word[0])
{
cout<< "find char "<<tmp_word[0]<<" at ("<< x<<", "<<y<<") "<<endl;
canFind = true;
tmp_word++;
count--;
}
// if x,y out of range or char mismatch, then return false for unable to find word
else
{
canFind = false;
count = 0;
}
}
// if found, we will save current i,j to locate 1st char, then the direction number to indicate the location of rest chars.
if (canFind)
{
res[0] = i;
res[1] = j;
res[2] = k;
return true;
}
}
}
}
}
//nothings foun, return nonexistance
return false;
}

int main()
{
int n = 5;
char** m = new char*[n];
for (int i=0; i<n; i++)
m[n] = new char[n];

// create a test matrix
m[0][0] = 'a'; m[0][1] = 'b'; m[0][2] = 'c'; m[0][3] = 'd'; m[0][4] = 'e';
m[1][0] = 's'; m[1][1] = 'g'; m[1][2] = 'a'; m[1][3] = 's'; m[1][4] = 'g';
m[2][0] = 'r'; m[2][1] = 'l'; m[2][2] = 'q'; m[2][3] = 'w'; m[2][4] = 'd';
m[3][0] = 't'; m[3][1] = 'h'; m[3][2] = 'u'; m[3][3] = 'e'; m[3][4] = 's';
m[4][0] = 'u'; m[4][1] = 'b'; m[4][2] = 'e'; m[4][3] = 't'; m[4][4] = 'd';

//set a test string word
char* word = (char*)"ubettt";
//cout<< word<<endl<<strlen(word)<<endl;
//print the table
for (int i =0; i<n; i++)
{
for (int j = 0; j< n; j++)
{
cout<<m[i][j]<<' ';
}
cout<<endl;
}
//
int* res = new int[3];
bool ot = findWord(m, word, n, res);
if(ot)
cout<<res[0] <<' '<<res[1]<<' '<<res[2]<<endl;
else
cout<<"no result"<<endl;
// the res array gives the location of word by giving first 2 elements as the corrdinates of first char, then direction.
}``````

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

``````#include <iostream>
#include <cstring>
#include <unordered_map> // for hashing
using namespace std;

//define directions
const int NW = 1;
const int NN = 2;
const int NE = 3;
const int WW = 4;
const int EE = 5;
const int SW = 6;
const int SS = 7;
const int SE = 8;

/*
N*N matrix having various alphabets in different cells is given. Also a word is given. You have to find the position of this word in the given matrix.

Approach:
1. set up double for loop to traverse the matrix, looking for the 1st char of target word
2. once found, search the rest chars from each of 8 possible directions, if mismatch or border condition happens, discard that direction and continue with the other one; if successfully locate all the chars, the function return true and stores the coordinate of 1st char and the direction info to array.
3. if all nxn trials failed, we return false to indicate non-existance of the word.
*/

int xof(int dir)
{
if (dir == NW || dir == NN || dir == NE)
return -1;
else if (dir == WW || dir == EE)
return 0;
else
return 1;
}
int yof(int dir)
{
if (dir == NW || dir == WW || dir == SW)
return -1;
else if (dir == NN || dir == SS)
return 0;
else
return 1;
}

// function takes matrix and target word and size n, stores the location of found word to res array
bool findWord(char** matrix, char* word, int n, int* res)
{
// set up double for loop to search for 1st char
for (int i =0; i<n; i++)
{
for (int j=0; j<n;j++)
{
//if found, go through all 8 directions to search for the rest
if (matrix[i][j] == word[0])
{
cout<< "find char "<<word[0]<<" at ("<< i<<", "<<j<<") "<<endl;
//number 1-8 indicates direction NW, N, NE, W, E, SW, S, SE
for (int k=1; k<=8; k++)
{
int x = i;
int y = j;
char* tmp_word = word; //local copy of word
tmp_word++; // delete first char
int count = strlen(tmp_word); //count = total_char - 1
bool canFind = false; //check condition
//search for rest chars; count decrements 1 each time a subsequent char is found, or instantly becomes 0 to indicate nonexistance in current direction, canFind will indicate the result of search
while(count)
{
x = x + xof(k);
y = y + yof(k);
//cout<< "(x,y) = ("<<x<<", "<<y<<") "<<endl;
//if find the next char, we gonna continue search for next char until tmp_word has no char
if (x>=0 && x<n && y>=0 && y<n && matrix[x][y] == tmp_word[0])
{
cout<< "find char "<<tmp_word[0]<<" at ("<< x<<", "<<y<<") "<<endl;
canFind = true;
tmp_word++;
count--;
}
// if x,y out of range or char mismatch, then return false for unable to find word
else
{
canFind = false;
count = 0;
}
}
// if found, we will save current i,j to locate 1st char, then the direction number to indicate the location of rest chars.
if (canFind)
{
res[0] = i;
res[1] = j;
res[2] = k;
return true;
}
}
}
}
}
//nothings foun, return nonexistance
return false;
}

int main()
{
int n = 5;
char** m = new char*[n];
for (int i=0; i<n; i++)
m[n] = new char[n];

// create a test matrix
m[0][0] = 'a'; m[0][1] = 'b'; m[0][2] = 'c'; m[0][3] = 'd'; m[0][4] = 'e';
m[1][0] = 's'; m[1][1] = 'g'; m[1][2] = 'a'; m[1][3] = 's'; m[1][4] = 'g';
m[2][0] = 'r'; m[2][1] = 'l'; m[2][2] = 'q'; m[2][3] = 'w'; m[2][4] = 'd';
m[3][0] = 't'; m[3][1] = 'h'; m[3][2] = 'u'; m[3][3] = 'e'; m[3][4] = 's';
m[4][0] = 'u'; m[4][1] = 'b'; m[4][2] = 'e'; m[4][3] = 't'; m[4][4] = 'd';

//set a test string word
char* word = (char*)"ubettt";
//cout<< word<<endl<<strlen(word)<<endl;
//print the table
for (int i =0; i<n; i++)
{
for (int j = 0; j< n; j++)
{
cout<<m[i][j]<<' ';
}
cout<<endl;
}
//
int* res = new int[3];
bool ot = findWord(m, word, n, res);
if(ot)
cout<<res[0] <<' '<<res[1]<<' '<<res[2]<<endl;
else
cout<<"no result"<<endl;
// the res array gives the location of word by giving first 2 elements as the coordinates of first char, then direction.
}``````

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.