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

- coder March 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- coder March 15, 2013 | Flag
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..

- coder March 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- jaks April 11, 2013 | Flag
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;
}

- HauntedGhost March 04, 2013 | Flag Reply
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).

- DashDash March 04, 2013 | Flag Reply
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).

- Nikhil March 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

ACA
AAA
ATD

How will you Hash A ?

- Abhi March 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- udit March 04, 2013 | Flag
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()

- showell30@yahoo.com March 05, 2013 | Flag Reply
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.

- Sairam Ravu March 28, 2013 | Flag
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 ...??
Any comments on this?

- jimmy514in March 09, 2013 | Flag Reply
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();	
}

- Anonymous March 09, 2013 | Flag Reply
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

- prabodh.prakash March 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- jvs April 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- yogesh.iiita April 22, 2013 | Flag
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;
}
}

- Mukesh Kumar Dhaker March 14, 2013 | Flag Reply
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
{
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;
}

- Anonymous March 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

O(n)

- Anonymous April 02, 2013 | Flag
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(){

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

- lweipku April 02, 2013 | Flag Reply
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(){

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

- lweipku April 02, 2013 | Flag Reply
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.

- Tushar Bhasme April 03, 2013 | Flag Reply
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
		printf("\nString not found");
	getch();
}

- Razz April 08, 2013 | Flag Reply
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

- varun July 14, 2013 | Flag Reply
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;
}

- Nascent March 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what exactly are you doing ?

- Anonymous March 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Nascent March 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is Brute Force, how can you optimize ?

- Abhi March 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- jz March 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- jz March 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Abhi March 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

No, issues :-)

- Abhi March 04, 2013 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More