Amazon Interview Question
Software Engineer / DevelopersGiven a matrix of characters M and an input string S, find if S occurs in M in horizontal or vertical direction.
Any thoughts on this questions .
I think i should search the first char of string S in matrix which will take O(M*M) time then i think we can proceed in horizontal or vertical direction. I know this is very basic solution and interviewer is probably expecting better than this .
My approach towards this problem is
Lets say we have matrix of M having m rows and n columns
always search row wise for S[0] or S[x-1] where x is the length of string.
Now suppose currently you are at (i,j) position in matrix.
int a =0; // a global variable
if( M[i,j]== S[0] && i<=(m-x)){
bool flag = true;
for( a = 1 to x-1){
if( S[a] == M[i+a,j])
continue;
else{
flag = false;
break;
}
}
a= 0;
if(flag){
we got the string.
return ;
}
}
if( M[i,j]== S[0] && j<=(n-x)){
bool flag = true;
for( a = 1 to x-1){
if( S[a] == M[i,j+a])
continue;
else{
flag = false;
break;
}
}
if(flag){
we got the string.
return ;
}
}
if( M[i,j]== S[x-1] && i<=(m-x)){
bool flag = true;
for( a = 1 to x-1){
if( S[x-a] == M[i+a,j])
continue;
else{
flag = false;
break;
}
}
a = 0;
if(flag){
we got the string.
return ;
}
}
if( M[i,j]== S[x-1] && j<=(n-x)){
bool flag = true;
for( a = 1 to x-1){
if( S[x-a] == M[i,j+a])
continue;
else{
flag = false;
break;
}
}
if(flag){
we got the string.
return ;
}
}
//If none of the above returns then
//Start searching from S[i,j+ a+1] if a+1 <=n
// else start from S[i+1,0]
In list question. make one scan on list 1 and one scan on list 2. Let sizes be m and n. If m is larger then n, then skip pointer of m from head (m-n) times. now size of both list is same. now skip each pointer side by side, till you reach common node.
in stock question one option in brute force method O(n*2). Another way is to keep track of current max and try to find minimum after that. if you find max again. reset every thing and remember the last max loss.
got selected by the way :)
- AnonymousUser March 27, 2010