Adobe Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
you can't get all the words with this approach unless i am unable to understand your approach. Could you give little bit of detail
I assume its something like a[4][4] = { a,e,i,j | c,d,o,k | l,m,n,p | q,s,t,u }. Now traverse the matrix in n2 - [a|ae|aei|aeij|ac|acl|aclq]and so on ... for each word search in dictionary maintained in trie in O(k)
I think there is no need to check all of them. Suppose if we have q m c k p d ... When we search the dictionary if we have any words starting with "qm" we will know that there are no words starting with that so we can skip that sequence completely. This way we can save more time.
Also, you need to ask the interviewer whether you can reconsider a letter. I mean if you have c, a, n should we consider it as two words can, an?
looks different to me. the 10506747 question seems to be limiting the size of the matrix. In that case, its easy to simply enumerate all the words . In this question, you really have to be smart about the datastructure you choose
#include<iostream>
using namespace std;
int main()
{char a[10][10];
char s[20];
cout<<"eneter the matrix character of 5 by 5 matrix\n";
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
cin>>a[i][j];
cout<<"enter the char string which we want to find of length 3.....\n";
for(int i=0;i<3;i++)
cin>>s[i];
int k=0;
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
{ int count=0;
if(a[i][j]==s[k])
{ count++;
if(a[i][j+1]==s[k+1])
{ while(count!=3&&j<5)
{ if(a[i][j+1]==s[k+1])
{ count++; j++;k++;}
else
{ count=1;}
}
if(count==3)
{ cout<<"string is present\n"; break;}
}
else if(a[i][j-1]==s[k+1])
{ while(count!=3&&j>=0)
{ if(a[i][j-1]==s[k+1])
{ count++;j--;k++;}
else
{ count=1; break;}
}
if(count==3)
{ cout<<"string is present \n";break;}
}
else if(a[i+1][j]==s[k+1])
{ while(count!=3&&i<5)
{ if(a[i+1][j]==s[k+1])
{ count++; i++;k++;}
else
{ count=1; break;}
}
if(count==3)
{ cout<<"string is present\n";break;}
}
else if(a[i-1][j]==s[k+1])
{ while(count!=3&&i>=0)
{ if(a[i-1][j]==s[k+1])
{ count++;i--;k++;}
else
{ count=1; break;}
}
if(count==3)
{cout<<"string is present \n"; break;}
}
else if(a[i+1][j+1]==s[k+1])
{ while(count!=3&&i<5&&j<5)
{ if(a[i+1][j+1]==s[k+1])
{ count++;i++;j++;k++;}
else
{count=1; break;}
}
if(count==3)
{ cout<<"string is present\n";
break;}
}
else if(a[i-1][j+1]==s[k+1])
{ while(count!=3&&i>=0&&j<5)
{ if(a[i-1][j+1]==s[k+1])
{ count++;i--;j++;k++;}
else
{count=1;break;}
}
if(count==3)
{ cout<<"string is present\n";
break;}
}
else if(a[i+1][j-1]==s[k+1])
{ while(count!=3&&i<5&&j>=0)
{ if(a[i+1][j-1]==s[k+1])
{ count++;i++;j--;k++;}
else
{ count=1;break;}
}
if(count==3)
{ cout<<"string is present\n";
break;}
}
else if(a[i-1][j-1]==s[k+1])
{ while(count!=3&&i>=0&&j>=0)
{ if(a[i-1][j-1]==s[k+1])
{ count++;i--;j--;k++;}
else
{ count=1; break;}
}
if(count==3)
{ cout<<"string is present\n";
break;}
}
}
}
system("pause");
return 0;
}
While enumerating the matrix through a nested for loop , doubly linked lists can be maintained to represent the rows and columns which would be very easy to reverse.
- Anonymous September 19, 2012So basically all possible words can be found in n^2 complexity
Let me know if this is correct , I would want to actually code it , if this is the right direction.