## Adobe Interview Question for Computer Scientists

Country: United States

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

Longest common subsequence between the matrix (iterated in row major form) and given string.
i.e.
return LCSLength((char *)givenMatrix, NumElements(givenMatrix), str, strlen(str)) == strlen(str);

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

lcs wud be o(mn)..but we can do it on o(m)...

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

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..

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

I think you are right.
It is as simple iterating through the whole matrix matching every character of the string to be find.

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

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;
}``````

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

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).

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

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).

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

Interesting.. but is it correct ? consider searching CAT in the below matrix

ACA
AAA
ATD

How will you Hash A ?

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

Maybe we can store both the row and column of each char in Hash and then start with the row,col pair of the first element in the string. For every subsequent character in the string, look up if its row,col co-ordinate is adjacent to the previous one.

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

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()``````

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

Yeah we can build trie with all words. Then we can check whether given word is present or not.

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

How about building a trie for the words in the dictionary,
and then using a BFS to pattern match each letter in the matrix ...??

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

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();
}``````

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

``````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

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

BAT is also a valid word, how will you find that.

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

``````Well nice idea but if i am correct then this algorithm will not take care of right to left associativity eg.
c	b	k
d	a	l
t	x	i
in this matrix there is
c
a
t
but  is not traceble.``````

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

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;
}
}

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

#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
{
}
}
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;
}

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

O(n)

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

#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(){

for(int i=0;i<3;i++){
}
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
}
}
char* str_tofind=new char[4];
for(int i=0;i<3;i++){
cin>>str_tofind[i];
}
str_tofind[3]='\0';
cout<<"String in the Matrix"<<endl;
else
cout<<"Not find in the Matrix"<<endl;

return 0;
}

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

``````#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(){

for(int i=0;i<3;i++){
}
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
}
}
char* str_tofind=new char[4];
for(int i=0;i<3;i++){
cin>>str_tofind[i];
}
str_tofind[3]='\0';
cout<<"String in the Matrix"<<endl;
else
cout<<"Not find in the Matrix"<<endl;

return 0;
}``````

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

All the elements in the 2D array can be put into a queue. Then keep removing an element and check if it matches to the next character in the string to be searched.

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

``````# 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
getch();
}``````

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

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

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

``````#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;
}``````

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

what exactly are you doing ?

Comment hidden because of low score. Click to expand.
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

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

This is Brute Force, how can you optimize ?

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

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.

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

ignore my comment, i completely missed the fact that there is an adjacency requirement for the letters in the 2D array

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

@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.

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

No, issues :-)

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.