NVIDIA Interview Question
Country: India
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
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.
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)
#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();
}
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++) {
matrixdata[matrix[i][j] - 'a'].add(new Coord(j, i));
}
// 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;
}
}
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
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;
}
#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.
}
#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.
}
While traversing the 2d matrix ( a[][] ) row wise.
- Cerberuz August 30, 2012If ( 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.
}