Adobe Interview Question
Computer ScientistsCountry: United States
can someone plase elaborate the question?..cant we just start matching the characters of the word to be searched by starting it from the first row till the end..that wud b done in the order of the dimension of array..pls replyy..
Link to run the code: ideone.com/9ttqJt
int di[] = {0,1,1};
int dj[] = {1,1,0};
bool findStr(vector<string> s, int i, int j, string tofind, int l){
int r = s.size();
int c = s[0].size();
if(l == tofind.size()) return true;
if(i >= r || j >= c) return false;
bool ret = false;
if(tofind[l] == s[i][j]){
for(int d=0; d<3; d++){
ret |= findStr(s, i+di[d], j+dj[d], tofind, l+1);
}
}
else{
for(int d=0; d<3; d++){
ret |= findStr(s, i+di[d], j+dj[d], tofind, 0);
}
}
return ret;
}
bool FindString(char **str, int m, int n, char *wordToFind, int pos)
{
if(str[m,n] == wordToFind[pos])
{
if(strlen(wordToFind) == pos)
{
return true;
}
else
{
return FindString(str, m+1, n, wordToFind, pos+1) || FindString(str, m, n+1, wordToFind, pos+1) || FindString(str, m+1, n+1, wordToFind, pos+1)
}
}
else if( m>M || n >N)
return false;
else
return FindString(str, m+1, n, wordToFind, pos) || FindString(str, m, n+1, wordToFind, pos) || FindString(str, m+1, n+1, wordToFind, pos)
}
Please let me know if I am going wrong here
I am starting from (0,0).
We store "Row" position of every character present inside the dual array into HASH TABLE. Key: Char, Value - Row position. Then we can search hash table for every character in the search string in O(1) if its present or not . Now, since we cannot move upwards, while searching each character of search string, we can keep track of the row of the last character we found and compare it with the row of the current character. If it is >= than previous row, then move forward and make this row as current row. if its < or character cannot be found in hash table then string does not exists and exit the loop.
Complexity O(n) and Space Complexity O(n).
Interesting.. but is it correct ? consider searching CAT in the below matrix
ACA
AAA
ATD
How will you Hash A ?
Iterative Version in Python:
This is essentially brute force, but it efficiently terminates paths as soon as a mismatched letter is found.
def test():
matrix = [
['C', 'X', 'T', 'Z'],
['X', 'A', 'Y', 'Z'],
['W', 'X', 'Q', 'R'],
]
assert [(0,0), (1,1), (0,2)] == find_string(matrix, 'CAT')
def find_string(matrix, s):
substrings = []
for row in range(len(matrix)):
for col in range(len(matrix[0])):
c = matrix[row][col]
if c == s[0]:
if len(s) == 1:
return [(row, col)]
substrings.append([(row, col)])
while substrings:
substring = substrings.pop()
row, col = substring[-1]
deltas = [
(-1, -1), (-1, 0), (-1, 1),
( 0, -1), ( 0, 1),
( 1, -1), ( 1, 0), ( 1, 1),
]
for rd, cd in deltas:
rn = row + rd
cn = col + cd
if (rn, cn) in substring:
# don't allow repeats
continue
try:
c = matrix[rn][cn]
except IndexError:
continue
if c != s[len(substring)]:
continue
new_substring = substring + [(rn,cn)]
if len(new_substring) == len(s):
return new_substring
substrings.append(new_substring)
return None
test()
Please let me know if the below code is correct.......if it contains the string then it returns true else False
#include<stdio.h>
#include<conio.h>
int main()
{
int i,j,a=0;
char str[][3] = {
'c','b','k',
'd','a','l',
'g','t','i'
};
char search_str[3]="cat";
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
if(str[i][j] == search_str[a])
a++;
}
}if(a == 3){printf("True");}else{printf("False");}
getch();
}
Looks like a DP problem.
in a two dimensional array A, I define a function
F(i, j) =
= 0 if max {F(i-1, j), F(i, j-1), F(i-1, j-1)} = 0 and A[i, j] != first character of input string
= 1 if max {F(i-1, j), F(i, j-1), F(i-1, j-1)} = 0 and A[i, j] == first character of input string
= 1 + max {F(i-1, j), F(i, j-1), F(i-1, j-1)} if index of A[i, j] in input String = 1 + index of max {F(i-1, j), F(i, j-1), F(i-1, j-1)} in the input string; 0 otherwise
At any (i, j) if the value is the length of the input string, we know, we have found the answer.
Thus, the matrix
c b k
d a l
g t i
will be transformed to
1 0 0
0 2 0
0 3 0
thus, at position [3, 2] : we know, we have formed the word
comment, if you find any issue with the logic
bool findword(char a[][],char b[],int n,int m)
{ int count=b.length();
int k=0,t,p;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
{ t=i;p=j;
if(a[t][p]==b[k])
{ if(a[t][p+1]==b[k+1]&&p<n-1) { p=p+1;k++;}
if(a[t][p-1]==b[k+1]&&p>=0) { p=p-1;k++;}
if(a[t+1][p]==b[k+1]&&t<m-1){ t=t+1;k++;}
if(a[t+1][p+1]==b[k+1]&&t<m-1&&p<n-1) { t=t+1;p=p+1;k++;}
}
else
{ if(count==k) retrun true;
else
k=0;
}
}
#include<iostream>
using namespace std;
void FindStr(char a[3][3],char str[3])
{
int assciArry[9],assciStr[3];
int i=0,k=0,l=0;
for(int j=0;j<3;j++)
{
assciArry[k]= a[i][j];
k++;
}
i++;
for(int j=0;j<3;j++)
{
assciArry[k]= a[i][j];
k++;
}
i++;
for(int j=0;j<3;j++)
{
assciArry[k]= a[i][j];
k++;
}
for(int j=0;j<3;j++)
{
assciStr[l]=str[j];
l++;
}
for(int m=0;m<9;m++)
{
std::cout<<assciArry[m]<<"\n";
}
for(int n=0;n<3;n++)
{
std::cout<<assciStr[n]<<"\n";
}
int p=0,q=0,count=0;
while (p<9)
{
if(assciArry[p]==assciStr[q])
{
count++;
p++;q++;
}
else if(q==3)
{
q = 0;
p++;
}
else
{
q++;
}
}
if(count == 3)
{
std::cout<<"String Found"<<"\n";
}
else
{
std::cout<<"String Not Found"<<"\n";
}
}
int main()
{
char arr[][3]={{'c','b','k'},
{'d','a','l'},
{'g','t','i'}};
char str[]="zat";
char str1[]="cat";
FindStr(arr,str);
FindStr(arr,str1);
return 0;
}
#include <iostream>
#include <string>
using namespace std;
bool FindStringInMatrix(int i,int j,char**str_matrix, char* str_tofind, int str_tag){
if(str_tag>strlen(str_tofind)-1){
return true;
}
if (str_tofind[str_tag]==str_matrix[i][j]){
//cout<<"find "<<str_tofind[str_tag]<<" in ("<<i<<","<<j<<") :"<< str_tag<<endl;
if(FindStringInMatrix(i+1,j,str_matrix,str_tofind,str_tag+1))
return true;
if(FindStringInMatrix(i,j+1,str_matrix,str_tofind,str_tag+1))
return true;
if(FindStringInMatrix(i+1,j+1,str_matrix,str_tofind,str_tag+1))
return true;
}
return false;
}
int main(){
char** str_read=new char*[3];
for(int i=0;i<3;i++){
str_read[i]=new char[3];
}
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
cin>>str_read[i][j];
}
}
char* str_tofind=new char[4];
for(int i=0;i<3;i++){
cin>>str_tofind[i];
}
str_tofind[3]='\0';
if(FindStringInMatrix(0,0,str_read,str_tofind,0))
cout<<"String in the Matrix"<<endl;
else
cout<<"Not find in the Matrix"<<endl;
return 0;
}
#include <iostream>
#include <string>
using namespace std;
bool FindStringInMatrix(int i,int j,char**str_matrix, char* str_tofind, int str_tag){
if(str_tag>strlen(str_tofind)-1){
return true;
}
if (str_tofind[str_tag]==str_matrix[i][j]){
//cout<<"find "<<str_tofind[str_tag]<<" in ("<<i<<","<<j<<") :"<< str_tag<<endl;
if(FindStringInMatrix(i+1,j,str_matrix,str_tofind,str_tag+1))
return true;
if(FindStringInMatrix(i,j+1,str_matrix,str_tofind,str_tag+1))
return true;
if(FindStringInMatrix(i+1,j+1,str_matrix,str_tofind,str_tag+1))
return true;
}
return false;
}
int main(){
char** str_read=new char*[3];
for(int i=0;i<3;i++){
str_read[i]=new char[3];
}
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
cin>>str_read[i][j];
}
}
char* str_tofind=new char[4];
for(int i=0;i<3;i++){
cin>>str_tofind[i];
}
str_tofind[3]='\0';
if(FindStringInMatrix(0,0,str_read,str_tofind,0))
cout<<"String in the Matrix"<<endl;
else
cout<<"Not find in the Matrix"<<endl;
return 0;
}
# include <stdio.h>
# include <conio.h>
#include <string.h>
void main(){
int arr[26];
char str[16];
char mat[4][4] = {{'d','a','c','b'},
{'o','g','t','l'},
{'l','p','l','e'},
{'m','x','t','m'}};
for(int i=0; i<26; i++){
arr[i] = 0;
}
for(int i=0;i<4; i++){
for(int j= 0; j<4; j++){
arr[mat[i][j]-97]++;
}
}
printf("Enter any String: ");
gets(str);
int k, found = 1;
for(k=0; k< strlen(str); k++){
if(arr[*(str +k) -97]){
arr[*(str +k) -97]--;
}else{
found = 0; break;
}
}
if(found)
printf("\nString found");
else
printf("\nString not found");
getch();
}
Below is the recursive code for finding all words in a matrix.
I have considered all posssible 8 directions from any given cell which can be modified according to what is asked.
A cell can constitute to only one word and hence if it is a part of any word I have marked it with a '*'.
bool solveMatrix(int row,int col, string word)
{
if(word.compare("*") ==0)
return false;
if(dictionary.search(word))
{
cout<<"\n"<<word;
matrix[row][col] = '*';
return true;
}
for(int i=0; i<MAXNEIGHBOURS ; i++)
{
int newRow = row + displacement[i][0];
int newCol = col + displacement[i][1];
char originalCharacter = matrix[row][col];
matrix[row][col] = '*';
if(isValid(newRow,newCol))
{
if(solveMatrix(newRow,newCol,word+matrix[newRow][newCol]))
return true;
}
matrix[row][col] = originalCharacter;
}
return false;
}
complete executing code can be found at ms-amazon.blogspot.in/2013/07/print-all-words-in-matrix-cbk-dal-gti.html
#include<stdio.h>
#include<conio.h>
int find(char a[][3],char b[],int i, int j, int len,int m)
{
if(i>=3 || j>=3)
return 0;
if(m==(len-1))
return 1;
else if(a[i][j]==b[m])
{
++m;
return (find(a,b,i+1,j,len,m)|| find(a,b,i,j+1,len,m));
}
else
return (find(a,b,i+1,j,len,m) || find(a,b,i,j+1,len,m));
}
int main()
{
char a[][3]={'c','b','k',
'd','a','l',
'g','t','i',
};
char b[]="mat";
if(find(a,b,0,0,3,0))
printf("there");
else
printf("no");
getchar();
getchar();
return 0;
}
My logic is simple. Start with the top left element i.e a[0][0] and recursively move to left and down to search for each letter of the word. I have called for left and down but it can be called for left, down and right. Once we find a letter we increment the m to point to next element in the string array to be found. Thats all. Thanks
1) create a hashtable< character, num_time> based on the 2D array.
2) sort the string given.
3) for each distinct char C in the string, check that the number of time C exists in the array (via the hashtable) >= number of times C exists in string. If 3) is true for C, repeat 3) for next character until end. If it is false , return false.
4) return true.
U might point out to your interviewer that if this is an operation you will run frequently, you might get a substantial gain by make the hashtable permanent.
ignore my comment, i completely missed the fact that there is an adjacency requirement for the letters in the 2D array
@JZ : this is incorrect.. search CAT in this matrix with your Algo.
B,C,D,Z
E,A,F,G
J,K,L,T
CAT doesn't exist in this matrix but your Algo will return true.
Longest common subsequence between the matrix (iterated in row major form) and given string.
- coder March 05, 2013i.e.
return LCSLength((char *)givenMatrix, NumElements(givenMatrix), str, strlen(str)) == strlen(str);